Submission #540497

#	Time	Username	Problem	Language	Result	Execution time	Memory
540497		doowey	NoM (RMI21_nom)	C++14	100 / 100	95 ms	57740 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 2005;
const int M = N * 2;
const int MOD = (int)1e9 + 7;

int mult(int x, int y){
    return (x * 1ll * y) % MOD;
}

void add(int &u, int v){
    u = (u + v) % MOD;
}

int pick[M][M];
int cnt[M];
int fac[M];
int dp[N][N];

int main(){
    fastIO;
    int n, m;
    cin >> n >> m;
    for(int i = 0 ; i < n * 2; i ++ ){
        cnt[i % m] ++ ;
    }
    for(int i = 0 ; i < M; i ++ ){
        pick[i][0]=1;
    }
    for(int i = 1; i < M; i ++ ){
        for(int j = 1; j <= i; j ++ ){
            add(pick[i][j], pick[i-1][j]);
            add(pick[i][j], pick[i-1][j-1]);
        }
    }
    fac[0] = 1;
    for(int i = 1; i < M; i ++ ){
        fac[i] = mult(fac[i - 1], i);
    }
    dp[0][0] = mult(pick[n][cnt[0]], fac[cnt[0]]);
    int total = 0;
    int single;
    int value;
    for(int i = 1; i < m ; i ++ ){
        total += cnt[i - 1];
        for(int j = 0 ; j <= n; j ++ ){
            if(dp[i-1][j] == 0) continue;
            for(int nx = 0; nx <= cnt[i]; nx ++ ){
                single = total - 2ll * j;
                if(single < 0) continue;
                if(nx > single) continue;
                if(single + j > n) continue;
                if(j + nx > n) continue;
                value = dp[i - 1][j];
                value = mult(value, pick[single][nx]);
                value = mult(value, pick[n - single - j][cnt[i] - nx]);
                value = mult(value, fac[cnt[i]]);
                add(dp[i][j + nx], value);
            }
        }
    }
    int sol = dp[m-1][n];
    for(int i = 1; i <= n; i ++ ){
        sol = mult(sol, 2);
    }
    cout << sol << "\n";

    return 0;
}

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