QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#371128#7802. Game of Nimkevinyang#AC ✓215ms513980kbC++207.8kb2024-03-30 00:22:332024-03-30 00:22:35

Judging History

This is the latest submission verdict.

  • [2024-03-30 00:22:35]
  • Judged
  • Verdict: AC
  • Time: 215ms
  • Memory: 513980kb
  • [2024-03-30 00:22:33]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

/* Macros {{{ */
/*  A lot of this is from some of Benq's submissions
    [https://codeforces.com/profile/Benq]
    Ugly af to the eyes, but with vim fold its barable
    Hopefully c++20 concepts can make all this stuff must cleaner */

/* Basics {{{ */
using ll = long long;
using ld = long double;
using str = string;

using pi = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
#define mp make_pair
#define fi first
#define se second

#define arr array
#define ve vector
using vi = vector<int>;
using vll = vector<ll>;
using vld = vector<ld>;

using vpi = vector<pi>;
using vpll = vector<pll>;
using vpld = vector<pld>;

using vvi = vector<vi>;
using vvll = vector<vll>;
using vvld = vector<vld>;

using vvpi = vector<vpi>;
using vvpll = vector<vpll>;
using vvpld = vector<vpld>;

#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz size()
#define rsz(a) resize(a)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

#define For(i, a, b) for (int i = a; i < b; ++i)
#define Rof(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define rep(a) For(_, 0, a)
#define each(a, x) for (auto &a : x)
#define reach(a, x) for (auto a = x.rbegin(); a != x.rend(); ++a)

template <typename T, typename U>
inline void cmin(T &x, U y) {
    if (y < x) x = y;
}
template <typename T, typename U>
inline void cmax(T &x, U y) {
    if (x < y) x = y;
}
/*}}}*/

/* IO {{{ */

/* Template Macros {{{ */
#define tcT template <class T
#define tcTU tcT, class U
#define tcTUU tcT, class... U
/*}}}*/

inline namespace Helpers { /*{{{*/
tcT, class = void > struct is_iterable : false_type {};
tcT > struct is_iterable<
          T, void_t<decltype(begin(declval<T>())), decltype(end(declval<T>()))>>
    : true_type {};
tcT > constexpr bool is_iterable_v = is_iterable<T>::value;

tcT, class = void > struct is_readable : false_type {};
tcT > struct is_readable<T, typename std::enable_if_t<is_same_v<
                                decltype(cin >> declval<T &>()), istream &>>>
    : true_type {};
tcT > constexpr bool is_readable_v = is_readable<T>::value;

tcT, class = void > struct is_printable : false_type {};
tcT > struct is_printable<T, typename std::enable_if_t<is_same_v<
                                 decltype(cout << declval<T>()), ostream &>>>
    : true_type {};
tcT > constexpr bool is_printable_v = is_printable<T>::value;
} /* namespace Helpers */
/*}}}*/

inline namespace Input { /*{{{*/
tcT > constexpr bool needs_input_v = !is_readable_v<T> && is_iterable_v<T>;
tcTUU > void re(T &t, U &...u);
tcTU > void re(pair<T, U> &p); /* pairs */

/* re: read{{{ */
tcT > typename enable_if<is_readable_v<T>, void>::type re(T &x) {
    cin >> x;
} /* default */
tcT > typename enable_if<needs_input_v<T>, void>::type re(
          T &i);                                   // vectors, arrays, etc...
tcTU > void re(pair<T, U> &p) { re(p.fi, p.se); }  // pairs
tcT > typename enable_if<needs_input_v<T>, void>::type re(T &i) {
    each(x, i) re(x);
}
tcTUU > void re(T &t, U &...u) {
    re(t);
    re(u...);
} /* read multiple}}} */

/* rv: resize and read vectors{{{ */
void rv(size_t) {}
tcTUU > void rv(size_t N, ve<T> &t, U &...u);
template <class... U>
void rv(size_t, size_t N2, U &...u);
tcTUU > void rv(size_t N, ve<T> &t, U &...u) {
    t.rsz(N);
    re(t);
    rv(N, u...);
}
template <class... U>
void rv(size_t, size_t N2, U &...u) {
    rv(N2, u...);
} /*}}}*/

/* dumb shortcuts to read in ints{{{ */
void decrement() {} /* subtract one from each */
tcTUU > void decrement(T &t, U &...u) {
    --t;
    decrement(u...);
}
#define ints(...)    \
    int __VA_ARGS__; \
    re(__VA_ARGS__);
#define int1(...)      \
    ints(__VA_ARGS__); \
    decrement(__VA_ARGS__); /*}}}*/
} /* namespace Input */
/*}}}*/

