QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#49484 | #1261. Inv | ckiseki# | RE | 2ms | 3700kb | C++ | 1.0kb | 2022-09-21 16:35:38 | 2022-09-21 16:35:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
uint32_t dp[maxn][maxn];
uint32_t pre[maxn];
void build(int x) {
for (int i = 0; i < maxn; i++) {
pre[i] = dp[x][i];
if (i >= 2) pre[i] += pre[i - 2];
}
}
uint32_t query(int r, int l) {
if (r < 0)
return 0;
else if (l - 2 < 0)
return pre[r];
else
return pre[r] - pre[l - 2];
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, K;
cin >> n >> K;
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= i*(i-1)/2; j++)
dp[i][j] = dp[i-1][j];
build(i-1);
for (int j = 0; j <= i*(i-1)/2; j++) {
dp[i][j] += query(j - 1, j - 1 - (i-2) * 2);
// for (int k = 0; k <= i-2; k++) {
// int jj = j - k*2 - 1;
// if (jj >= 0)
// dp[i][j] += dp[i-1][jj];
// }
}
}
// cout << dp[n][K] << '\n';
cout << dp[n][K] % 2 << '\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3516kb
input:
4 1
output:
1
result:
ok answer is '1'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3700kb
input:
10 21
output:
0
result:
ok answer is '0'
Test #3:
score: -100
Runtime Error
input:
500 124331