oj.uz

Submission #857045

# Submission time Handle Problem Language Result Execution time Memory
857045 2023-10-05T10:12:36 Z lolismek NoM (RMI21_nom) C++14
0 / 100
 9 ms 33412 KB 
#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 comb[NMAX + 1][NMAX + 1];

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

    return comb[n][k];
}

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;

    for(int i = 1; i <= m; i++){
        sz[i] = n / m;
        if(sz[i] <= n % m){
            sz[i]++;
        }
    }

    dp[1][sz[1]] = C(n, sz[1]);
    int sum = sz[1];

    for(int i = 2; i <= m; i++){
        sum += sz[i];
        for(int j = 0; j <= n; j++){
            for(int nw = 0; nw <= sz[i]; nw++){
                int r = (sum - j) / 2;
                if(r * 2 != sum - j){
                    continue;
                }   

                if(j - 2 * nw + sz[i] >= 0 && j - 2 * nw + sz[i] <= n){
                    (dp[i][j] += (((((dp[i - 1][j - 2 * nw + sz[i]] * C(sz[i], nw)) % MOD) * C(n - r, nw)) % MOD) * C(j - 2 * nw + sz[i], sz[i] - nw)) % MOD) %= MOD;
                }
            }
        }
    }
    
    int ans = dp[m][0];

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

    cout << (((ans * pw) % MOD) * fact) % MOD <<'\n';

    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 33372 KB Output is correct
2 Correct 9 ms 33412 KB Output is correct
3 Correct 9 ms 33372 KB Output is correct
4 Correct 9 ms 33372 KB Output is correct
5 Incorrect 9 ms 33372 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 33372 KB Output is correct
2 Correct 9 ms 33412 KB Output is correct
3 Correct 9 ms 33372 KB Output is correct
4 Correct 9 ms 33372 KB Output is correct
5 Incorrect 9 ms 33372 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 33372 KB Output is correct
2 Correct 9 ms 33412 KB Output is correct
3 Correct 9 ms 33372 KB Output is correct
4 Correct 9 ms 33372 KB Output is correct
5 Incorrect 9 ms 33372 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 33372 KB Output is correct
2 Correct 9 ms 33412 KB Output is correct
3 Correct 9 ms 33372 KB Output is correct
4 Correct 9 ms 33372 KB Output is correct
5 Incorrect 9 ms 33372 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 33372 KB Output is correct
2 Correct 9 ms 33412 KB Output is correct
3 Correct 9 ms 33372 KB Output is correct
4 Correct 9 ms 33372 KB Output is correct
5 Incorrect 9 ms 33372 KB Output isn't correct
6 Halted 0 ms 0 KB -