oj.uz

Submission #598577

# Submission time Handle Problem Language Result Execution time Memory
598577 2022-07-18T14:21:56 Z CaroLinda NoM (RMI21_nom) C++14
100 / 100
 229 ms 204868 KB 
#include <bits/stdc++.h>

#define ll long long

const ll MOD = 1e9+7LL;
const int MAX = 4010;

using namespace std;

int N, M;
int qtdMod[MAX], moduloHere[MAX];
ll dp[MAX][MAX][2]; //flag pra falar se devo escolher livres ou duplas
ll bin[MAX][MAX];
ll fat[MAX], pot[MAX];

void calcBin(){
    bin[0][0] = 1;

    for(int i = 1; i <= 2*N; i++){
        bin[i][0]=1;

        for(int j = 1; j <= 2*N; j++){
            bin[i][j] = (bin[i-1][j]+bin[i-1][j-1]);
            if(bin[i][j] >= MOD)
                bin[i][j] -= MOD;
        }
    }
}

void calcFat(){
    fat[0] = 1;
    for(int i = 1; i <= 2*N; i++)
        fat[i] = (fat[i-1] * i) % MOD;
}

void calcPot(){
    pot[0] = 1;
    for(int i = 1; i <= 2*N; i++)
        pot[i] = (pot[i-1] << 1LL) % MOD;
}

int getQuantity(int x){
    return qtdMod[moduloHere[x]%M]-x;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M;

    calcBin();
    calcFat();
    calcPot();

    for(int i = 0; i < 2*N; i++)
        qtdMod[i%M]++;

    int ant = 0;
    for(int i = 0; i < M; i++){
        for(int q = qtdMod[i]; q > 0; q--,ant++ )
            moduloHere[ant] = i;
    }

    for(int i = 1; i < M; i++)
        qtdMod[i] += qtdMod[i-1];

    dp[2*N][0][0] = dp[2*N][0][1] = 1;

    for(int i = 2*N-1; i >= 0; i--)
        for(int j = 0; j <= min(i,N); j++){
            int foram = ((i-j)>>1)+j;

            if(foram > N)
                continue;

            int faltam = N-foram;
            int qtdModLeft = getQuantity(i);

            if(faltam >= qtdModLeft){
                ll jeito = (bin[faltam][qtdModLeft] * fat[qtdModLeft] ) % MOD;
                jeito *= pot[qtdModLeft];
                jeito %= MOD;

                ll qMod = qtdMod[moduloHere[i]]-(moduloHere[i] == 0 ? 0 : qtdMod[moduloHere[i]-1]);
                qMod = bin[qMod][qtdModLeft];

                (jeito *= qMod) %= MOD;

                dp[i][j][1] = jeito  * dp[qtdMod[moduloHere[i]]][j+qtdModLeft][0];
                dp[i][j][1] %= MOD;
            }


            dp[i][j][0] = dp[i][j][1];

            if(j){
                dp[i][j][0] += ( dp[i+1][j-1][0] * j ) % MOD;
                if(dp[i][j][0] >= MOD)
                    dp[i][j][0] -= MOD;
            }
        }

    cout << dp[0][0][0] << "\n";
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 2 ms 2388 KB Output is correct
12 Correct 1 ms 1620 KB Output is correct
13 Correct 1 ms 1620 KB Output is correct
14 Correct 1 ms 1620 KB Output is correct
15 Correct 1 ms 1656 KB Output is correct
16 Correct 1 ms 2004 KB Output is correct
17 Correct 1 ms 1492 KB Output is correct
18 Correct 1 ms 1620 KB Output is correct
19 Correct 2 ms 2004 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 2 ms 2388 KB Output is correct
12 Correct 1 ms 1620 KB Output is correct
13 Correct 1 ms 1620 KB Output is correct
14 Correct 1 ms 1620 KB Output is correct
15 Correct 1 ms 1656 KB Output is correct
16 Correct 1 ms 2004 KB Output is correct
17 Correct 1 ms 1492 KB Output is correct
18 Correct 1 ms 1620 KB Output is correct
19 Correct 2 ms 2004 KB Output is correct
20 Correct 3 ms 4180 KB Output is correct
21 Correct 2 ms 3924 KB Output is correct
22 Correct 5 ms 8020 KB Output is correct
23 Correct 6 ms 6868 KB Output is correct
24 Correct 6 ms 9172 KB Output is correct
25 Correct 5 ms 7508 KB Output is correct
26 Correct 5 ms 7636 KB Output is correct
27 Correct 6 ms 9428 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 2 ms 2388 KB Output is correct
12 Correct 1 ms 1620 KB Output is correct
13 Correct 1 ms 1620 KB Output is correct
14 Correct 1 ms 1620 KB Output is correct
15 Correct 1 ms 1656 KB Output is correct
16 Correct 1 ms 2004 KB Output is correct
17 Correct 1 ms 1492 KB Output is correct
18 Correct 1 ms 1620 KB Output is correct
19 Correct 2 ms 2004 KB Output is correct
20 Correct 3 ms 4180 KB Output is correct
21 Correct 2 ms 3924 KB Output is correct
22 Correct 5 ms 8020 KB Output is correct
23 Correct 6 ms 6868 KB Output is correct
24 Correct 6 ms 9172 KB Output is correct
25 Correct 5 ms 7508 KB Output is correct
26 Correct 5 ms 7636 KB Output is correct
27 Correct 6 ms 9428 KB Output is correct
28 Correct 22 ms 28764 KB Output is correct
29 Correct 25 ms 31168 KB Output is correct
30 Correct 26 ms 30420 KB Output is correct
31 Correct 27 ms 29700 KB Output is correct
32 Correct 33 ms 33472 KB Output is correct
33 Correct 36 ms 35712 KB Output is correct
34 Correct 43 ms 53016 KB Output is correct

Subtask #5
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 2 ms 2388 KB Output is correct
12 Correct 1 ms 1620 KB Output is correct
13 Correct 1 ms 1620 KB Output is correct
14 Correct 1 ms 1620 KB Output is correct
15 Correct 1 ms 1656 KB Output is correct
16 Correct 1 ms 2004 KB Output is correct
17 Correct 1 ms 1492 KB Output is correct
18 Correct 1 ms 1620 KB Output is correct
19 Correct 2 ms 2004 KB Output is correct
20 Correct 3 ms 4180 KB Output is correct
21 Correct 2 ms 3924 KB Output is correct
22 Correct 5 ms 8020 KB Output is correct
23 Correct 6 ms 6868 KB Output is correct
24 Correct 6 ms 9172 KB Output is correct
25 Correct 5 ms 7508 KB Output is correct
26 Correct 5 ms 7636 KB Output is correct
27 Correct 6 ms 9428 KB Output is correct
28 Correct 22 ms 28764 KB Output is correct
29 Correct 25 ms 31168 KB Output is correct
30 Correct 26 ms 30420 KB Output is correct
31 Correct 27 ms 29700 KB Output is correct
32 Correct 33 ms 33472 KB Output is correct
33 Correct 36 ms 35712 KB Output is correct
34 Correct 43 ms 53016 KB Output is correct
35 Correct 130 ms 150552 KB Output is correct
36 Correct 157 ms 176164 KB Output is correct
37 Correct 140 ms 147064 KB Output is correct
38 Correct 141 ms 155172 KB Output is correct
39 Correct 141 ms 143036 KB Output is correct
40 Correct 229 ms 204868 KB Output is correct