#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long N, M;
long long cache[1000005];
long long mod_exp(long long a,long long b,long long c)
{
a%=c;
if(b==0)return 1;
if(b==1)return a;
if(b&1) return (a*mod_exp((a*a)%c,(b-1)/2,c))%c;
return mod_exp((a*a)%c,b/2,c);
}
long long mod_div(long long a, long long b)
{
return (a * mod_exp(b, MOD-2, MOD)) % MOD;
}
long long solve(int pos, int left)
{
if(left < 0)
return 0;
if(pos == N)
return 1;
long long ans = (solve(pos + 1, left - 1));
ans = (ans + solve(pos + 1, left + 1) * M) % MOD;
return ans;
}
long long pow2[1000005];
long long nCm[1000005];
int main()
{
scanf("%lld%lld", &N, &M);
pow2[1] = 1;
for(int i=2; i <= N; i++)
pow2[i]= (pow2[i-1] * M) % MOD;
nCm[0] = 1;
nCm[1] = 1;
for(int i=2; i <= N/2; i++)
{
long long n = i-1;
nCm[i] = (nCm[i-1] * (n * 2 + 1)) % MOD;
nCm[i] = (nCm[i] * (n * 2 + 2)) % MOD;
nCm[i] = mod_div(nCm[i], (n + 1) * (n + 2) % MOD );
}
cache[0] = 1;
cache[1] = M;
cache[2] = M * (M+1) % MOD;
for(int i=3; i <= N; i+=2)
{
cache[i] = ((cache[i-1] * (M+1) % MOD) - (pow2[(i+1)/2] * nCm[i/2] % MOD) + MOD) % MOD;
cache[i+1] = cache[i] * (M+1) % MOD;
}
printf("%lld\n", cache[N]);
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
238 ms |
25160 KB |
Output is correct |
| 2 |
Correct |
49 ms |
25160 KB |
Output is correct |
| 3 |
Correct |
583 ms |
25160 KB |
Output is correct |
| 4 |
Correct |
655 ms |
25160 KB |
Output is correct |
| 5 |
Correct |
668 ms |
25160 KB |
Output is correct |
| 6 |
Correct |
366 ms |
25160 KB |
Output is correct |
| 7 |
Correct |
416 ms |
25160 KB |
Output is correct |
| 8 |
Correct |
278 ms |
25160 KB |
Output is correct |
| 9 |
Correct |
115 ms |
25160 KB |
Output is correct |
| 10 |
Correct |
28 ms |
25160 KB |
Output is correct |
| 11 |
Correct |
31 ms |
25160 KB |
Output is correct |
| 12 |
Correct |
591 ms |
25160 KB |
Output is correct |
| 13 |
Correct |
563 ms |
25160 KB |
Output is correct |
| 14 |
Correct |
246 ms |
25160 KB |
Output is correct |
| 15 |
Correct |
265 ms |
25160 KB |
Output is correct |
| 16 |
Correct |
240 ms |
25160 KB |
Output is correct |
| 17 |
Correct |
729 ms |
25160 KB |
Output is correct |
| 18 |
Correct |
752 ms |
25160 KB |
Output is correct |
| 19 |
Correct |
790 ms |
25160 KB |
Output is correct |
| 20 |
Correct |
795 ms |
25160 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
214 ms |
25160 KB |
Output is correct |
| 2 |
Correct |
67 ms |
25160 KB |
Output is correct |
| 3 |
Correct |
143 ms |
25160 KB |
Output is correct |
| 4 |
Correct |
719 ms |
25160 KB |
Output is correct |
| 5 |
Correct |
447 ms |
25160 KB |
Output is correct |
| 6 |
Correct |
548 ms |
25160 KB |
Output is correct |
| 7 |
Correct |
385 ms |
25160 KB |
Output is correct |
| 8 |
Correct |
215 ms |
25160 KB |
Output is correct |
| 9 |
Correct |
380 ms |
25160 KB |
Output is correct |
| 10 |
Correct |
50 ms |
25160 KB |
Output is correct |
| 11 |
Correct |
627 ms |
25160 KB |
Output is correct |
| 12 |
Correct |
655 ms |
25160 KB |
Output is correct |
| 13 |
Correct |
621 ms |
25160 KB |
Output is correct |
| 14 |
Correct |
294 ms |
25160 KB |
Output is correct |
| 15 |
Correct |
363 ms |
25160 KB |
Output is correct |
| 16 |
Correct |
363 ms |
25160 KB |
Output is correct |
| 17 |
Correct |
61 ms |
25160 KB |
Output is correct |
| 18 |
Correct |
791 ms |
25160 KB |
Output is correct |
| 19 |
Correct |
796 ms |
25160 KB |
Output is correct |
| 20 |
Correct |
784 ms |
25160 KB |
Output is correct |
