Submission #857770

#	Time	Username	Problem	Language	Result	Execution time	Memory
857770		divad	NoM (RMI21_nom)	C++14	100 / 100	73 ms	63320 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9+7;
const int NMAX = 2e3+2;
int n,m,cnt[NMAX];
/// dp[i][j] = cate imperecheri pot obtine cu primele i resturi si sa ramana j neimperecheata

struct Mint{
    int val;
    Mint(){
        val = 0;
    }
    Mint(int _val){
        val = _val%MOD;
    }
    Mint operator * (Mint oth) {
        return (val * oth.val);
    }
    Mint operator * (int oth) {
        oth %= MOD;
        return (val * oth);
    }
    Mint operator + (Mint oth) {
        return (val + oth.val);
    }
    Mint operator - (Mint oth) {
        return (val + MOD - oth.val);
    }
    Mint operator = (int oth){
        val = oth;
        val %= MOD;
        return *this;
    }
    Mint operator += (Mint oth){
        val += oth.val;
        val %= MOD;
        return *this;
    }
} fact[2*NMAX], inv[2*NMAX], dp[NMAX][2*NMAX];

Mint lgput(int n, int a){
    if(a == 0){
        return 1ll;
    }else{
        if(a%2 == 0){
            Mint val = lgput(n, a/2);
            return val*val;
        }else{
            return lgput(n, a-1)*n;
        }
    }
}

Mint comb(int n, int m){
    return fact[n]*inv[n-m]*inv[m];
}

Mint aranj(int n, int m){
    return fact[n]*inv[n-m];
}

signed main()
{
    /// 257 15
    fact[0] = 1;
    for(int i = 1; i < NMAX*2; i++){
        fact[i] = fact[i-1]*i;
    }
    inv[NMAX*2-1] = lgput(fact[NMAX*2-1].val, MOD-2);
    for(int i = NMAX*2-2; i >= 0; i--){
        inv[i] = inv[i+1]*(i+1);
    }
    cin >> n >> m;
    for(int i = 1; i <= 2*n; i++){
        cnt[i%m]++;
    }
    dp[0][cnt[0]] = 1;
    int maxi = cnt[0];
    for(int i = 1; i < m; i++){
        for(int k = 0; k <= cnt[i]; k++){
            for(int j = k; j <= maxi; j++){
                /// (i-1, j) -> (i, j-k+(cnt[i]-k))
                dp[i][j-k+(cnt[i]-k)] += dp[i-1][j]*comb(cnt[i], k)*aranj(j, k);
            }
        }
        maxi += cnt[i];
    }
    dp[m-1][0] = dp[m-1][0]*fact[n];
    dp[m-1][0] = dp[m-1][0]*lgput(2, n);
    cout << dp[m-1][0].val;
    return 0;
}

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