QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#260316 | #7802. Game of Nim | DoorKickers# | AC ✓ | 985ms | 1017228kb | C++20 | 2.7kb | 2023-11-22 01:22:07 | 2023-11-22 01:22:07 |
Judging History
answer
#include <bits/stdc++.h>
#include <algorithm>
#include <cctype>
#include <climits>
#include <functional>
#include <iomanip>
#include <queue>
#include <set>
#include <valarray>
#define ll long long
#define ull unsigned long long
#define mp make_pair
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define rep(a, b, c) for (int a = b; a <= c; a++)
#define per(a, b, c) for (int a = c; a >= b; a--)
#define all(a) a.begin() + 1, a.end()
#define all_(a) a.begin(), a.end()
#define vi vector<int>
#define vl vector<ll>
#define vpii vector<pii>
#define vpll vector<pll>
int mod = 998244353;
ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a % b);}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll fp_m (ll a, ll n) {
a %= mod;
ll res = 1; while (n) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res;
}
ll fp (ll a, ll n) {
ll res = 1; while (n) { if (n & 1) res *= a; a *= a; n >>= 1; } return res;
}
ll inv(ll x) {return fp_m(x, mod - 2);}
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
os << "[";
for (size_t i = 0; i < vec.size(); ++i) {
os << vec[i];
if (i < vec.size() - 1)
os << ", ";
}
os << "]";
return os;
}
template<typename T, typename... Args>
void debug(std::string name, T value, Args &&...arg) {
std::cout << name;
(..., (std::cout << '[' << arg << ']'));
std::cout << " = " << value << '\n';
}
//中文测试 中文测试
signed main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0); std::cout.tie(0);
int n, p, m; std::cin >> n >> p >> m;
mod = m;
// dp[i][j][k] for (i item) (j xor sum) (k last value) : ways
// dp[i + nk][j ^ nk][nk] += dp[i][j][k] (nk >= k)
std::vector dp(n + 1, std::vector(512, std::vector<long long>(n + 1)));
dp[0][0][0] = 1;
// note that xor sum <= value sum
// note that A xor B >= A - B
for (int i = 0; i <= n - p; i++) {
for (int j = 0; j <= i; j++) {
if (j - (n - p - i) > p || j + (n - p - i) < p) continue;
for (int k = 0; k <= i; k++) {
if (dp[i][j][k] != 0) {
for (int nk = std::max(1, k); i + nk <= n - p; nk++) {
dp[i + nk][j ^ nk][nk] = (dp[i + nk][j ^ nk][nk] + dp[i][j][k]) % mod;
}
}
// debug("dp", dp[i][j][k], i, j, k);
}
}
}
long long ans = 0;
for (int i = 1; i <= n; i++) {
ans = (ans + dp[n - p][p][i]) % mod;
}
std::cout << ans << '\n';
return 0;
}
/*
1 2 3 4 5 6
[1, 1]
[2, 2]
[3, 3]
[4, 2]
[5, 1]
[6, 1]
*/
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4148kb
input:
8 3 1000
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 1ms
memory: 4096kb
input:
5 2 1000
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
2 1 2
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3976kb
input:
6 2 1323123
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 1ms
memory: 4280kb
input:
10 4 123412412
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 2ms
memory: 5500kb
input:
20 10 123123
output:
2
result:
ok 1 number(s): "2"
Test #7:
score: 0
Accepted
time: 4ms
memory: 11500kb
input:
42 23 231234142
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 0ms
memory: 11544kb
input:
42 12 123123342
output:
610
result:
ok 1 number(s): "610"
Test #9:
score: 0
Accepted
time: 8ms
memory: 76516kb
input:
132 42 198519289
output:
386930
result:
ok 1 number(s): "386930"
Test #10:
score: 0
Accepted
time: 19ms
memory: 120852kb
input:
168 55 190931488
output:
7739643
result:
ok 1 number(s): "7739643"
Test #11:
score: 0
Accepted
time: 16ms
memory: 256212kb
input:
248 119 180187404
output:
5541
result:
ok 1 number(s): "5541"
Test #12:
score: 0
Accepted
time: 140ms
memory: 416504kb
input:
318 39 446463275
output:
309993834
result:
ok 1 number(s): "309993834"
Test #13:
score: 0
Accepted
time: 103ms
memory: 877416kb
input:
464 193 484172941
output:
58956714
result:
ok 1 number(s): "58956714"
Test #14:
score: 0
Accepted
time: 668ms
memory: 985204kb
input:
492 49 509191931
output:
410787599
result:
ok 1 number(s): "410787599"
Test #15:
score: 0
Accepted
time: 456ms
memory: 1017228kb
input:
500 100 1000000000
output:
898871667
result:
ok 1 number(s): "898871667"
Test #16:
score: 0
Accepted
time: 162ms
memory: 1017200kb
input:
500 200 2424
output:
1571
result:
ok 1 number(s): "1571"
Test #17:
score: 0
Accepted
time: 966ms
memory: 1017056kb
input:
500 1 998244353
output:
824962382
result:
ok 1 number(s): "824962382"
Test #18:
score: 0
Accepted
time: 958ms
memory: 1017156kb
input:
500 2 999999999
output:
479167812
result:
ok 1 number(s): "479167812"
Test #19:
score: 0
Accepted
time: 938ms
memory: 1017096kb
input:
500 5 987654321
output:
888251427
result:
ok 1 number(s): "888251427"
Test #20:
score: 0
Accepted
time: 95ms
memory: 1017100kb
input:
500 499 2
output:
0
result:
ok 1 number(s): "0"
Test #21:
score: 0
Accepted
time: 79ms
memory: 1017052kb
input:
500 250 4324
output:
203
result:
ok 1 number(s): "203"
Test #22:
score: 0
Accepted
time: 80ms
memory: 1017060kb
input:
500 256 1000000000
output:
0
result:
ok 1 number(s): "0"
Test #23:
score: 0
Accepted
time: 76ms
memory: 1017208kb
input:
500 255 1000000000
output:
0
result:
ok 1 number(s): "0"
Test #24:
score: 0
Accepted
time: 88ms
memory: 1017156kb
input:
500 254 1000000000
output:
0
result:
ok 1 number(s): "0"
Test #25:
score: 0
Accepted
time: 95ms
memory: 1017076kb
input:
500 253 1000000000
output:
0
result:
ok 1 number(s): "0"
Test #26:
score: 0
Accepted
time: 80ms
memory: 1017060kb
input:
500 252 1000000000
output:
0
result:
ok 1 number(s): "0"
Test #27:
score: 0
Accepted
time: 68ms
memory: 1017056kb
input:
500 251 1000000000
output:
0
result:
ok 1 number(s): "0"
Test #28:
score: 0
Accepted
time: 91ms
memory: 1017120kb
input:
500 240 1000000000
output:
78752
result:
ok 1 number(s): "78752"
Test #29:
score: 0
Accepted
time: 369ms
memory: 1017120kb
input:
500 127 1000000000
output:
735856900
result:
ok 1 number(s): "735856900"
Test #30:
score: 0
Accepted
time: 373ms
memory: 1017136kb
input:
500 128 1000000000
output:
752639907
result:
ok 1 number(s): "752639907"
Test #31:
score: 0
Accepted
time: 630ms
memory: 1017120kb
input:
500 64 1000000000
output:
696747666
result:
ok 1 number(s): "696747666"
Test #32:
score: 0
Accepted
time: 619ms
memory: 1017104kb
input:
500 63 1000000000
output:
372258537
result:
ok 1 number(s): "372258537"
Test #33:
score: 0
Accepted
time: 60ms
memory: 457468kb
input:
333 123 303739951
output:
0
result:
ok 1 number(s): "0"
Test #34:
score: 0
Accepted
time: 639ms
memory: 1007020kb
input:
497 55 842080168
output:
0
result:
ok 1 number(s): "0"
Test #35:
score: 0
Accepted
time: 55ms
memory: 639860kb
input:
395 291 982483005
output:
0
result:
ok 1 number(s): "0"
Test #36:
score: 0
Accepted
time: 80ms
memory: 944096kb
input:
481 389 968737780
output:
0
result:
ok 1 number(s): "0"
Test #37:
score: 0
Accepted
time: 119ms
memory: 479452kb
input:
341 74 211356241
output:
0
result:
ok 1 number(s): "0"
Test #38:
score: 0
Accepted
time: 605ms
memory: 816744kb
input:
447 6 220551443
output:
0
result:
ok 1 number(s): "0"
Test #39:
score: 0
Accepted
time: 12ms
memory: 61808kb
input:
117 53 229852993
output:
0
result:
ok 1 number(s): "0"
Test #40:
score: 0
Accepted
time: 137ms
memory: 573024kb
input:
374 92 655232919
output:
510631436
result:
ok 1 number(s): "510631436"
Test #41:
score: 0
Accepted
time: 19ms
memory: 112236kb
input:
161 24 522915247
output:
0
result:
ok 1 number(s): "0"
Test #42:
score: 0
Accepted
time: 28ms
memory: 361912kb
input:
296 264 921737931
output:
0
result:
ok 1 number(s): "0"
Test #43:
score: 0
Accepted
time: 3ms
memory: 67820kb
input:
123 59 249153627
output:
0
result:
ok 1 number(s): "0"
Test #44:
score: 0
Accepted
time: 44ms
memory: 425740kb
input:
321 289 374745139
output:
0
result:
ok 1 number(s): "0"
Test #45:
score: 0
Accepted
time: 75ms
memory: 823852kb
input:
449 321 564028761
output:
0
result:
ok 1 number(s): "0"
Test #46:
score: 0
Accepted
time: 9ms
memory: 23452kb
input:
67 65 193423543
output:
0
result:
ok 1 number(s): "0"
Test #47:
score: 0
Accepted
time: 48ms
memory: 306648kb
input:
272 268 89068990
output:
0
result:
ok 1 number(s): "0"
Test #48:
score: 0
Accepted
time: 92ms
memory: 983412kb
input:
491 483 929064777
output:
0
result:
ok 1 number(s): "0"
Test #49:
score: 0
Accepted
time: 35ms
memory: 486176kb
input:
344 328 489724616
output:
0
result:
ok 1 number(s): "0"
Test #50:
score: 0
Accepted
time: 31ms
memory: 537472kb
input:
362 330 987111640
output:
0
result:
ok 1 number(s): "0"
Test #51:
score: 0
Accepted
time: 31ms
memory: 271672kb
input:
255 191 825170913
output:
0
result:
ok 1 number(s): "0"
Test #52:
score: 0
Accepted
time: 45ms
memory: 365536kb
input:
297 169 682131614
output:
0
result:
ok 1 number(s): "0"
Test #53:
score: 0
Accepted
time: 99ms
memory: 567244kb
input:
372 116 897520833
output:
406985347
result:
ok 1 number(s): "406985347"
Test #54:
score: 0
Accepted
time: 101ms
memory: 507360kb
input:
351 95 801600616
output:
0
result:
ok 1 number(s): "0"
Test #55:
score: 0
Accepted
time: 79ms
memory: 746272kb
input:
427 299 527480415
output:
0
result:
ok 1 number(s): "0"
Test #56:
score: 0
Accepted
time: 718ms
memory: 991284kb
input:
493 35 345854681
output:
0
result:
ok 1 number(s): "0"
Test #57:
score: 0
Accepted
time: 520ms
memory: 884872kb
input:
466 45 705433124
output:
405583388
result:
ok 1 number(s): "405583388"
Test #58:
score: 0
Accepted
time: 108ms
memory: 360852kb
input:
295 20 478460925
output:
0
result:
ok 1 number(s): "0"
Test #59:
score: 0
Accepted
time: 536ms
memory: 860588kb
input:
459 38 692239363
output:
0
result:
ok 1 number(s): "0"
Test #60:
score: 0
Accepted
time: 1ms
memory: 3800kb
input:
3 1 1000
output:
0
result:
ok 1 number(s): "0"
Test #61:
score: 0
Accepted
time: 1ms
memory: 3796kb
input:
3 2 1000
output:
0
result:
ok 1 number(s): "0"
Test #62:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
4 1 1000
output:
1
result:
ok 1 number(s): "1"
Test #63:
score: 0
Accepted
time: 0ms
memory: 4000kb
input:
4 2 1000
output:
1
result:
ok 1 number(s): "1"
Test #64:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
4 3 1000
output:
0
result:
ok 1 number(s): "0"
Test #65:
score: 0
Accepted
time: 1ms
memory: 4136kb
input:
8 3 2
output:
0
result:
ok 1 number(s): "0"
Test #66:
score: 0
Accepted
time: 1ms
memory: 3856kb
input:
6 1 100
output:
3
result:
ok 1 number(s): "3"
Test #67:
score: 0
Accepted
time: 1ms
memory: 3972kb
input:
6 2 100
output:
2
result:
ok 1 number(s): "2"
Test #68:
score: 0
Accepted
time: 1ms
memory: 4200kb
input:
6 3 100
output:
2
result:
ok 1 number(s): "2"
Test #69:
score: 0
Accepted
time: 28ms
memory: 272616kb
input:
256 128 123981492
output:
1
result:
ok 1 number(s): "1"
Test #70:
score: 0
Accepted
time: 40ms
memory: 268392kb
input:
254 127 1000000000
output:
877
result:
ok 1 number(s): "877"
Test #71:
score: 0
Accepted
time: 870ms
memory: 1017056kb
input:
500 14 958912859
output:
650304186
result:
ok 1 number(s): "650304186"
Test #72:
score: 0
Accepted
time: 729ms
memory: 1017096kb
input:
500 42 591829519
output:
133671197
result:
ok 1 number(s): "133671197"
Test #73:
score: 0
Accepted
time: 985ms
memory: 1015224kb
input:
499 1 999912321
output:
0
result:
ok 1 number(s): "0"
Test #74:
score: 0
Accepted
time: 71ms
memory: 1015308kb
input:
499 498 984129849
output:
0
result:
ok 1 number(s): "0"
Test #75:
score: 0
Accepted
time: 920ms
memory: 1009228kb
input:
498 1 918239128
output:
604086379
result:
ok 1 number(s): "604086379"
Test #76:
score: 0
Accepted
time: 72ms
memory: 1009176kb
input:
498 497 984192849
output:
0
result:
ok 1 number(s): "0"
Test #77:
score: 0
Accepted
time: 15ms
memory: 268444kb
input:
254 127 877
output:
0
result:
ok 1 number(s): "0"
Test #78:
score: 0
Accepted
time: 19ms
memory: 268436kb
input:
254 125 729
output:
0
result:
ok 1 number(s): "0"
Test #79:
score: 0
Accepted
time: 451ms
memory: 1017204kb
input:
500 100 613156101
output:
0
result:
ok 1 number(s): "0"
Test #80:
score: 0
Accepted
time: 491ms
memory: 1017056kb
input:
500 99 755405164
output:
3
result:
ok 1 number(s): "3"
Test #81:
score: 0
Accepted
time: 480ms
memory: 1017120kb
input:
500 99 924361444
output:
924361439
result:
ok 1 number(s): "924361439"
Test #82:
score: 0
Accepted
time: 460ms
memory: 1017160kb
input:
500 97 6974800
output:
1
result:
ok 1 number(s): "1"
Test #83:
score: 0
Accepted
time: 470ms
memory: 1017060kb
input:
500 96 42601567
output:
42601566
result:
ok 1 number(s): "42601566"
Test #84:
score: 0
Accepted
time: 587ms
memory: 1017028kb
input:
500 1 2
output:
1
result:
ok 1 number(s): "1"
Test #85:
score: 0
Accepted
time: 776ms
memory: 1017052kb
input:
500 1 5
output:
2
result:
ok 1 number(s): "2"
Test #86:
score: 0
Accepted
time: 893ms
memory: 1017072kb
input:
500 1 14
output:
5
result:
ok 1 number(s): "5"
Test #87:
score: 0
Accepted
time: 972ms
memory: 1017152kb
input:
500 1 42
output:
33
result:
ok 1 number(s): "33"
Test #88:
score: 0
Accepted
time: 954ms
memory: 1017100kb
input:
500 1 132
output:
123
result:
ok 1 number(s): "123"
Test #89:
score: 0
Accepted
time: 955ms
memory: 1017072kb
input:
500 1 429
output:
57
result:
ok 1 number(s): "57"
Test #90:
score: 0
Accepted
time: 714ms
memory: 1017084kb
input:
500 1 3
output:
0
result:
ok 1 number(s): "0"
Extra Test:
score: 0
Extra Test Passed