Submission #857082

#	Time	Username	Problem	Language	Result	Execution time	Memory
857082		lolismek	NoM (RMI21_nom)	C++14	100 / 100	113 ms	63036 KiB

Main

#include <iostream>

#define int long long

using namespace std;

const int NMAX = 2000;
const int MOD = 1e9 + 7;

int dp[NMAX + 1][NMAX + 1];
int sz[NMAX + 1];
int s[NMAX + 1];

int comb[NMAX + 1][NMAX + 1];
int fact[NMAX + 1];

int C(int n, int k){
    if(n < 0 || k < 0 || k > n){
        return 0;
    }

    return comb[n][k];
}

int f(int s, int j){
    if((s - j) % 2 == 1){
        return -1;
    }

    return j + ((s - j) / 2);
}

signed main(){

    comb[0][0] = 1;
    for(int i = 1; i <= NMAX; i++){
        comb[i][0] = 1;
        for(int j = 1; j <= NMAX; j++){
            comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % MOD;
        }
    }

    int n, m;
    cin >> n >> m;

    n *= 2;
    for(int i = 1; i <= m; i++){
        for(int j = i; j <= n; j += m){
            sz[i]++;
        }
        s[i] = s[i - 1] + sz[i];
    }
    n /= 2;

    dp[1][sz[1]] = C(n, sz[1]);
    for(int i = 1; i <= m - 1; i++){
        for(int j = 0; j <= n; j++){
            for(int k = 0; k <= min(j, sz[i + 1]); k++){
                int newJ = j - k + (sz[i + 1] - k);
                if(newJ > n){
                    continue;
                }

                int r = n - f(s[i] + k, j - k);
                if(r == -1){
                    continue;
                }
                (dp[i + 1][newJ] += ((dp[i][j] * C(j, k)) % MOD * C(r, sz[i + 1] - k)) % MOD) %= MOD;
            }
        }
    }
    
    int ans = dp[m][0];

    fact[0] = 1;
    for(int i = 1; i <= 2 * n; i++){
        (fact[i] = fact[i - 1] * i) %= MOD;
    }

    int pw = 1;
    for(int i = 1; i <= n; i++){
        (pw *= 2) %= MOD;
    }

    ans = (ans * pw) % MOD;

    for(int i = 1; i <= m; i++){
        (ans *= fact[sz[i]]) %= MOD;
    }

    cout << ans <<'\n';

    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 18 / 18
• Subtask 5: 48 / 48