Submission #1514993
Source Code Expand
#include <bits/stdc++.h> #define F first #define S second #define pii pair<int, int> #define pb push_back using namespace std; typedef long long ll; typedef long double ld; const int N = 2100, mod = 924844033; ll dp[N][N][2], res[N], foo[N]; ll fact[N]; int main(){ int n, k; cin >> n >> k; for(int i=0; i<=n; i++) dp[i][0][0] = 1; for(int i=2; i<=n; i++) for(int j=1; j<=i; j++){ dp[i][j][0] += dp[i - 1][j][0] + dp[i - 1][j][1]; dp[i][j][0] %= mod; if(j>1){ dp[i][j][0] += dp[i - 2][j - 2][0] + dp[i - 2][j - 2][1]; dp[i][j][0] %= mod; } dp[i][j][1] = dp[i - 1][j - 1][1]; dp[i][j][1] += (2LL * dp[i - 2][j - 1][0] + 2LL * dp[i - 2][j - 1][1]) % mod; dp[i][j][1] %= mod; } res[0] = 1; int sum = 0; for(int r=0; r<k; r++){ int tool; if(r < (n%k)) tool = (n + k - 1)/k; else tool = n/k; for(int i=0; i<=sum+tool; i++) foo[i] = 0; for(int i=0; i<=tool; i++) for(int j=0; j<=sum; j++){ foo[i + j] += (1LL * res[j] * (dp[tool][i][0] + dp[tool][i][1])) % mod; foo[i + j] %= mod; } sum += tool; for(int i=0; i<sum; i++) res[i] = foo[i]; } fact[0] = 1; for(int i=1; i<=n; i++) fact[i] = (1LL * fact[i - 1] * i) % mod; ll ans = fact[n]; for(int i=1; i<=n; i++){ if(i % 2){ ll bad = (1LL * fact[n - i] * res[i]) % mod; ans += mod - bad; ans %= mod; }else{ ll good = (1LL * fact[n - i] * res[i]) % mod; ans += good; ans %= mod; } } cout << ans << endl; }
Submission Info
Submission Time | |
---|---|
Task | D - ~K Perm Counting |
User | KeivanR |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1545 Byte |
Status | WA |
Exec Time | 44 ms |
Memory | 66048 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 | AC | 1 ms | 256 KB |
example1 | WA | 1 ms | 256 KB |
example2 | WA | 1 ms | 256 KB |
example3 | WA | 1 ms | 256 KB |
example4 | AC | 5 ms | 12800 KB |
handmade0 | WA | 1 ms | 256 KB |
handmade1 | WA | 28 ms | 66048 KB |
handmade2 | WA | 44 ms | 66048 KB |
handmade3 | AC | 26 ms | 61952 KB |
handmade4 | WA | 38 ms | 59904 KB |
handmade5 | WA | 36 ms | 66048 KB |
handmade6 | WA | 36 ms | 66048 KB |
maxrand0 | WA | 40 ms | 61952 KB |
maxrand1 | AC | 37 ms | 61952 KB |
maxrand2 | AC | 38 ms | 64000 KB |
maxrand3 | AC | 33 ms | 61952 KB |
maxrand4 | WA | 41 ms | 61952 KB |
rand0 | AC | 37 ms | 64000 KB |
rand1 | WA | 7 ms | 18944 KB |
rand2 | WA | 8 ms | 23040 KB |
rand3 | WA | 2 ms | 2560 KB |
rand4 | WA | 36 ms | 57856 KB |
small0 | WA | 3 ms | 8704 KB |
small1 | AC | 2 ms | 4608 KB |
small2 | WA | 3 ms | 8704 KB |
supersmall0 | WA | 1 ms | 256 KB |
supersmall1 | AC | 1 ms | 256 KB |
supersmall2 | AC | 1 ms | 256 KB |