Submission #4035884
Source Code Expand
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<vector> #include<map> #include<set> #include<string> #include<queue> #include<stack> using namespace std; #define MOD 924844033 #define INF (1<<29) #define LINF (1LL<<60) #define EPS (1e-10) typedef long long Int; typedef pair<Int, Int> P; Int fact[1080000]; Int revfact[1080000]; Int rev[1080000]; void init(){ Int m = MOD; fact[0] = 1; revfact[0] = 1; rev[0] = 0; rev[1] = 1; for(int i = 1;i < 1080000;i++){ fact[i] = fact[i-1] * i % m; if(i>1)rev[i] = MOD / i * (MOD-rev[MOD % i]) % MOD; revfact[i] = revfact[i-1] * rev[i] % MOD; } } Int nCk(Int n, Int k){ if(n < k)return 0; return fact[n] * revfact[n-k] % MOD * revfact[k] % MOD; } Int dp[2160][2]; Int n, k, K; int main(){ init(); dp[0][0] = 1; cin >> n >> K; for(int i = 0;i < K*2;i++){ for(int j = i;j < n;j += 2*K){ for(int k = n;k >= 1;k--){ dp[k][0] = (dp[k][0] + dp[k][1]) % MOD; if(j >= K)dp[k][0] = (dp[k][0] + dp[k-1][0]) % MOD; if(K <= j && j < 2*K)dp[k][0] = (dp[k][0] + dp[k-1][1]) %MOD; if(j + K < n)dp[k][1] = (dp[k-1][0] + dp[k-1][1])%MOD; else dp[k][1] = 0; } cout << dp[2][0] << ";" << dp[2][1] << endl; } } Int cnt = fact[n]; for(int i = 1;i <= n;i++){ if(i % 2 == 1)cnt -= (dp[i][0] + dp[i][1]) * fact[n-i]%MOD; else cnt += (dp[i][0] + dp[i][1]) * fact[n-i] %MOD; cnt %= MOD; } if(cnt < 0)cnt += MOD; cout << cnt << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - ~K Perm Counting |
User | catupper |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1559 Byte |
Status | WA |
Exec Time | 53 ms |
Memory | 25600 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 900 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example0, example1, example2, example3, example4 |
All | example0, example1, example2, example3, example4, handmade0, handmade1, handmade2, handmade3, handmade4, handmade5, handmade6, maxrand0, maxrand1, maxrand2, maxrand3, maxrand4, rand0, rand1, rand2, rand3, rand4, small0, small1, small2, supersmall0, supersmall1, supersmall2 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
example0 | WA | 24 ms | 25600 KB |
example1 | WA | 23 ms | 25600 KB |
example2 | WA | 23 ms | 25600 KB |
example3 | WA | 23 ms | 25600 KB |
example4 | WA | 25 ms | 25600 KB |
handmade0 | WA | 23 ms | 25600 KB |
handmade1 | WA | 53 ms | 25600 KB |
handmade2 | WA | 38 ms | 25600 KB |
handmade3 | WA | 49 ms | 25600 KB |
handmade4 | WA | 35 ms | 25600 KB |
handmade5 | WA | 53 ms | 25600 KB |
handmade6 | WA | 53 ms | 25600 KB |
maxrand0 | WA | 41 ms | 25600 KB |
maxrand1 | WA | 49 ms | 25600 KB |
maxrand2 | WA | 50 ms | 25600 KB |
maxrand3 | WA | 50 ms | 25600 KB |
maxrand4 | WA | 37 ms | 25600 KB |
rand0 | WA | 51 ms | 25600 KB |
rand1 | WA | 26 ms | 25600 KB |
rand2 | WA | 26 ms | 25600 KB |
rand3 | WA | 23 ms | 25600 KB |
rand4 | WA | 40 ms | 25600 KB |
small0 | WA | 24 ms | 25600 KB |
small1 | WA | 23 ms | 25600 KB |
small2 | WA | 24 ms | 25600 KB |
supersmall0 | WA | 23 ms | 25600 KB |
supersmall1 | WA | 23 ms | 25600 KB |
supersmall2 | WA | 23 ms | 25600 KB |