inline namespace ToString { /*{{{*/
tcT > constexpr bool needs_output_v = !is_printable_v<T> && is_iterable_v<T>;

/* ts: string representation to print */
tcT > typename enable_if<is_printable_v<T>, str>::type ts(T v) {
    stringstream ss;
    ss << fixed << setprecision(15) << v;
    return ss.str();
} /* default */
tcT > str bit_vec(T t) { /* bit vector to string */
    str res = "{";
    For(i, 0, t.sz) res += ts(t[i]);
    res += "}";
    return res;
}
str ts(ve<bool> v) { return bit_vec(v); }
template <size_t SZ>
str ts(bitset<SZ> b) {
    return bit_vec(b);
} /* bit vector */
tcTU > str ts(pair<T, U> p); /* pairs */
tcT > typename enable_if<needs_output_v<T>, str>::type ts(
          T v); /* vectors, arrays */
tcTU > str ts(pair<T, U> p) { return "(" + ts(p.fi) + ", " + ts(p.se) + ")"; }
tcT > typename enable_if<is_iterable_v<T>, str>::type ts_sep(T v, str sep) {
    /* convert container to string w/ separator sep */
    bool fst = 1;
    str res = "";
    for (const auto &x : v) {
        if (!fst) res += sep;
        fst = 0;
        res += ts(x);
    }
    return res;
}
tcT > typename enable_if<needs_output_v<T>, str>::type ts(T v) {
    return "{" + ts_sep(v, ", ") + "}";
}

/* for nested DS */
template <int, class T>
typename enable_if<!needs_output_v<T>, ve<str>>::type ts_lev(const T &v) {
    return {ts(v)};
}
template <int lev, class T>
typename enable_if<needs_output_v<T>, ve<str>>::type ts_lev(const T &v) {
    if (lev == 0 || !v.sz) return {ts(v)};
    ve<str> res;
    for (const auto &t : v) {
        if (res.sz) res.back() += ",";
        ve<str> tmp = ts_lev<lev - 1>(t);
        res.insert(end(res), all(tmp));
    }
    For(i, 0, res.sz) {
        str bef = " ";
        if (i == 0) bef = "{";
        res[i] = bef + res[i];
    }
    res.back() += "}";
    return res;
}
} /* namespace ToString */
/*}}}*/

inline namespace Output { /*{{{*/
template <class T>
void pr_sep(ostream &os, str, const T &t) {
    os << ts(t);
}
template <class T, class... U>
void pr_sep(ostream &os, str sep, const T &t, const U &...u) {
    pr_sep(os, sep, t);
    os << sep;
    pr_sep(os, sep, u...);
}
/* print w/ no spaces */
template <class... T>
void pr(const T &...t) {
    pr_sep(cout, "", t...);
}
/* print w/ spaces, end with newline */
void ps() { cout << "\n"; }
template <class... T>
void ps(const T &...t) {
    pr_sep(cout, " ", t...);
    ps();
}
/* debug to cerr */
template <class... T>
void dbg_out(const T &...t) {
    pr_sep(cerr, " | ", t...);
    cerr << endl;
}
void loc_info(int line, str names) {
    cerr << "Line(" << line << ") -> [" << names << "]: ";
}
template <int lev, class T>
void dbgl_out(const T &t) {
    cerr << "\n\n" << ts_sep(ts_lev<lev>(t), "\n") << "\n" << endl;
}
} /* namespace Output */
/*}}}}}}}}}*/

int n, p, m;

void solve() {
    re(n, p, m);

    ve<vvi> dp((n-p)+1, vvi((n-p)+1, vi(513, 0)));

    // dp[i][j][k] = number of solutions for i stones with min pile being j and cur xor k
    //  dp[i][j][k] = (i >= j ? dp[i-j][j][k^j] : 0) + dp[i][j+1][k]
    //  dp[0][j][0] = 1

    for(int j=0; j<=(n-p); ++j) dp[0][j][0] = 1;

    for(int i=1; i<=(n-p); ++i) {
        for(int j=i; j>0; --j) {
            for(int k=0; k<513; ++k) {
                dp[i][j][k] = dp[i-j][j][k^j];
                if(j < (n-p)) dp[i][j][k] = (dp[i][j][k] + dp[i][j+1][k]) % m;
            }
        }
    }

    int res = dp[n-p][1][p];
    ps(res);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    /* cout << fixed << setprecision(6); */
    int t = 1;
    // cin >> t;
    for (int i = 0; i < t; i++) solve();

    return 0;
    // you should actually read the stuff at the bottom
}

