Submission #1476002
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> pip;
typedef pair<pll, pll> P;
const ll INF = 1ll<<29;
const ll MOD = 1000000007;
const double EPS = 1e-9;
const bool debug = 0;
//---------------------------------//
ll dp[2][2001][2];
ll fact[2001];
bool cf[2001];
ll mod = 924844033;
int main() {
int n, k; cin >> n >> k;
int cp = 1;
REP(j, 2) {
REP(i, k) {
int now = i;
cf[cp++] = false;
now += k;
while (now < n) {
cf[cp++] = true;
now += k;
}
}
}
dp[0][0][0] = 1;
FOR(i, 1, 2 * n + 1) {
int now = i & 1;
int bef = !now;
memset(dp[now], 0, sizeof(dp[now]));
REP(j, n + 1) {
if (cf[i]) {
dp[now][j][0] += dp[bef][j][0] + dp[bef][j][1];
if (j > 0) dp[now][j][1] += dp[bef][j - 1][0];
}
else {
dp[now][j][0] += dp[bef][j][0] + dp[bef][j][1];
}
dp[now][j][0] %= mod; dp[now][j][1] %= mod;
}
}
fact[0] = 1;
FOR(i, 1, n + 1) fact[i] = fact[i - 1] * i % mod;
ll ans = 0;
REP(i, n + 1) {
ll now = (dp[0][i][0] + dp[0][i][1]) % mod;
now = now * fact[n - i] % mod;
ans += now * (i & 1 ? -1 : 1);
ans = (ans + mod) % mod;
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - ~K Perm Counting |
User |
tkmst201 |
Language |
C++14 (GCC 5.4.1) |
Score |
900 |
Code Size |
1679 Byte |
Status |
AC |
Exec Time |
161 ms |
Memory |
384 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 |
9 ms |
256 KB |
handmade0 |
AC |
1 ms |
256 KB |
handmade1 |
AC |
161 ms |
384 KB |
handmade2 |
AC |
160 ms |
384 KB |
handmade3 |
AC |
143 ms |
384 KB |
handmade4 |
AC |
135 ms |
384 KB |
handmade5 |
AC |
161 ms |
384 KB |
handmade6 |
AC |
161 ms |
384 KB |
maxrand0 |
AC |
146 ms |
384 KB |
maxrand1 |
AC |
149 ms |
384 KB |
maxrand2 |
AC |
155 ms |
384 KB |
maxrand3 |
AC |
146 ms |
384 KB |
maxrand4 |
AC |
145 ms |
384 KB |
rand0 |
AC |
160 ms |
384 KB |
rand1 |
AC |
17 ms |
256 KB |
rand2 |
AC |
21 ms |
384 KB |
rand3 |
AC |
2 ms |
256 KB |
rand4 |
AC |
128 ms |
384 KB |
small0 |
AC |
5 ms |
256 KB |
small1 |
AC |
3 ms |
256 KB |
small2 |
AC |
4 ms |
256 KB |
supersmall0 |
AC |
1 ms |
256 KB |
supersmall1 |
AC |
1 ms |
256 KB |
supersmall2 |
AC |
1 ms |
256 KB |