QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #839817 | #8728. Tablica | HuTao | 100 ✓ | 39ms | 155308kb | C++14 | 1.3kb | 2025-01-02 10:12:21 | 2025-01-02 10:12:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3005, P = 1e9 + 7;
int n, m;
LL c[N][N], fact[N], p2[N];
LL f[N][N * 2];
int main()
{
scanf("%d%d", &n, &m);
if(n < m) swap(n, m);
for(int i = 0; i <= n; i ++ )
{
c[i][0] = 1;
for(int j = 1; j <= i; j ++ )
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % P;
}
fact[0] = 1;
for(int i = 1; i <= n; i ++ ) fact[i] = fact[i - 1] * i % P;
p2[0] = 1;
for(int i = 1; i <= n; i ++ ) p2[i] = p2[i - 1] * (P + 1) / 2 % P;
f[0][0] = 1;
for(int i = 1; i <= m; i ++ )
for(int j = i; j <= i * 2; j ++ )
f[i][j] = (f[i - 1][j - 1] * j + (j >= 2 ? f[i - 1][j - 2] * j * (j - 1) / 2 : 0)) % P;
LL res = 0;
for(int i = 0; i <= m; i ++ )
{
LL s = 0;
for(int j = 0; j <= n - i; j ++ )
{
s = (s + (i & 1 ? P - p2[i + j] : p2[i + j]) * c[n - i][j] % P * f[m - i][n - i + j]) % P;
// printf("#%d %d %lld\n", i, j, c[n][i] % P * c[m][i] % P * c[n - i][j] % P * f[m - i][n - i + j] % P);
}
res = (res + s * c[n][i] % P * c[m][i] % P * fact[i]) % P;
}
printf("%lld\n", res);
return 0;
}
詳細信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 1ms
memory: 5808kb
input:
5 6
output:
456750
result:
ok 1 number(s): "456750"
Test #2:
score: 10
Accepted
time: 1ms
memory: 5888kb
input:
6 6
output:
5464710
result:
ok 1 number(s): "5464710"
Test #3:
score: 10
Accepted
time: 1ms
memory: 5800kb
input:
3 5
output:
270
result:
ok 1 number(s): "270"
Test #4:
score: 10
Accepted
time: 1ms
memory: 5808kb
input:
3 6
output:
90
result:
ok 1 number(s): "90"
Test #5:
score: 10
Accepted
time: 1ms
memory: 8044kb
input:
4 6
output:
14580
result:
ok 1 number(s): "14580"
Test #6:
score: 10
Accepted
time: 1ms
memory: 5880kb
input:
3 4
output:
270
result:
ok 1 number(s): "270"
Subtask #2:
score: 18
Accepted
Dependency #1:
100%
Accepted
Test #7:
score: 18
Accepted
time: 2ms
memory: 9996kb
input:
50 49
output:
750700714
result:
ok 1 number(s): "750700714"
Test #8:
score: 18
Accepted
time: 2ms
memory: 8136kb
input:
50 50
output:
630532893
result:
ok 1 number(s): "630532893"
Test #9:
score: 18
Accepted
time: 2ms
memory: 10052kb
input:
41 34
output:
800856205
result:
ok 1 number(s): "800856205"
Test #10:
score: 18
Accepted
time: 0ms
memory: 8084kb
input:
39 41
output:
541550932
result:
ok 1 number(s): "541550932"
Test #11:
score: 18
Accepted
time: 0ms
memory: 10076kb
input:
38 46
output:
651393374
result:
ok 1 number(s): "651393374"
Test #12:
score: 18
Accepted
time: 2ms
memory: 9952kb
input:
37 39
output:
746919932
result:
ok 1 number(s): "746919932"
Test #13:
score: 18
Accepted
time: 0ms
memory: 10016kb
input:
30 50
output:
214086425
result:
ok 1 number(s): "214086425"
Test #14:
score: 18
Accepted
time: 2ms
memory: 9980kb
input:
50 41
output:
193351204
result:
ok 1 number(s): "193351204"
Test #15:
score: 18
Accepted
time: 0ms
memory: 9972kb
input:
44 32
output:
63855946
result:
ok 1 number(s): "63855946"
Test #16:
score: 18
Accepted
time: 1ms
memory: 8080kb
input:
45 42
output:
266239299
result:
ok 1 number(s): "266239299"
Subtask #3:
score: 31
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #17:
score: 31
Accepted
time: 0ms
memory: 22396kb
input:
199 200
output:
841552647
result:
ok 1 number(s): "841552647"
Test #18:
score: 31
Accepted
time: 0ms
memory: 22188kb
input:
200 200
output:
157842226
result:
ok 1 number(s): "157842226"
Test #19:
score: 31
Accepted
time: 3ms
memory: 18456kb
input:
156 199
output:
216453917
result:
ok 1 number(s): "216453917"
Test #20:
score: 31
Accepted
time: 0ms
memory: 18236kb
input:
161 199
output:
539960909
result:
ok 1 number(s): "539960909"
Test #21:
score: 31
Accepted
time: 3ms
memory: 16240kb
input:
194 160
output:
764024671
result:
ok 1 number(s): "764024671"
Test #22:
score: 31
Accepted
time: 0ms
memory: 18188kb
input:
184 195
output:
117763744
result:
ok 1 number(s): "117763744"
Test #23:
score: 31
Accepted
time: 0ms
memory: 18204kb
input:
152 174
output:
350941677
result:
ok 1 number(s): "350941677"
Test #24:
score: 31
Accepted
time: 0ms
memory: 18164kb
input:
195 186
output:
130526660
result:
ok 1 number(s): "130526660"
Test #25:
score: 31
Accepted
time: 0ms
memory: 16156kb
input:
173 159
output:
754934766
result:
ok 1 number(s): "754934766"
Test #26:
score: 31
Accepted
time: 0ms
memory: 20204kb
input:
194 170
output:
956364877
result:
ok 1 number(s): "956364877"
Subtask #4:
score: 41
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #27:
score: 41
Accepted
time: 39ms
memory: 138700kb
input:
3000 2999
output:
5195706
result:
ok 1 number(s): "5195706"
Test #28:
score: 41
Accepted
time: 35ms
memory: 148588kb
input:
3000 3000
output:
224347336
result:
ok 1 number(s): "224347336"
Test #29:
score: 41
Accepted
time: 32ms
memory: 144860kb
input:
2854 2864
output:
513408195
result:
ok 1 number(s): "513408195"
Test #30:
score: 41
Accepted
time: 28ms
memory: 148188kb
input:
2887 2803
output:
58832696
result:
ok 1 number(s): "58832696"
Test #31:
score: 41
Accepted
time: 35ms
memory: 148364kb
input:
2800 2925
output:
804387597
result:
ok 1 number(s): "804387597"
Test #32:
score: 41
Accepted
time: 23ms
memory: 153252kb
input:
2842 2813
output:
971828715
result:
ok 1 number(s): "971828715"
Test #33:
score: 41
Accepted
time: 36ms
memory: 149992kb
input:
2808 2972
output:
329457042
result:
ok 1 number(s): "329457042"
Test #34:
score: 41
Accepted
time: 31ms
memory: 151708kb
input:
2821 2853
output:
81282690
result:
ok 1 number(s): "81282690"
Test #35:
score: 41
Accepted
time: 24ms
memory: 155308kb
input:
2875 2956
output:
105351485
result:
ok 1 number(s): "105351485"
Test #36:
score: 41
Accepted
time: 35ms
memory: 149320kb
input:
2879 2852
output:
672034506
result:
ok 1 number(s): "672034506"
Extra Test:
score: 0
Extra Test Passed