Submission #1442179


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<lint, lint> pi;
const int MAXN = 100005;
const int mod = 1e9 + 7;

lint ipow(lint x, lint p){
	lint ret = 1, piv = x % mod;
	while(p){
		if(p&1) ret *= piv;
		piv *= piv;
		ret %= mod;
		piv %= mod;
		p >>= 1;
	}
	return ret % mod;
}

lint a[MAXN], b[MAXN], c[MAXN];
lint inv[MAXN];
int n, m, p;

lint bino(int x, int y){
	if(x >= mod) return 0;
	lint ans = 1;
	for(int i=0; i<y; i++){
		ans *= x - i;
		ans %= mod;
		ans *= inv[i+1];
		ans %= mod;
	}
	return ans;
}

int main(){
	cin >> n >> p >> m;
	for(int i=1; i<MAXN; i++) inv[i] = ipow(i, mod-2);
	a[0] = 1;
	for(int i=1; i<n; i++) a[i] = a[i-1] * p % mod;
	b[0] = 1;
	for(int i=1; i<n; i++) b[i] = b[i-1] * ((m - 1 + i) * inv[i] % mod) % mod;
	lint ans = 0;
	for(int i=0; i<n; i++) ans = (ans + a[i] * b[n-1-i]) % mod;
	printf("%lld\n", ans);
}

Submission Info

Submission Time
Task F - Range Sum Queries
User koosaga
Language C++14 (GCC 5.4.1)
Score 100
Code Size 957 Byte
Status AC
Exec Time 18 ms
Memory 2560 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 12 / 12 48 / 48 40 / 40
Status
AC × 3
AC × 12
AC × 21
AC × 30
Set Name Test Cases
Sample sample_1.txt, sample_2.txt, sample_3.txt
Subtask1 sample_1.txt, sample_2.txt, sample_3.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub1_5.txt, sub1_6.txt, sub1_7.txt, sub1_8.txt, sub1_9.txt
Subtask2 sample_1.txt, sample_2.txt, sample_3.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub1_5.txt, sub1_6.txt, sub1_7.txt, sub1_8.txt, sub1_9.txt, sub2_1.txt, sub2_2.txt, sub2_3.txt, sub2_4.txt, sub2_5.txt, sub2_6.txt, sub2_7.txt, sub2_8.txt, sub2_9.txt
Subtask3 sample_1.txt, sample_2.txt, sample_3.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub1_5.txt, sub1_6.txt, sub1_7.txt, sub1_8.txt, sub1_9.txt, sub2_1.txt, sub2_2.txt, sub2_3.txt, sub2_4.txt, sub2_5.txt, sub2_6.txt, sub2_7.txt, sub2_8.txt, sub2_9.txt, sub3_1.txt, sub3_2.txt, sub3_3.txt, sub3_4.txt, sub3_5.txt, sub3_6.txt, sub3_7.txt, sub3_8.txt, sub3_9.txt
Case Name Status Exec Time Memory
sample_1.txt AC 16 ms 1024 KB
sample_2.txt AC 16 ms 1024 KB
sample_3.txt AC 16 ms 1024 KB
sub1_1.txt AC 16 ms 1024 KB
sub1_2.txt AC 16 ms 1024 KB
sub1_3.txt AC 16 ms 1024 KB
sub1_4.txt AC 16 ms 1024 KB
sub1_5.txt AC 16 ms 1024 KB
sub1_6.txt AC 16 ms 1024 KB
sub1_7.txt AC 16 ms 1024 KB
sub1_8.txt AC 16 ms 1024 KB
sub1_9.txt AC 16 ms 1024 KB
sub2_1.txt AC 17 ms 1792 KB
sub2_2.txt AC 17 ms 1408 KB
sub2_3.txt AC 17 ms 1792 KB
sub2_4.txt AC 17 ms 2176 KB
sub2_5.txt AC 17 ms 2048 KB
sub2_6.txt AC 17 ms 1408 KB
sub2_7.txt AC 18 ms 2560 KB
sub2_8.txt AC 16 ms 1152 KB
sub2_9.txt AC 16 ms 1024 KB
sub3_1.txt AC 17 ms 2176 KB
sub3_2.txt AC 16 ms 1024 KB
sub3_3.txt AC 17 ms 1792 KB
sub3_4.txt AC 17 ms 2048 KB
sub3_5.txt AC 17 ms 2048 KB
sub3_6.txt AC 18 ms 2560 KB
sub3_7.txt AC 16 ms 1152 KB
sub3_8.txt AC 18 ms 2432 KB
sub3_9.txt AC 18 ms 2560 KB