Submission #2114538
Source Code Expand
#include<bits/stdc++.h> using namespace std; const int N=4010,mod=924844033; int n,K,f[N][N][2],g[N],Fac[N];bool vis[N][2],d[N]; int main(){ scanf("%d%d",&n,&K); int tot=0; for(int i=1;i<=n;i++){ for(int j=0;j<2;j++){ if(vis[i][j])continue; int t=0; for(int x=i,y=j;x<=n;x+=K,y^=1)vis[x][y]=1,t++; d[tot+=t]=1; } } f[0][0][1]=1; for(int i=0;i<tot;i++){ for(int j=0;j<=i;j++){ f[i+1][j][0]=(1ll*f[i+1][j][0]+f[i][j][0]+f[i][j][1])%mod; if(!d[i])f[i+1][j+1][1]=(f[i+1][j+1][1]+f[i][j][0])%mod; } } for(int i=1;i<=n;i++) g[i]=(f[tot][i][0]+f[tot][i][1])%mod; Fac[0]=1; for(int i=1;i<=n;i++)Fac[i]=1ll*Fac[i-1]*i%mod; int ans=Fac[n]; for(int i=1;i<=n;i++)ans=(ans+1ll*(i&1?-1:1)*g[i]*Fac[n-i])%mod; if(ans<0)ans+=mod; cout<<ans<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - ~K Perm Counting |
User | Yuao_2001 |
Language | C++14 (GCC 5.4.1) |
Score | 900 |
Code Size | 844 Byte |
Status | AC |
Exec Time | 57 ms |
Memory | 123904 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:6:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d",&n,&K); ^
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 | 8 ms | 27136 KB |
handmade0 | AC | 1 ms | 256 KB |
handmade1 | AC | 57 ms | 123904 KB |
handmade2 | AC | 45 ms | 123904 KB |
handmade3 | AC | 52 ms | 117248 KB |
handmade4 | AC | 40 ms | 115200 KB |
handmade5 | AC | 57 ms | 123904 KB |
handmade6 | AC | 57 ms | 123904 KB |
maxrand0 | AC | 43 ms | 119296 KB |
maxrand1 | AC | 48 ms | 119296 KB |
maxrand2 | AC | 50 ms | 123392 KB |
maxrand3 | AC | 53 ms | 119296 KB |
maxrand4 | AC | 42 ms | 119296 KB |
rand0 | AC | 53 ms | 123392 KB |
rand1 | AC | 11 ms | 37376 KB |
rand2 | AC | 12 ms | 43520 KB |
rand3 | AC | 2 ms | 4608 KB |
rand4 | AC | 39 ms | 111104 KB |
small0 | AC | 6 ms | 18944 KB |
small1 | AC | 4 ms | 10752 KB |
small2 | AC | 5 ms | 14848 KB |
supersmall0 | AC | 1 ms | 256 KB |
supersmall1 | AC | 1 ms | 256 KB |
supersmall2 | AC | 1 ms | 256 KB |