oj.uz

Submission #857769

# Submission time Handle Problem Language Result Execution time Memory
857769 2023-10-06T22:10:51 Z divad NoM (RMI21_nom) C++14
0 / 100
 59 ms 127792 KB 
#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

ifstream fin("num.in");
ofstream fout("num.out");

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);
    }
    fin >> 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);
    fout << dp[m-1][0].val;
    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 127792 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 127792 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 127792 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 127792 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 48.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 127792 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -