Submission #1692525
Source Code Expand
#include<iostream> #include<algorithm> #include<cstdio> #include<cstdlib> #include<cstring> using namespace std; typedef long long ll; const ll maxn=2e3+10,mod=924844033; ll n,k,dp[maxn][maxn][2],ans; int main(){ ios::sync_with_stdio(false); cin>>n>>k; dp[0][0][0]=1; for(ll i=1,cnt=0;i<=2*k;++i) for(ll j=i;j<=n;j+=2*k){ ++cnt; dp[cnt][0][0]=1; for(ll a=1;a<=cnt;++a){ dp[cnt][a][0]=(dp[cnt-1][a][0]+dp[cnt-1][a][1])%mod; if(j>k) (dp[cnt][a][0]+=dp[cnt-1][a-1][0])%=mod; if(j+2*k<=n) (dp[cnt][a][1]+=dp[cnt-1][a-1][0]+dp[cnt-1][a-1][1])%=mod; else if(j+k<=n) (dp[cnt][a][0]+=dp[cnt-1][a-1][0]+dp[cnt-1][a-1][1])%=mod; } } for(ll i=0;i<=n;++i){ ll res=i&1?mod-1:1; res=res*dp[n][i][0]%mod; for(ll j=1;j<=n-i;++j) res=res*j%mod; (ans+=res)%=mod; } cout<<ans<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - ~K Perm Counting |
User | guo |
Language | C++14 (GCC 5.4.1) |
Score | 900 |
Code Size | 881 Byte |
Status | AC |
Exec Time | 33 ms |
Memory | 61312 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 | 12800 KB |
handmade0 | AC | 1 ms | 256 KB |
handmade1 | AC | 33 ms | 61312 KB |
handmade2 | AC | 27 ms | 61312 KB |
handmade3 | AC | 30 ms | 57856 KB |
handmade4 | AC | 24 ms | 57856 KB |
handmade5 | AC | 33 ms | 61312 KB |
handmade6 | AC | 33 ms | 61312 KB |
maxrand0 | AC | 26 ms | 59904 KB |
maxrand1 | AC | 29 ms | 59904 KB |
maxrand2 | AC | 31 ms | 60288 KB |
maxrand3 | AC | 30 ms | 59904 KB |
maxrand4 | AC | 25 ms | 59904 KB |
rand0 | AC | 32 ms | 61056 KB |
rand1 | AC | 7 ms | 18944 KB |
rand2 | AC | 8 ms | 20992 KB |
rand3 | AC | 2 ms | 2560 KB |
rand4 | AC | 24 ms | 55808 KB |
small0 | AC | 3 ms | 8704 KB |
small1 | AC | 2 ms | 4608 KB |
small2 | AC | 3 ms | 6656 KB |
supersmall0 | AC | 1 ms | 256 KB |
supersmall1 | AC | 1 ms | 256 KB |
supersmall2 | AC | 1 ms | 256 KB |