| 编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
|---|---|---|---|---|---|---|---|---|
| #49250 | #1255. 棋盘计数 | Accepted | 100 | 201 ms | 16364 K | C++ 17 / 2.1 K | 丁丁跑卡车 | 2021-06-07 12:28:53 |
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ud unsigned int
#define ll long long
#define ull unsigned long long
#define MAX_INF 0x3f
#define MAX_INF_VAL 0x3f3f3f3f
#define MAX_INF_VAL_LL 0x3f3f3f3f3f3f3f3f
//#define pi 3.141592653589
#define eps 1e-9
#define F(x) ((x) / 3 + ((x) % 3 == 1 ? 0 : tb))
#define G(x) ((x) < tb ? (x)*3 + 1 : ((x)-tb) * 3 + 2)
//#define p 2173412051LL
//#define sz 2
using namespace std;
template <typename T>
void read(T &x) {
x = 0;
char ch = getchar();
ll f = 1;
while (!isdigit(ch)) {
if (ch == '-')
f *= -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - 48;
ch = getchar();
}
x *= f;
}
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
const ll p = 1e9 + 7;
ll f[1010][1010][2];
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
int n, m;
cin >> t;
memset(f, 0, sizeof(f));
f[1][0][0] = 1;
for (int i = 1; i < 1000; ++i) {
for (int j = 0; j < i; ++j) {
for (int k = 0; k < 2; ++k) {
ll tmp = f[i][j][k];
if (tmp == 0)
continue;
ll n0, n1, n2, n3 = 0;
if (k == 0) {
n0 = tmp * j;
n1 = tmp * 2;
n2 = tmp * (i - 1 - j);
} else {
n0 = tmp * (j - 1);
n1 = tmp;
n2 = tmp * (i - j);
n3 = tmp;
}
if (n0)
f[i + 1][j - 1][0] = (f[i + 1][j - 1][0] + n0) % p;
f[i + 1][j + 1][1] = (f[i + 1][j + 1][1] + n1) % p;
f[i + 1][j][0] = (f[i + 1][j][0] + n2) % p;
f[i + 1][j][1] = (f[i + 1][j][1] + n3) % p;
}
}
}
while (t--) {
cin >> n >> m;
cout << (f[n][m][0] + f[n][m][1]) % p << '\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