/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3664kb

input:

8 3 1000

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3656kb

input:

5 2 1000

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

2 1 2

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

6 2 1323123

output:

2

result:

ok 1 number(s): "2"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

10 4 123412412

output:

2

result:

ok 1 number(s): "2"

Test #6:

score: 0
Accepted
time: 1ms
memory: 4092kb

input:

20 10 123123

output:

2

result:

ok 1 number(s): "2"

Test #7:

score: 0
Accepted
time: 1ms
memory: 3940kb

input:

42 23 231234142

output:

0

result:

ok 1 number(s): "0"

Test #8:

score: 0
Accepted
time: 0ms
memory: 5220kb

input:

42 12 123123342

output:

610

result:

ok 1 number(s): "610"

Test #9:

score: 0
Accepted
time: 4ms
memory: 20460kb

input:

132 42 198519289

output:

386930

result:

ok 1 number(s): "386930"

Test #10:

score: 0
Accepted
time: 7ms
memory: 29868kb

input:

168 55 190931488

output:

7739643

result:

ok 1 number(s): "7739643"

Test #11:

score: 0
Accepted
time: 8ms
memory: 37940kb

input:

248 119 180187404

output:

5541

result:

ok 1 number(s): "5541"

Test #12:

score: 0
Accepted
time: 65ms
memory: 163584kb

input:

318 39 446463275

output:

309993834

result:

ok 1 number(s): "309993834"

Test #13:

score: 0
Accepted
time: 43ms
memory: 154628kb

input:

464 193 484172941

output:

58956714

result:

ok 1 number(s): "58956714"

Test #14:

score: 0
Accepted
time: 139ms
memory: 405940kb

input:

492 49 509191931

output:

410787599

result:

ok 1 number(s): "410787599"

Test #15:

score: 0
Accepted
time: 104ms
memory: 331800kb

input:

500 100 1000000000

output:

898871667

result:

ok 1 number(s): "898871667"

Test #16:

score: 0
Accepted
time: 59ms
memory: 188388kb

input:

500 200 2424

output:

1571

result:

ok 1 number(s): "1571"

Test #17:

score: 0
Accepted
time: 195ms
memory: 513916kb

input:

500 1 998244353

output:

824962382

result:

ok 1 number(s): "824962382"

Test #18:

score: 0
Accepted
time: 215ms
memory: 511820kb

input:

500 2 999999999

output:

479167812

result:

ok 1 number(s): "479167812"

Test #19:

score: 0
Accepted
time: 191ms
memory: 505776kb

input:

500 5 987654321

output:

888251427

result:

ok 1 number(s): "888251427"

Test #20:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

500 499 2

output:

0

result:

ok 1 number(s): "0"

Test #21:

score: 0
Accepted
time: 53ms
memory: 132284kb

input:

500 250 4324

output:

203

result:

ok 1 number(s): "203"

Test #22:

score: 0
Accepted
time: 32ms
memory: 126084kb

input:

500 256 1000000000

output:

0

result:

ok 1 number(s): "0"

Test #23:

score: 0
Accepted
time: 36ms
memory: 127172kb

input:

500 255 1000000000

output:

0

result:

ok 1 number(s): "0"

Test #24:

score: 0
Accepted
time: 43ms
memory: 127960kb

input:

500 254 1000000000

output:

0

result:

ok 1 number(s): "0"

Test #25:

score: 0
Accepted
time: 31ms
memory: 128988kb

input:

500 253 1000000000

output:

0

result:

ok 1 number(s): "0"

Test #26:

score: 0
Accepted
time: 35ms
memory: 130176kb

input:

500 252 1000000000

output:

0

result:

ok 1 number(s): "0"

Test #27:

score: 0
Accepted
time: 44ms
memory: 131160kb

input:

500 251 1000000000

output:

0

result:

ok 1 number(s): "0"

Test #28:

score: 0
Accepted
time: 62ms
memory: 142424kb

input:

500 240 1000000000

output:

78752

result:

ok 1 number(s): "78752"

Test #29:

score: 0
Accepted
time: 104ms
memory: 289328kb

input:

500 127 1000000000

output:

735856900

result:

ok 1 number(s): "735856900"

Test #30:

score: 0
Accepted
time: 102ms
memory: 287656kb

input:

500 128 1000000000

output:

752639907

result:

ok 1 number(s): "752639907"

Test #31:

score: 0
Accepted
time: 152ms
memory: 393544kb

input:

500 64 1000000000

output:

696747666

result:

ok 1 number(s): "696747666"

