| 编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
|---|---|---|---|---|---|---|---|---|
| #47978 | #1255. 棋盘计数 | Accepted | 100 | 141 ms | 7212 K | C++ 17 / 901 B | Komeiji Koishi | 2021-05-10 11:35:23 |
#include <cstdio>
#include <algorithm>
using namespace std;
int n, k, dp[1005][1005][2], T;
const int mod = 1e9 + 7;
int M(int x) { return x >= mod ? x - mod : x; }
int main() {
dp[1][0][1] = 1;
dp[2][1][0] = 2;
for (int i = 2; i <= 1000; i++) {
for (int j = 0; j < i; j++) {
if (dp[i][j][0]) {
dp[i + 1][j][0] = M(dp[i + 1][j][0] + dp[i][j][0]);
if (j)
dp[i + 1][j - 1][1] = (1ll * dp[i + 1][j - 1][1] + 1ll * (j - 1) * dp[i][j][0]) % mod;
dp[i + 1][j][1] = (1ll * dp[i + 1][j][1] + 1ll * (i - j) * dp[i][j][0]) % mod;
dp[i + 1][j + 1][0] = M(dp[i + 1][j + 1][0] + dp[i][j][0]);
}
if (dp[i][j][1]) {
if (j)
dp[i + 1][j - 1][1] = (1ll * dp[i + 1][j - 1][1] + 1ll * j * dp[i][j][1]) % mod;
dp[i + 1][j][1] = (1ll * dp[i + 1][j][1] + 1ll * (i - j - 1) * dp[i][j][1]) % mod;
dp[i + 1][j + 1][0] = (1ll * dp[i + 1][j + 1][0] + 2ll * dp[i][j][1]) % mod;
}
}
}
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &k);
printf("%d\n", M(dp[n][k][0] + dp[n][k][1]));
}
return 0;
}1000
1000 0
1000 1
1000 2
1000 3
1000 4
1000 5
1000 6
1000 7
1000 8
1000 9
1000 10
1000
<9796 bytes omitted>711794305
99846303
899237562
681335754
230732925
841887937
326646608
783522506
856793774
62
<10775 bytes omitted>用户输出
711794305
99846303
899237562
681335754
230732925
841887937
326646608
783522506
856793774
627151005
22593836
500862107
386631082
<9747 bytes omitted>系统信息
Exited with return code 0999
999 0
999 1
999 2
999 3
999 4
999 5
999 6
999 7
999 8
999 9
999 10
999 11
999 12
9
<8786 bytes omitted>110101472
981934801
308522336
458676777
99450860
834644892
444203414
516153872
642974718
10
<10746 bytes omitted>用户输出
110101472
981934801
308522336
458676777
99450860
834644892
444203414
516153872
642974718
102785145
288326656
367298143
884037519
<9719 bytes omitted>系统信息
Exited with return code 0998
998 0
998 1
998 2
998 3
998 4
998 5
998 6
998 7
998 8
998 9
998 10
998 11
998 12
9
<8777 bytes omitted>445553830
153237199
464505551
267732642
280144046
678747047
837049884
817341812
367245736
3
<10737 bytes omitted>用户输出
445553830
153237199
464505551
267732642
280144046
678747047
837049884
817341812
367245736
396987041
515262046
531923638
15937224
<9711 bytes omitted>系统信息
Exited with return code 0997
997 0
997 1
997 2
997 3
997 4
997 5
997 6
997 7
997 8
997 9
997 10
997 11
997 12
9
<8768 bytes omitted>993342525
350021946
952046855
310916274
832525298
837369602
945431809
803095321
108393692
8
<10728 bytes omitted>用户输出
993342525
350021946
952046855
310916274
832525298
837369602
945431809
803095321
108393692
860597703
196127312
214302798
91350760
<9703 bytes omitted>系统信息
Exited with return code 0996
996 0
996 1
996 2
996 3
996 4
996 5
996 6
996 7
996 8
996 9
996 10
996 11
996 12
9
<8759 bytes omitted>753800152
728212331
666768406
767777799
407988856
717077293
645776066
256593174
849073806
6
<10748 bytes omitted>用户输出
753800152
728212331
666768406
767777799
407988856
717077293
645776066
256593174
849073806
607603573
83329883
743577533
265613044
<9724 bytes omitted>系统信息
Exited with return code 0995
995 0
995 1
995 2
995 3
995 4
995 5
995 6
995 7
995 8
995 9
995 10
995 11
995 12
9
<8750 bytes omitted>147787261
323705021
370950794
650199455
604696835
490633355
860606588
466696188
638847655
4
<10719 bytes omitted>用户输出
147787261
323705021
370950794
650199455
604696835
490633355
860606588
466696188
638847655
443708363
776120008
109192895
86505767
<9696 bytes omitted>系统信息
Exited with return code 0994
994 0
994 1
994 2
994 3
994 4
994 5
994 6
994 7
994 8
994 9
994 10
994 11
994 12
9
<8741 bytes omitted>327270428
984154964
146233155
98214204
273872499
413254345
188399121
739586319
950397586
15
<10702 bytes omitted>用户输出
327270428
984154964
146233155
98214204
273872499
413254345
188399121
739586319
950397586
158408509
156618558
138854423
918580701
<9680 bytes omitted>系统信息
Exited with return code 0993
993 0
993 1
993 2
993 3
993 4
993 5
993 6
993 7
993 8
993 9
993 10
993 11
993 12
9
<8732 bytes omitted>368613063
741788800
554400871
236850107
469888823
20327871
968247473
164762094
307277621
41
<10693 bytes omitted>用户输出
368613063
741788800
554400871
236850107
469888823
20327871
968247473
164762094
307277621
413455878
954805321
663273457
532577041
<9672 bytes omitted>系统信息
Exited with return code 0992
992 0
992 1
992 2
992 3
992 4
992 5
992 6
992 7
992 8
992 9
992 10
992 11
992 12
9
<8723 bytes omitted>456205691
435039377
617986349
362643120
828264223
592218404
658779911
642029069
851452394
3
<10691 bytes omitted>用户输出
456205691
435039377
617986349
362643120
828264223
592218404
658779911
642029069
851452394
308399607
752849091
97229093
848550688
<9671 bytes omitted>系统信息
Exited with return code 0991
991 0
991 1
991 2
991 3
991 4
991 5
991 6
991 7
991 8
991 9
991 10
991 11
991 12
9
<8714 bytes omitted>735748839
759625444
954034034
992746616
498441704
107731189
991424955
487056544
113495944
7
<10654 bytes omitted>用户输出
735748839
759625444
954034034
992746616
498441704
107731189
991424955
487056544
113495944
768683298
110578004
77706728
488833080
<9635 bytes omitted>系统信息
Exited with return code 0