Submission #1338395
Source Code Expand
#include <bits/stdc++.h> using namespace std; const int DIM = 2005; const int MOD = 924844033; int dp1[DIM][DIM], dp2[DIM], fct[DIM]; void add( int dp[DIM], int n ) { for( int i = n; i >= 0; i -- ) for( int j = min( n / 2, n - i ); j >= 1; j -- ) dp2[i + j] = ( 1LL * dp2[i] * dp[j] + dp2[i + j] ) % MOD; return; } int main( void ) { ios::sync_with_stdio( false ); cin.tie(); cout.tie(); int n, k; cin >> n >> k; dp1[0][0] = dp2[0] = fct[0] = 1; for( int i = 1; i <= n; i ++ ) { fct[i] = ( fct[i - 1] * 1LL * i ) % MOD; for( int j = 0; j <= i / 2; j ++ ) { dp1[i][j] = dp1[i - 1][j]; if( i >= 2 && j >= 1 ) dp1[i][j] = ( dp1[i][j] + dp1[i - 2][j - 1] ) % MOD; } } for( int i = 1; i <= k; i ++ ) { int sz = ceil( (n - i + 1) * 1.0 / k ); add( dp1[sz], n ); add( dp1[sz], n ); } int ans = 0; for( int i = 0; i <= n; i ++ ) { if( i % 2 == 0 ) ans = ( ans + 1LL * dp2[i] * fct[n - i] % MOD ) % MOD; else ans = ( ans - 1LL * dp2[i] * fct[n - i] % MOD + MOD ) % MOD; } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - ~K Perm Counting |
User | EmanuelNrx |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1312 Byte |
Status | TLE |
Exec Time | 2103 ms |
Memory | 14976 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | 16 ms | 3456 KB |
handmade0 | AC | 1 ms | 256 KB |
handmade1 | AC | 13 ms | 14976 KB |
handmade2 | TLE | 2103 ms | 14976 KB |
handmade3 | AC | 12 ms | 14080 KB |
handmade4 | TLE | 2103 ms | 13696 KB |
handmade5 | AC | 331 ms | 14976 KB |
handmade6 | AC | 325 ms | 14976 KB |
maxrand0 | TLE | 2103 ms | 14208 KB |
maxrand1 | TLE | 2103 ms | 14336 KB |
maxrand2 | TLE | 2103 ms | 14720 KB |
maxrand3 | AC | 133 ms | 14208 KB |
maxrand4 | TLE | 2103 ms | 14208 KB |
rand0 | TLE | 2103 ms | 14976 KB |
rand1 | AC | 217 ms | 5504 KB |
rand2 | AC | 513 ms | 5504 KB |
rand3 | AC | 2 ms | 640 KB |
rand4 | TLE | 2103 ms | 13696 KB |
small0 | AC | 16 ms | 3456 KB |
small1 | AC | 5 ms | 1024 KB |
small2 | AC | 26 ms | 1408 KB |
supersmall0 | AC | 1 ms | 256 KB |
supersmall1 | AC | 1 ms | 256 KB |
supersmall2 | AC | 1 ms | 256 KB |