Submission #3771239
Source Code Expand
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define int long long
#define INF 1000000000000000000
using namespace std;
#define ANS(f) if(f) cout << "YES" << endl; else cout << "NO" << endl;
typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;
template<typename T>
void readv(vector<T> &a){ REP(i, a.size()) cin >> a[i]; }
void readi(vector<int> &a){ REP(i, a.size()){cin >> a[i]; a[i]--;} }
void debug(mat m){REP(i, m.size()){ REP(j, m[0].size()){ cout << m[i][j] << ","; } cout << endl; }}
int modpow(int x, int n, int m){
int a = 1;
IREP(i, 64){
a = (a * a) % m;
if(((n >> i) & 1) == 1) a = (a * x) % m;
}
return a;
}
#define M 3300
signed main(){
int N, K; cin >> N >> K;
int mod = 1000000007;
mat dp(N + 1, vec(M + 1, 0));
if(K >= N) dp[N][1] = 1;
dp[N][0] = K + 1 - dp[N][1];
IFOR(i, 1, N){
int d = K - i;
if(d > 0) REP(j, M + 1){
dp[i][j] += d * dp[i + 1][j];
dp[i][j] %= mod;
}
REP(a, min(K, i) + 1){
REP(j, M + 1){
int s = j + (a + j) / i;
if(s <= M){
dp[i][s] += dp[i + 1][j];
dp[i][s] %= mod;
}
}
}
}
//debug(dp);
int ans = K * (K - 1) % mod;
ans = (ans * modpow(2, mod - 2, mod)) % mod;
ans = (ans * N) % mod;
ans = (ans * modpow(K + 1, N, mod)) % mod;
REP(i, M + 1){
ans -= i * dp[1][i];
ans = (ans % mod + mod) % mod;
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
G - Mancala |
User |
sumitacchan |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2084 Byte |
Status |
WA |
Exec Time |
205 ms |
Memory |
2944 KB |
Judge Result
Set Name |
sample |
All |
Score / Max Score |
0 / 0 |
0 / 1000 |
Status |
|
|
Set Name |
Test Cases |
sample |
sample-01.txt, sample-02.txt |
All |
sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, sample-01.txt, sample-02.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
WA |
1 ms |
384 KB |
01-02.txt |
WA |
2 ms |
512 KB |
01-03.txt |
WA |
3 ms |
512 KB |
01-04.txt |
WA |
149 ms |
2816 KB |
01-05.txt |
WA |
11 ms |
2944 KB |
01-06.txt |
AC |
15 ms |
2816 KB |
01-07.txt |
WA |
105 ms |
2944 KB |
01-08.txt |
WA |
180 ms |
2688 KB |
01-09.txt |
WA |
200 ms |
2816 KB |
01-10.txt |
WA |
204 ms |
2944 KB |
01-11.txt |
WA |
205 ms |
2944 KB |
01-12.txt |
WA |
14 ms |
1920 KB |
01-13.txt |
WA |
113 ms |
2816 KB |
01-14.txt |
WA |
17 ms |
1152 KB |
01-15.txt |
WA |
143 ms |
2816 KB |
01-16.txt |
WA |
110 ms |
2176 KB |
01-17.txt |
WA |
6 ms |
640 KB |
01-18.txt |
WA |
118 ms |
2816 KB |
sample-01.txt |
AC |
1 ms |
384 KB |
sample-02.txt |
WA |
10 ms |
768 KB |