Submission #1338396

---

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 l, int n ) {
    
    for( int i = n; i >= 0; i -- )
    for( int j = min( l / 2, n - i ); j >= 1; j -- )
        dp2[i + j] = ( 1LL * dp2[i] * dp1[l][j] + dp2[i + j] ) % MOD;
    
    return;
}

int main( void ) {
    
    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( sz, n ); add( sz, n );
    }
    
    int ans = 0;
    for( int i = 0; i <= n; i ++ ) {
        if( i % 2 == 0 )
            ans = ( +1LL * dp2[i] * fct[n - i] % MOD + ans ) % MOD;
        else
            ans = ( -1LL * dp2[i] * fct[n - i] % MOD + ans + MOD ) % MOD;
    }
    
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result