Submission #2744720
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
#define MOD 1000000007
#define MAX_P 200005
Int fact[MAX_P],inv[MAX_P],finv[MAX_P];;
Int extgcd(Int a,Int b,Int& x,Int& y){
Int d=a;
if(b!=0){
d=extgcd(b,a%b,y,x);
y-=(a/b)*x;
}else{
x=1;y=0;
}
return d;
}
Int mod_inverse(Int a,Int mod){
Int x,y;
extgcd(a,mod,x,y);
return (mod+x%mod)%mod;
}
Int mod_pow(Int x,Int n,Int mod){
Int res=1;
while(n){
if(n&1) (res*=x)%=mod;
(x*=x)%=mod;
n>>=1;
}
return res;
}
Int mod_inverse2(Int a,Int mod){
return mod_pow(a,mod-2,mod);
}
void init(Int mod){
fact[0]=1;
for(Int i=1;i<MAX_P;i++)
fact[i]=(fact[i-1]*i)%mod;
inv[1]=1;
for(Int i=2;i<MAX_P;i++)
inv[i]=inv[mod%i]*(mod-mod/i)%mod;
finv[0]=1;
for(Int i=1;i<MAX_P;i++)
finv[i]=finv[i-1]*inv[i]%mod;
}
Int mod_fact(Int n,Int mod,Int& e){
e=0;
if(n==0) return 1;
Int res=mod_fact(n/mod,mod,e);
e+=n/mod;
if(n/mod%2!=0)return res*(mod-fact[n%mod]) %mod;
return res*fact[n%mod]%mod;
}
Int mod_comb(Int n,Int k,Int mod){
if(n==k||k==0) return 1;
Int e1,e2,e3;
Int a1=mod_fact(n,mod,e1),a2=mod_fact(k,mod,e2),a3=mod_fact(n-k,mod,e3);
if(e1>e2+e3) return 0;
return a1*mod_inverse(a2*a3%mod,mod)%mod;
}
Int mod_comb2(Int n,Int k,Int mod){
Int res=1;
for(Int i=0;i<k;i++){
res*=(n-i)%mod;
res%=mod;
res*=mod_inverse(i+1,mod);
res%=mod;
}
return res;
}
//only for prime mod
Int mod_comb3(Int n,Int k,Int mod){
if(k<0||k>n) return 0;
return fact[n]*finv[k]%mod*finv[n-k]%mod;
}
Int montmort(Int n,Int mod){
Int res=0,inv=1;
for(Int k=2;k<=n;k++){
(inv*=mod_inverse(k,mod))%=mod;
if(k%2) (res+=mod-inv)%=mod;
else (res+=inv)%=mod;
}
for(Int i=1;i<=n;i++)
(res*=i)%=mod;
return res;
}
// calculate P(t) from given points in [0,N]
Int LagrangePolynomial(vector<Int> &y,Int t,const Int mod){
init(mod);
Int n=y.size()-1;
Int num=1;
for(Int i=0;i<=n;i++)
num=num*((t-i)%mod)%mod;
Int res=0;
for(Int i=0;i<=n;i++){
Int tmp=(y[i]*num%mod)*mod_inverse((t-i)%mod,mod)%mod;
tmp=tmp*finv[i]%mod;
tmp=tmp*finv[n-i]%mod;
if((n-i)&1) tmp=mod-tmp;
res=(res+tmp)%mod;
}
return res;
}
//INSERT ABOVE HERE
signed main(){
Int a,b,c;
cin>>a>>b>>c;
vector<Int> po(a,1);
for(Int i=1;i<a;i++) po[i]=po[i-1]*b%MOD;
Int ans=0,co=1;
for(Int i=0;i<a;i++){
ans+=po[a-(i+1)]*co%MOD;
ans%=MOD;
co=co*(c+i)%MOD;
co=co*mod_inverse(i+1,MOD)%MOD;
}
cout<<ans<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Range Sum Queries |
User |
beet |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
2669 Byte |
Status |
AC |
Exec Time |
23 ms |
Memory |
1024 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Subtask3 |
Score / Max Score |
0 / 0 |
12 / 12 |
48 / 48 |
40 / 40 |
Status |
|
|
|
|
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 |
1 ms |
256 KB |
sample_2.txt |
AC |
1 ms |
256 KB |
sample_3.txt |
AC |
1 ms |
256 KB |
sub1_1.txt |
AC |
1 ms |
256 KB |
sub1_2.txt |
AC |
1 ms |
256 KB |
sub1_3.txt |
AC |
1 ms |
256 KB |
sub1_4.txt |
AC |
1 ms |
256 KB |
sub1_5.txt |
AC |
1 ms |
256 KB |
sub1_6.txt |
AC |
1 ms |
256 KB |
sub1_7.txt |
AC |
1 ms |
256 KB |
sub1_8.txt |
AC |
1 ms |
256 KB |
sub1_9.txt |
AC |
1 ms |
256 KB |
sub2_1.txt |
AC |
12 ms |
640 KB |
sub2_2.txt |
AC |
7 ms |
512 KB |
sub2_3.txt |
AC |
12 ms |
640 KB |
sub2_4.txt |
AC |
17 ms |
896 KB |
sub2_5.txt |
AC |
15 ms |
768 KB |
sub2_6.txt |
AC |
6 ms |
384 KB |
sub2_7.txt |
AC |
22 ms |
1024 KB |
sub2_8.txt |
AC |
3 ms |
384 KB |
sub2_9.txt |
AC |
2 ms |
256 KB |
sub3_1.txt |
AC |
17 ms |
896 KB |
sub3_2.txt |
AC |
1 ms |
256 KB |
sub3_3.txt |
AC |
11 ms |
640 KB |
sub3_4.txt |
AC |
15 ms |
768 KB |
sub3_5.txt |
AC |
15 ms |
768 KB |
sub3_6.txt |
AC |
22 ms |
1024 KB |
sub3_7.txt |
AC |
2 ms |
256 KB |
sub3_8.txt |
AC |
21 ms |
1024 KB |
sub3_9.txt |
AC |
23 ms |
1024 KB |