QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#32665 | #2573. Two Permutations | YaoBIG# | AC ✓ | 51ms | 10708kb | C++20 | 1.8kb | 2022-05-22 22:13:24 | 2022-05-22 22:13:25 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = (int)1e9 + 7;
void mInc(int& a, int b) {
a += b;
if (a >= MOD) a -= MOD;
}
const int N = 100;
const int K = N * N;
int dp[2][N][K + 1];
// DP[n][m][s]: Ways to have a permutation of length n, where we ignore m positions, and have sum s
int solve(int max_n, int tar_k) {
dp[0][0][0] = 1;
for (int n = 0; n < max_n; ++n) {
int c = n & 1;
int t = c ^ 1;
for (int m = 0; m <= n; ++m) {
for (int s = 0; s <= n*n; ++s) {
ll v0 = dp[c][m][s];
if (v0 == 0) continue;
// cerr << n << ' ' << m << ' ' << s << ": " << v0 << '\n';
ll v1 = v0 * m % MOD;
int add = n + 1;
mInc(dp[t][m + 1][s], v0); // n at last position, ignore last position
mInc(dp[t][m][s + add], v0); // n at last position, DO NOT ignore last position
mInc(dp[t][m][s + add], v1); // n NOT at last position, ignore last position, n hits a non-ignoring position
if (m > 0) mInc(dp[t][m - 1][s + 2*add], v1); // n NOT at last position, DO NOT ignore last position, n hits a non-ignoring position
mInc(dp[t][m + 1][s], v1); // n NOT at last position, ignore last position, n hits a ignoring position
mInc(dp[t][m][s + add], v1); // n NOT at last position, DO NOT ignore last position, n hits a ignoring position
dp[c][m][s] = 0;
}
}
}
/*
for (int m = 0; m <= max_n; ++m) {
for (int s = 0; s <= max_n*max_n; ++s) {
ll v0 = dp[max_n & 1][m][s];
if (v0 == 0) continue;
cerr << max_n << ' ' << m << ' ' << s - K << ": " << v0 << '\n';
}
}
*/
return dp[max_n & 1][0][tar_k];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
ll res = solve(n, k);
for (int i = 1; i <= n; ++i) res = (res * i) % MOD;
cout << res << '\n';
}
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 5672kb
input:
2 4
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5604kb
input:
3 7
output:
12
result:
ok 1 number(s): "12"
Test #3:
score: 0
Accepted
time: 0ms
memory: 7664kb
input:
4 10
output:
24
result:
ok 1 number(s): "24"
Test #4:
score: 0
Accepted
time: 3ms
memory: 5616kb
input:
4 14
output:
96
result:
ok 1 number(s): "96"
Test #5:
score: 0
Accepted
time: 1ms
memory: 5608kb
input:
5 10
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 3ms
memory: 5676kb
input:
5 15
output:
120
result:
ok 1 number(s): "120"
Test #7:
score: 0
Accepted
time: 3ms
memory: 5600kb
input:
5 21
output:
2400
result:
ok 1 number(s): "2400"
Test #8:
score: 0
Accepted
time: 1ms
memory: 5632kb
input:
6 21
output:
720
result:
ok 1 number(s): "720"
Test #9:
score: 0
Accepted
time: 2ms
memory: 5620kb
input:
6 30
output:
25920
result:
ok 1 number(s): "25920"
Test #10:
score: 0
Accepted
time: 2ms
memory: 5512kb
input:
6 27
output:
106560
result:
ok 1 number(s): "106560"
Test #11:
score: 0
Accepted
time: 0ms
memory: 7728kb
input:
20 300
output:
644873710
result:
ok 1 number(s): "644873710"
Test #12:
score: 0
Accepted
time: 3ms
memory: 5708kb
input:
20 139
output:
0
result:
ok 1 number(s): "0"
Test #13:
score: 0
Accepted
time: 3ms
memory: 5772kb
input:
30 470
output:
491424690
result:
ok 1 number(s): "491424690"
Test #14:
score: 0
Accepted
time: 1ms
memory: 5832kb
input:
30 500
output:
8436035
result:
ok 1 number(s): "8436035"
Test #15:
score: 0
Accepted
time: 1ms
memory: 7928kb
input:
40 1000
output:
617159088
result:
ok 1 number(s): "617159088"
Test #16:
score: 0
Accepted
time: 5ms
memory: 9720kb
input:
40 900
output:
729805907
result:
ok 1 number(s): "729805907"
Test #17:
score: 0
Accepted
time: 7ms
memory: 10152kb
input:
60 1830
output:
16340084
result:
ok 1 number(s): "16340084"
Test #18:
score: 0
Accepted
time: 11ms
memory: 9964kb
input:
60 2000
output:
832198921
result:
ok 1 number(s): "832198921"
Test #19:
score: 0
Accepted
time: 51ms
memory: 10328kb
input:
100 5050
output:
437918130
result:
ok 1 number(s): "437918130"
Test #20:
score: 0
Accepted
time: 50ms
memory: 10708kb
input:
100 700
output:
0
result:
ok 1 number(s): "0"
Test #21:
score: 0
Accepted
time: 51ms
memory: 10412kb
input:
100 10000
output:
0
result:
ok 1 number(s): "0"