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>| 编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
|---|---|---|---|---|---|---|---|---|
| #50923 | #1255. 棋盘计数 | Time Limit Exceeded | 0 | 10262 ms | 8340 K | C++ 17 / 1.0 K | afhi | 2021-07-06 0:13:54 |
#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 += b;
if (a >= mod)
a -= b;
}
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;
while (T--) {
int n, k;
cin >> n >> k;
memset(dp, 0, sizeof(dp));
dp[1][0][0] = 1;
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]));
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]));
}
}
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>999
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>998
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>997
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>996
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>995
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>994
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>993
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>992
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>