QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#260316#7802. Game of NimDoorKickers#AC ✓985ms1017228kbC++202.7kb2023-11-22 01:22:072023-11-22 01:22:07

Judging History

This is the latest submission verdict.

  • [2023-11-22 01:22:07]
  • Judged
  • Verdict: AC
  • Time: 985ms
  • Memory: 1017228kb
  • [2023-11-22 01:22:07]
  • Submitted

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