Submission #9437198
Source Code Expand
// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <vector> #include <cmath> #define re register using namespace std; inline int read() { int X=0,w=1; char c=getchar(); while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); } while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar(); return X*w; } const int N=2000+10; const int mod=924844033; int n,k; int a[N<<1],cnt=0; int fac[N],dp[N<<1][N][2]; int main() { n=read(),k=read(); for (re int i=1;i<=k;++i) { for (re int j=i;j<=n;j+=k) a[++cnt]=j==i; for (re int j=i;j<=n;j+=k) a[++cnt]=j==i; } dp[0][0][0]=1; for (re int i=0;i<cnt;++i) for (re int j=0;j<=n;++j) { dp[i+1][j][0]=(dp[i][j][0]+dp[i][j][1])%mod; if (!a[i+1]) dp[i+1][j+1][1]=dp[i][j][0]; } fac[0]=1; for (re int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod; int ans=0; for (re int i=0;i<=n;++i) { int w=1ll*(dp[cnt][i][0]+dp[cnt][i][1])*fac[n-i]%mod; if (i&1) ans=(ans-w+mod)%mod; else ans=(ans+w)%mod; } printf("%d\n",ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - ~K Perm Counting |
User | M_sea |
Language | C++14 (GCC 5.4.1) |
Score | 900 |
Code Size | 1273 Byte |
Status | AC |
Exec Time | 32 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 | 5 ms | 13568 KB |
handmade0 | AC | 1 ms | 256 KB |
handmade1 | AC | 32 ms | 63104 KB |
handmade2 | AC | 31 ms | 63104 KB |
handmade3 | AC | 29 ms | 59648 KB |
handmade4 | AC | 27 ms | 59648 KB |
handmade5 | AC | 32 ms | 63104 KB |
handmade6 | AC | 32 ms | 63104 KB |
maxrand0 | AC | 29 ms | 61696 KB |
maxrand1 | AC | 30 ms | 61696 KB |
maxrand2 | AC | 31 ms | 62080 KB |
maxrand3 | AC | 30 ms | 61696 KB |
maxrand4 | AC | 29 ms | 61696 KB |
rand0 | AC | 32 ms | 62848 KB |
rand1 | AC | 7 ms | 19840 KB |
rand2 | AC | 8 ms | 22016 KB |
rand3 | AC | 2 ms | 2944 KB |
rand4 | AC | 26 ms | 57600 KB |
small0 | AC | 3 ms | 9344 KB |
small1 | AC | 2 ms | 4992 KB |
small2 | AC | 3 ms | 7168 KB |
supersmall0 | AC | 1 ms | 256 KB |
supersmall1 | AC | 1 ms | 256 KB |
supersmall2 | AC | 1 ms | 256 KB |