Submission #1695211
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define M 2010 #define MOD 924844033 #define rep(i, x, y) for(int i = (x); i <= (y); i ++) inline int read() { char ch = getchar(); int x = 0, f = 1; while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); } while('0' <= ch && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } bool vis[2010][2]; int f[4010][2010][2]; bool a[4010]; int fac[4010]; int sum; int main() { int n = read(), k = read(); fac[0] = 1; rep(i, 1, n) fac[i] = 1ll * i * fac[i - 1] % MOD; rep(i, 1, n) rep(j, 0, 1) if(!vis[i][j]) { int u = i, v = j; int now = 0; while(u <= n) { vis[u][v] = 1; u += k; v ^= 1; now ++; } a[sum += now] = 1; } f[1][0][0] = 1; rep(i, 2, sum) rep(j, 0, n) { (f[i][j][0] += f[i - 1][j][0]) %= MOD; (f[i][j][0] += f[i - 1][j][1]) %= MOD; if(!a[i - 1]) { (f[i][j][1] += f[i - 1][j - 1][0]) %= MOD; } } int ans = 0; rep(i, 0, n) { ans = (ans + 1ll * (i & 1 ? -1 : 1) * fac[n - i] * (f[sum][i][0] + f[sum][i][1]) % MOD + MOD) % MOD; } cout << ans; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - ~K Perm Counting |
User | iamqzh |
Language | C++14 (GCC 5.4.1) |
Score | 900 |
Code Size | 1125 Byte |
Status | AC |
Exec Time | 60 ms |
Memory | 63104 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 900 / 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 | AC | 1 ms | 256 KB |
example2 | AC | 1 ms | 256 KB |
example3 | AC | 1 ms | 256 KB |
example4 | AC | 6 ms | 13440 KB |
handmade0 | AC | 1 ms | 256 KB |
handmade1 | AC | 58 ms | 63104 KB |
handmade2 | AC | 47 ms | 63104 KB |
handmade3 | AC | 52 ms | 59648 KB |
handmade4 | AC | 41 ms | 59648 KB |
handmade5 | AC | 58 ms | 63104 KB |
handmade6 | AC | 60 ms | 63104 KB |
maxrand0 | AC | 45 ms | 61696 KB |
maxrand1 | AC | 49 ms | 61696 KB |
maxrand2 | AC | 51 ms | 61952 KB |
maxrand3 | AC | 53 ms | 61696 KB |
maxrand4 | AC | 43 ms | 61696 KB |
rand0 | AC | 55 ms | 62848 KB |
rand1 | AC | 9 ms | 19840 KB |
rand2 | AC | 10 ms | 21888 KB |
rand3 | AC | 2 ms | 2944 KB |
rand4 | AC | 41 ms | 57600 KB |
small0 | AC | 4 ms | 9216 KB |
small1 | AC | 3 ms | 4992 KB |
small2 | AC | 4 ms | 7168 KB |
supersmall0 | AC | 1 ms | 256 KB |
supersmall1 | AC | 1 ms | 256 KB |
supersmall2 | AC | 1 ms | 256 KB |