| 编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
|---|---|---|---|---|---|---|---|---|
| #50942 | #1255. 棋盘计数 | Accepted | 100 | 189 ms | 8348 K | C++ 17 / 1.0 K | afhi | 2021-07-06 0:33:45 |
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int MAX_N = 1005;
int dp[MAX_N][MAX_N][2];
const int mod = 1e9 + 7;
void add(int& a, int b) { a = (a + b) % mod; }
int mulMod(ll a, ll b) { return (a * b) % mod; }
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int T;
cin >> T;
memset(dp, 0, sizeof(dp));
dp[1][0][0] = 1;
int n = 1001;
for (int i = 1; i < n; i++) {
for (int k = 0; k < i; k++) {
add(dp[i + 1][k + 1][1], mulMod(dp[i][k][0], 2));
add(dp[i + 1][k + 1][1], dp[i][k][1]);
add(dp[i + 1][k][1], dp[i][k][1]);
add(dp[i + 1][k][0], mulMod(i - k - 1, dp[i][k][0]));
add(dp[i + 1][k][0], mulMod(i - k, dp[i][k][1]));
if (k > 0) {
add(dp[i + 1][k - 1][0], mulMod(k, dp[i][k][0]));
add(dp[i + 1][k - 1][0], mulMod(k - 1, dp[i][k][1]));
}
}
}
while (T--) {
int n, k;
cin >> n >> k;
cout << (dp[n][k][0] + dp[n][k][1]) % mod << "\n";
}
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