| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 19700 |
2016-02-25T04:42:45 Z |
ainta |
괄호 (kriii4_R) |
C++ |
|
974 ms |
48348 KB |
#include<stdio.h>
#include<algorithm>
using namespace std;
long long Mod = 1000000007, K, F[2010000], Inv[1010000], InvF[1010000], D[1010000], Po[1010000];
int n;
long long GetInv(long long a){
int b = Mod-2;
long long r = 1;
while(b){
if(b&1)r=r*a%Mod;
a=a*a%Mod;b>>=1;
}
return r;
}
int main(){
int i;
scanf("%d%lld",&n,&K);
Po[0]=F[0]=InvF[0]=1;
for(i=1;i<=2000000;i++)F[i] = F[i-1]*i%Mod;
for(i=1;i<=1000000;i++){
Po[i] = Po[i-1]*K%Mod;
Inv[i] = GetInv(i);
InvF[i] = InvF[i-1]*Inv[i]%Mod;
}
D[1] = K;
long long tp;
for(i=1;i<n;i++){
if(i%2==0)tp = F[i]*InvF[i/2]%Mod*InvF[i/2]%Mod*Inv[i/2+1]%Mod*Po[i/2]%Mod;
else tp = 0;
D[i+1] = ((D[i]-tp+Mod)%Mod*(K+1)%Mod + tp*K)%Mod;
}
printf("%lld\n",D[n]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
897 ms |
48348 KB |
Output is correct |
| 2 |
Correct |
873 ms |
48348 KB |
Output is correct |
| 3 |
Correct |
938 ms |
48348 KB |
Output is correct |
| 4 |
Correct |
953 ms |
48348 KB |
Output is correct |
| 5 |
Correct |
952 ms |
48348 KB |
Output is correct |
| 6 |
Correct |
903 ms |
48348 KB |
Output is correct |
| 7 |
Correct |
903 ms |
48348 KB |
Output is correct |
| 8 |
Correct |
903 ms |
48348 KB |
Output is correct |
| 9 |
Correct |
874 ms |
48348 KB |
Output is correct |
| 10 |
Correct |
868 ms |
48348 KB |
Output is correct |
| 11 |
Correct |
868 ms |
48348 KB |
Output is correct |
| 12 |
Correct |
944 ms |
48348 KB |
Output is correct |
| 13 |
Correct |
935 ms |
48348 KB |
Output is correct |
| 14 |
Correct |
898 ms |
48348 KB |
Output is correct |
| 15 |
Correct |
896 ms |
48348 KB |
Output is correct |
| 16 |
Correct |
891 ms |
48348 KB |
Output is correct |
| 17 |
Correct |
955 ms |
48348 KB |
Output is correct |
| 18 |
Correct |
958 ms |
48348 KB |
Output is correct |
| 19 |
Correct |
964 ms |
48348 KB |
Output is correct |
| 20 |
Correct |
973 ms |
48348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
899 ms |
48348 KB |
Output is correct |
| 2 |
Correct |
869 ms |
48348 KB |
Output is correct |
| 3 |
Correct |
885 ms |
48348 KB |
Output is correct |
| 4 |
Correct |
960 ms |
48348 KB |
Output is correct |
| 5 |
Correct |
926 ms |
48348 KB |
Output is correct |
| 6 |
Correct |
931 ms |
48348 KB |
Output is correct |
| 7 |
Correct |
921 ms |
48348 KB |
Output is correct |
| 8 |
Correct |
900 ms |
48348 KB |
Output is correct |
| 9 |
Correct |
916 ms |
48348 KB |
Output is correct |
| 10 |
Correct |
877 ms |
48348 KB |
Output is correct |
| 11 |
Correct |
928 ms |
48348 KB |
Output is correct |
| 12 |
Correct |
951 ms |
48348 KB |
Output is correct |
| 13 |
Correct |
947 ms |
48348 KB |
Output is correct |
| 14 |
Correct |
901 ms |
48348 KB |
Output is correct |
| 15 |
Correct |
911 ms |
48348 KB |
Output is correct |
| 16 |
Correct |
902 ms |
48348 KB |
Output is correct |
| 17 |
Correct |
876 ms |
48348 KB |
Output is correct |
| 18 |
Correct |
974 ms |
48348 KB |
Output is correct |
| 19 |
Correct |
973 ms |
48348 KB |
Output is correct |
| 20 |
Correct |
962 ms |
48348 KB |
Output is correct |
