oj.uz

Submission #857752

# Submission time Handle Problem Language Result Execution time Memory
857752 2023-10-06T20:49:21 Z divad NoM (RMI21_nom) C++14
9 / 100
 9 ms 63248 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

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) {
        return (val * oth);
    }
    Mint operator + (Mint oth) {
        return (val + oth.val);
    }
    Mint operator - (Mint oth) {
        return (val - oth.val + MOD);
    }
    Mint operator = (int oth){
        val = oth;
        return *this;
    }
    Mint operator += (Mint oth){
        val += oth.val;
        return *this;
    }
} fact[2*NMAX], inv[2*NMAX], dp[NMAX][2*NMAX];

Mint lgput(int n, int a){
    if(a == 0){
        return 1;
    }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];
}

signed main()
{
    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 sum = 0;
    for(int i = 1; i < m; i++){
        for(int k = 0; k <= cnt[i]; k++){
            for(int j = k; j <= n; j++){
                /// (i-1, j) -> (i, j-k+(cnt[i]-k))
                dp[i][j-k+(cnt[i]-k)] += dp[i-1][j]*fact[k]*comb(cnt[i], k)*comb(j, k);
            }
        }
    }
    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;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:71:9: warning: unused variable 'sum' [-Wunused-variable]
   71 |     int sum = 0;
      |         ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 63064 KB Output is correct
2 Correct 8 ms 63248 KB Output is correct
3 Correct 8 ms 63068 KB Output is correct
4 Correct 7 ms 63064 KB Output is correct
5 Correct 8 ms 63064 KB Output is correct
6 Correct 8 ms 63068 KB Output is correct
7 Correct 7 ms 63068 KB Output is correct
8 Correct 7 ms 63196 KB Output is correct
9 Correct 9 ms 63224 KB Output is correct
10 Correct 8 ms 63068 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 63064 KB Output is correct
2 Correct 8 ms 63248 KB Output is correct
3 Correct 8 ms 63068 KB Output is correct
4 Correct 7 ms 63064 KB Output is correct
5 Correct 8 ms 63064 KB Output is correct
6 Correct 8 ms 63068 KB Output is correct
7 Correct 7 ms 63068 KB Output is correct
8 Correct 7 ms 63196 KB Output is correct
9 Correct 9 ms 63224 KB Output is correct
10 Correct 8 ms 63068 KB Output is correct
11 Correct 8 ms 63064 KB Output is correct
12 Correct 7 ms 63068 KB Output is correct
13 Incorrect 7 ms 63068 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 63064 KB Output is correct
2 Correct 8 ms 63248 KB Output is correct
3 Correct 8 ms 63068 KB Output is correct
4 Correct 7 ms 63064 KB Output is correct
5 Correct 8 ms 63064 KB Output is correct
6 Correct 8 ms 63068 KB Output is correct
7 Correct 7 ms 63068 KB Output is correct
8 Correct 7 ms 63196 KB Output is correct
9 Correct 9 ms 63224 KB Output is correct
10 Correct 8 ms 63068 KB Output is correct
11 Correct 8 ms 63064 KB Output is correct
12 Correct 7 ms 63068 KB Output is correct
13 Incorrect 7 ms 63068 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 63064 KB Output is correct
2 Correct 8 ms 63248 KB Output is correct
3 Correct 8 ms 63068 KB Output is correct
4 Correct 7 ms 63064 KB Output is correct
5 Correct 8 ms 63064 KB Output is correct
6 Correct 8 ms 63068 KB Output is correct
7 Correct 7 ms 63068 KB Output is correct
8 Correct 7 ms 63196 KB Output is correct
9 Correct 9 ms 63224 KB Output is correct
10 Correct 8 ms 63068 KB Output is correct
11 Correct 8 ms 63064 KB Output is correct
12 Correct 7 ms 63068 KB Output is correct
13 Incorrect 7 ms 63068 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 63064 KB Output is correct
2 Correct 8 ms 63248 KB Output is correct
3 Correct 8 ms 63068 KB Output is correct
4 Correct 7 ms 63064 KB Output is correct
5 Correct 8 ms 63064 KB Output is correct
6 Correct 8 ms 63068 KB Output is correct
7 Correct 7 ms 63068 KB Output is correct
8 Correct 7 ms 63196 KB Output is correct
9 Correct 9 ms 63224 KB Output is correct
10 Correct 8 ms 63068 KB Output is correct
11 Correct 8 ms 63064 KB Output is correct
12 Correct 7 ms 63068 KB Output is correct
13 Incorrect 7 ms 63068 KB Output isn't correct
14 Halted 0 ms 0 KB -