Submission #1810857
Source Code Expand
#include <cstdio>
#include <iostream>
#define rep(i, x, y) for (int i = (x); i <= (y); i ++)
#define drep(i, x, y) for (int i = (x); i >= (y); i --)
using namespace std;
typedef long long LL;
const int N = 2005;
const LL mod = 924844033;
LL C[N][N], dp[N], fac[N];
inline void pre() {
rep(i, 0, N - 1) {
C[i][0] = 1;
rep(j, 1, i) {
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
if (C[i][j] >= mod) C[i][j] -= mod;
}
}
}
int main() {
pre();
int n, k, t;
cin >> n >> k;
dp[0] = 1;
rep(i, 1, k) {
t = (n - i) / k + 1;
drep(k, n, 1) {
rep(j, 1, min(k, t >> 1)) {
(dp[k] += dp[k - j] * C[t - j][j]) %= mod;
}
}
drep(k, n, 1) {
rep(j, 1, min(k, t >> 1)) {
(dp[k] += dp[k - j] * C[t - j][j]) %= mod;
}
}
}
fac[0] = 1;
rep(i, 1, n) fac[i] = fac[i - 1] * i % mod;
LL ans = 0, sgn = 1;
rep(i, 0, n) {
ans = (ans + sgn * dp[i] * fac[n - i] % mod + mod) % mod;
sgn *= -1;
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - ~K Perm Counting |
User |
The_Unbeatable |
Language |
C++14 (GCC 5.4.1) |
Score |
900 |
Code Size |
1052 Byte |
Status |
AC |
Exec Time |
32 ms |
Memory |
30208 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 |
17 ms |
30208 KB |
example1 |
AC |
17 ms |
30208 KB |
example2 |
AC |
17 ms |
30208 KB |
example3 |
AC |
17 ms |
30208 KB |
example4 |
AC |
18 ms |
30208 KB |
handmade0 |
AC |
17 ms |
30208 KB |
handmade1 |
AC |
29 ms |
30208 KB |
handmade2 |
AC |
23 ms |
30208 KB |
handmade3 |
AC |
28 ms |
30208 KB |
handmade4 |
AC |
22 ms |
30208 KB |
handmade5 |
AC |
32 ms |
30208 KB |
handmade6 |
AC |
32 ms |
30208 KB |
maxrand0 |
AC |
26 ms |
30208 KB |
maxrand1 |
AC |
31 ms |
30208 KB |
maxrand2 |
AC |
30 ms |
30208 KB |
maxrand3 |
AC |
31 ms |
30208 KB |
maxrand4 |
AC |
23 ms |
30208 KB |
rand0 |
AC |
31 ms |
30208 KB |
rand1 |
AC |
19 ms |
30208 KB |
rand2 |
AC |
18 ms |
30208 KB |
rand3 |
AC |
17 ms |
30208 KB |
rand4 |
AC |
25 ms |
30208 KB |
small0 |
AC |
17 ms |
30208 KB |
small1 |
AC |
17 ms |
30208 KB |
small2 |
AC |
17 ms |
30208 KB |
supersmall0 |
AC |
17 ms |
30208 KB |
supersmall1 |
AC |
17 ms |
30208 KB |
supersmall2 |
AC |
17 ms |
30208 KB |