QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#769910#9254. Random VariablesforgotmyhandleWA 3ms12924kbC++141.1kb2024-11-21 19:52:022024-11-21 19:52:03

Judging History

This is the latest submission verdict.

  • [2024-11-21 19:52:03]
  • Judged
  • Verdict: WA
  • Time: 3ms
  • Memory: 12924kb
Show
  • [2024-11-21 19:52:02]
  • Submitted

answer

#include <iostream>
#define int long long
using namespace std;
int tc, P;
int dp[1005][1005], C[1005][1005];
int cnt[1005];
signed main() {
    cin >> tc >> P;
    for (int i = C[0][0] = 1; i <= 1000; i++) {
        for (int j = C[i][0] = 1; j <= i; j++) 
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;
    }
    while (tc--) {
        int n, m;
        cin >> n >> m;
        for (int k = 1; k <= n; k++) {
            int lim = n / k;
            for (int i = 0; i <= lim; i++) dp[0][i] = 1;
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j <= lim; j++) {
                    dp[i][j] = dp[i - 1][j] * (m - j) % P;
                    if (i > k) 
                        dp[i][j] = (dp[i][j] - dp[i - k - 1][j + 1] * C[i - 1][k] % P * (m - j) % P + P) % P;
                }
            }
            cnt[k] = dp[n][0];
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) ans += (cnt[i] - cnt[i - 1]) * i % P;
        cout << ans % P << "\n";
    }
    return 0;
}
/*
3 123456789
3 2
5 5
7 7
*/
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 12924kb

input:

3 123456789
3 2
5 5
7 7

output:

18
7145
2066323

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 3ms
memory: 12856kb

input:

100 2
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
4 1
4 2
4 3
4 4
4 5
4 6
4 7
4 8
4 9
4 10
5 1
5 2
5 3
5 4
5 5
5 6
5 7
5 8
5 9
5 10
6 1
6 2
6 3
6 4
6 5
6 6
6 7
6 8
6 9
6 10
7 1
7 2
7 3
7 4
7 5
7 6
7 7
7 8
7 9
7 10
8 1
8 2...

output:

1
0
1
0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0

result:

ok 100 lines

Test #3:

score: -100
Wrong Answer
time: 3ms
memory: 12248kb

input:

100 3
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
4 1
4 2
4 3
4 4
4 5
4 6
4 7
4 8
4 9
4 10
5 1
5 2
5 3
5 4
5 5
5 6
5 7
5 8
5 9
5 10
6 1
6 2
6 3
6 4
6 5
6 6
6 7
6 8
6 9
6 10
7 1
7 2
7 3
7 4
7 5
7 6
7 7
7 8
7 9
7 10
8 1
8 2...

output:

1
2
0
1
2
0
1
2
0
1
2
0
0
2
0
0
2
0
0
2
0
0
0
0
0
0
0
0
0
0
1
-1
0
1
-1
0
1
-1
0
1
2
-1
0
2
-1
0
2
-1
0
2
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
1
0
0
1
2
2
0
2
2
0
2
2
0
2
0
0
0
0
0
0
0
0
0
0
1
-1
0
1
-1
0
1
-1
0
1

result:

wrong answer 32nd lines differ - expected: '2', found: '-1'
English 繁體中文 简体中文

Server Time: 2025-03-06 00:15:15 | OpenSource Project