Test #32:

score: 0
Accepted
time: 124ms
memory: 395236kb

input:

500 63 1000000000

output:

372258537

result:

ok 1 number(s): "372258537"

Test #33:

score: 0
Accepted
time: 25ms
memory: 94540kb

input:

333 123 303739951

output:

0

result:

ok 1 number(s): "0"

Test #34:

score: 0
Accepted
time: 152ms
memory: 404112kb

input:

497 55 842080168

output:

0

result:

ok 1 number(s): "0"

Test #35:

score: 0
Accepted
time: 7ms
memory: 25888kb

input:

395 291 982483005

output:

0

result:

ok 1 number(s): "0"

Test #36:

score: 0
Accepted
time: 3ms
memory: 21024kb

input:

481 389 968737780

output:

0

result:

ok 1 number(s): "0"

Test #37:

score: 0
Accepted
time: 44ms
memory: 150108kb

input:

341 74 211356241

output:

0

result:

ok 1 number(s): "0"

Test #38:

score: 0
Accepted
time: 136ms
memory: 402596kb

input:

447 6 220551443

output:

0

result:

ok 1 number(s): "0"

Test #39:

score: 0
Accepted
time: 3ms
memory: 12188kb

input:

117 53 229852993

output:

0

result:

ok 1 number(s): "0"

Test #40:

score: 0
Accepted
time: 47ms
memory: 167136kb

input:

374 92 655232919

output:

510631436

result:

ok 1 number(s): "510631436"

Test #41:

score: 0
Accepted
time: 17ms
memory: 42220kb

input:

161 24 522915247

output:

0

result:

ok 1 number(s): "0"

Test #42:

score: 0
Accepted
time: 2ms
memory: 5572kb

input:

296 264 921737931

output:

0

result:

ok 1 number(s): "0"

Test #43:

score: 0
Accepted
time: 6ms
memory: 12192kb

input:

123 59 249153627

output:

0

result:

ok 1 number(s): "0"

Test #44:

score: 0
Accepted
time: 2ms
memory: 5400kb

input:

321 289 374745139

output:

0

result:

ok 1 number(s): "0"

Test #45:

score: 0
Accepted
time: 19ms
memory: 37512kb

input:

449 321 564028761

output:

0

result:

ok 1 number(s): "0"

Test #46:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

67 65 193423543

output:

0

result:

ok 1 number(s): "0"

Test #47:

score: 0
Accepted
time: 1ms
memory: 3608kb

input:

272 268 89068990

output:

0

result:

ok 1 number(s): "0"

Test #48:

score: 0
Accepted
time: 1ms
memory: 3776kb

input:

491 483 929064777

output:

0

result:

ok 1 number(s): "0"

Test #49:

score: 0
Accepted
time: 1ms
memory: 3924kb

input:

344 328 489724616

output:

0

result:

ok 1 number(s): "0"

Test #50:

score: 0
Accepted
time: 0ms
memory: 5588kb

input:

362 330 987111640

output:

0

result:

ok 1 number(s): "0"

Test #51:

score: 0
Accepted
time: 0ms
memory: 12064kb

input:

255 191 825170913

output:

0

result:

ok 1 number(s): "0"

Test #52:

score: 0
Accepted
time: 11ms
memory: 37348kb

input:

297 169 682131614

output:

0

result:

ok 1 number(s): "0"

Test #53:

score: 0
Accepted
time: 56ms
memory: 138192kb

input:

372 116 897520833

output:

406985347

result:

ok 1 number(s): "406985347"

Test #54:

score: 0
Accepted
time: 39ms
memory: 138232kb

input:

351 95 801600616

output:

0

result:

ok 1 number(s): "0"

Test #55:

score: 0
Accepted
time: 11ms
memory: 37392kb

input:

427 299 527480415

output:

0

result:

ok 1 number(s): "0"

Test #56:

score: 0
Accepted
time: 152ms
memory: 433740kb

input:

493 35 345854681

output:

0

result:

ok 1 number(s): "0"

Test #57:

score: 0
Accepted
time: 130ms
memory: 367136kb

input:

466 45 705433124

output:

405583388

result:

ok 1 number(s): "405583388"

Test #58:

score: 0
Accepted
time: 56ms
memory: 159084kb

input:

295 20 478460925

output:

0

result:

ok 1 number(s): "0"

Test #59:

score: 0
Accepted
time: 135ms
memory: 367108kb

input:

459 38 692239363

output:

0

result:

ok 1 number(s): "0"

Test #60:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

3 1 1000

output:

0

result:

ok 1 number(s): "0"

