QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#72710 | #2573. Two Permutations | CSU2023# | AC ✓ | 44ms | 11508kb | C++14 | 1.5kb | 2023-01-18 10:20:43 | 2023-01-18 10:20:46 |
Judging History
answer
#include <bits/stdc++.h>
template <class T>
inline void read(T &res)
{
char ch; bool flag = false; res = 0;
while (ch = getchar(), !isdigit(ch) && ch != '-');
ch == '-' ? flag = true : res = ch ^ 48;
while (ch = getchar(), isdigit(ch))
res = res * 10 + ch - 48;
}
template <class T>
inline void put(T x)
{
if (x > 9) put(x / 10);
putchar(x % 10 + 48);
}
const int N = 105;
const int N2 = 1e4 + 5;
const int mod = 1e9 + 7;
const int inv2 = (mod + 1) >> 1;
int n, K, f[2][N2][N];
template <class T>
inline T Min(T x, T y) {return x < y ? x : y;}
inline void add(int &x, int y)
{
x += y;
x >= mod ? x -= mod : 0;
}
int main()
{
read(n); read(K);
f[0][0][0] = 1;
for (int i = 1; i <= n; ++i)
{
int now = i & 1, lst = now ^ 1;
for (int k = 0, km = Min(i * (i + 1), K); k <= km; ++k)
for (int t = 0; t <= i; ++t)
f[now][k][t] = 0;
for (int k = 0, km = Min(i * (i - 1), K); k <= km; ++k)
for (int t = 0; t < i; ++t)
if (f[lst][k][t])
{
int cur = f[lst][k][t], a1 = (i - 1 - t), a2 = (i - 1 - t), b = n - t - a1 - a2;
int &tmp1 = f[now][k + (i << 1)][t + 2];
tmp1 = (1ll * a1 * a2 * cur + tmp1) % mod;
int &tmp2 = f[now][k + i][t + 1];
tmp2 = (1ll * cur * (a1 + a2) * b + tmp2) % mod;
int &tmp3 = f[now][k][t];
tmp3 = (1ll * b * (b - 1) * cur + tmp3) % mod;
int &tmp4 = f[now][k + i][t + 1];
tmp4 = (1ll * cur * b + tmp4) % mod;
}
}
put(f[n & 1][K][n]), putchar('\n');
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5476kb
input:
2 4
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 2ms
memory: 5428kb
input:
3 7
output:
12
result:
ok 1 number(s): "12"
Test #3:
score: 0
Accepted
time: 2ms
memory: 5540kb
input:
4 10
output:
24
result:
ok 1 number(s): "24"
Test #4:
score: 0
Accepted
time: 2ms
memory: 5400kb
input:
4 14
output:
96
result:
ok 1 number(s): "96"
Test #5:
score: 0
Accepted
time: 2ms
memory: 5480kb
input:
5 10
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 0ms
memory: 5516kb
input:
5 15
output:
120
result:
ok 1 number(s): "120"
Test #7:
score: 0
Accepted
time: 2ms
memory: 5396kb
input:
5 21
output:
2400
result:
ok 1 number(s): "2400"
Test #8:
score: 0
Accepted
time: 2ms
memory: 5384kb
input:
6 21
output:
720
result:
ok 1 number(s): "720"
Test #9:
score: 0
Accepted
time: 2ms
memory: 5448kb
input:
6 30
output:
25920
result:
ok 1 number(s): "25920"
Test #10:
score: 0
Accepted
time: 1ms
memory: 5524kb
input:
6 27
output:
106560
result:
ok 1 number(s): "106560"
Test #11:
score: 0
Accepted
time: 2ms
memory: 5520kb
input:
20 300
output:
644873710
result:
ok 1 number(s): "644873710"
Test #12:
score: 0
Accepted
time: 3ms
memory: 5496kb
input:
20 139
output:
0
result:
ok 1 number(s): "0"
Test #13:
score: 0
Accepted
time: 1ms
memory: 9660kb
input:
30 470
output:
491424690
result:
ok 1 number(s): "491424690"
Test #14:
score: 0
Accepted
time: 0ms
memory: 5612kb
input:
30 500
output:
8436035
result:
ok 1 number(s): "8436035"
Test #15:
score: 0
Accepted
time: 1ms
memory: 5804kb
input:
40 1000
output:
617159088
result:
ok 1 number(s): "617159088"
Test #16:
score: 0
Accepted
time: 1ms
memory: 5784kb
input:
40 900
output:
729805907
result:
ok 1 number(s): "729805907"
Test #17:
score: 0
Accepted
time: 5ms
memory: 9564kb
input:
60 1830
output:
16340084
result:
ok 1 number(s): "16340084"
Test #18:
score: 0
Accepted
time: 5ms
memory: 6264kb
input:
60 2000
output:
832198921
result:
ok 1 number(s): "832198921"
Test #19:
score: 0
Accepted
time: 33ms
memory: 11388kb
input:
100 5050
output:
437918130
result:
ok 1 number(s): "437918130"
Test #20:
score: 0
Accepted
time: 3ms
memory: 5816kb
input:
100 700
output:
0
result:
ok 1 number(s): "0"
Test #21:
score: 0
Accepted
time: 44ms
memory: 11508kb
input:
100 10000
output:
0
result:
ok 1 number(s): "0"