Test #61:

score: 0
Accepted
time: 1ms
memory: 3552kb

input:

3 2 1000

output:

0

result:

ok 1 number(s): "0"

Test #62:

score: 0
Accepted
time: 0ms
memory: 3884kb

input:

4 1 1000

output:

1

result:

ok 1 number(s): "1"

Test #63:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

4 2 1000

output:

1

result:

ok 1 number(s): "1"

Test #64:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

4 3 1000

output:

0

result:

ok 1 number(s): "0"

Test #65:

score: 0
Accepted
time: 1ms
memory: 3648kb

input:

8 3 2

output:

0

result:

ok 1 number(s): "0"

Test #66:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

6 1 100

output:

3

result:

ok 1 number(s): "3"

Test #67:

score: 0
Accepted
time: 1ms
memory: 3684kb

input:

6 2 100

output:

2

result:

ok 1 number(s): "2"

Test #68:

score: 0
Accepted
time: 1ms
memory: 3572kb

input:

6 3 100

output:

2

result:

ok 1 number(s): "2"

Test #69:

score: 0
Accepted
time: 11ms
memory: 37500kb

input:

256 128 123981492

output:

1

result:

ok 1 number(s): "1"

Test #70:

score: 0
Accepted
time: 12ms
memory: 36984kb

input:

254 127 1000000000

output:

877

result:

ok 1 number(s): "877"

Test #71:

score: 0
Accepted
time: 175ms
memory: 487824kb

input:

500 14 958912859

output:

650304186

result:

ok 1 number(s): "650304186"

Test #72:

score: 0
Accepted
time: 155ms
memory: 433664kb

input:

500 42 591829519

output:

133671197

result:

ok 1 number(s): "133671197"

Test #73:

score: 0
Accepted
time: 191ms
memory: 511792kb

input:

499 1 999912321

output:

0

result:

ok 1 number(s): "0"

Test #74:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

499 498 984129849

output:

0

result:

ok 1 number(s): "0"

Test #75:

score: 0
Accepted
time: 187ms
memory: 509960kb

input:

498 1 918239128

output:

604086379

result:

ok 1 number(s): "604086379"

Test #76:

score: 0
Accepted
time: 1ms
memory: 3800kb

input:

498 497 984192849

output:

0

result:

ok 1 number(s): "0"

Test #77:

score: 0
Accepted
time: 7ms
memory: 36872kb

input:

254 127 877

output:

0

result:

ok 1 number(s): "0"

Test #78:

score: 0
Accepted
time: 11ms
memory: 37904kb

input:

254 125 729

output:

0

result:

ok 1 number(s): "0"

Test #79:

score: 0
Accepted
time: 116ms
memory: 331708kb

input:

500 100 613156101

output:

0

result:

ok 1 number(s): "0"

Test #80:

score: 0
Accepted
time: 126ms
memory: 333624kb

input:

500 99 755405164

output:

3

result:

ok 1 number(s): "3"

Test #81:

score: 0
Accepted
time: 115ms
memory: 333556kb

input:

500 99 924361444

output:

924361439

result:

ok 1 number(s): "924361439"

Test #82:

score: 0
Accepted
time: 115ms
memory: 336756kb

input:

500 97 6974800

output:

1

result:

ok 1 number(s): "1"

Test #83:

score: 0
Accepted
time: 122ms
memory: 338468kb

input:

500 96 42601567

output:

42601566

result:

ok 1 number(s): "42601566"

Test #84:

score: 0
Accepted
time: 191ms
memory: 513856kb

input:

500 1 2

output:

1

result:

ok 1 number(s): "1"

Test #85:

score: 0
Accepted
time: 175ms
memory: 513980kb

input:

500 1 5

output:

2

result:

ok 1 number(s): "2"

Test #86:

score: 0
Accepted
time: 196ms
memory: 513848kb

input:

500 1 14

output:

5

result:

ok 1 number(s): "5"

Test #87:

score: 0
Accepted
time: 175ms
memory: 513904kb

input:

500 1 42

output:

33

result:

ok 1 number(s): "33"

Test #88:

score: 0
Accepted
time: 200ms
memory: 513896kb

input:

500 1 132

output:

123

result:

ok 1 number(s): "123"

Test #89:

score: 0
Accepted
time: 177ms
memory: 513916kb

input:

500 1 429

output:

57

result:

ok 1 number(s): "57"

Test #90:

score: 0
Accepted
time: 191ms
memory: 513856kb

input:

500 1 3

output:

0

result:

ok 1 number(s): "0"

Extra Test:

score: 0
Extra Test Passed