QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#603839#7802. Game of Nimsurgutti#AC ✓749ms6772kbC++201.6kb2024-10-01 20:03:432024-10-01 20:03:44

Judging History

This is the latest submission verdict.

  • [2024-10-01 20:03:44]
  • Judged
  • Verdict: AC
  • Time: 749ms
  • Memory: 6772kb
  • [2024-10-01 20:03:43]
  • Submitted

answer

// Author: Olaf Surgut (surgutti)
// Created on 01-10-2024 13:41:45
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

#define endl '\n'
#define st first
#define nd second
#define pb push_bask
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define ROF(i, b, a) for (int i = (b); i >= (a); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)

const int N = 500 + 7;

int dp[2][2 * N][N];
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, p, m;
	cin >> n >> p >> m;
	
	int bits = 1;
	while (bits <= max(p, n - p))
		bits <<= 1;

	dp[0][p][n - p] = 1;
	
	debug(bits);

	FOR(i, 1, n - p) {
		int a = i & 1;
		int b = a ^ 1;

		REP(x, bits) FOR(j, 0, n - p)
			dp[a][x][j] = 0;

		debug(i, a, b);

		FOR(j, 0, n - p) {
			for (int k = 0; i * k <= j; k++) {
				if (k % 2 == 0) {
					REP(x, bits) {
						int& X = dp[a][x][j - k * i];
						X += dp[b][x][j];
						if (X >= m)
							X -= m;
					}
				}
				else {
					REP(x, bits) {
						int& X = dp[a][x ^ i][j - k * i];
						X += dp[b][x][j];
						if (X >= m)
							X -= m;
					}
				}
			}
		}
	}

	cout << dp[(n - p) & 1][0][0] << '\n';

	return 0;
}

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

详细

Test #1:

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

input:

8 3 1000

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

input:

5 2 1000

output:

0

result:

ok 1 number(s): "0"

Test #3:

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

input:

2 1 2

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

input:

6 2 1323123

output:

2

result:

ok 1 number(s): "2"

Test #5:

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

input:

10 4 123412412

output:

2

result:

ok 1 number(s): "2"

Test #6:

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

input:

20 10 123123

output:

2

result:

ok 1 number(s): "2"

Test #7:

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

input:

42 23 231234142

output:

0

result:

ok 1 number(s): "0"

Test #8:

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

input:

42 12 123123342

output:

610

result:

ok 1 number(s): "610"

Test #9:

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

input:

132 42 198519289

output:

386930

result:

ok 1 number(s): "386930"

Test #10:

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

input:

168 55 190931488

output:

7739643

result:

ok 1 number(s): "7739643"

Test #11:

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

input:

248 119 180187404

output:

5541

result:

ok 1 number(s): "5541"

Test #12:

score: 0
Accepted
time: 210ms
memory: 6672kb

input:

318 39 446463275

output:

309993834

result:

ok 1 number(s): "309993834"

Test #13:

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

input:

464 193 484172941

output:

58956714

result:

ok 1 number(s): "58956714"

Test #14:

score: 0
Accepted
time: 563ms
memory: 6724kb

input:

492 49 509191931

output:

410787599

result:

ok 1 number(s): "410787599"

Test #15:

score: 0
Accepted
time: 456ms
memory: 6680kb

input:

500 100 1000000000

output:

898871667

result:

ok 1 number(s): "898871667"

Test #16:

score: 0
Accepted
time: 245ms
memory: 6604kb

input:

500 200 2424

output:

1571

result:

ok 1 number(s): "1571"

Test #17:

score: 0
Accepted
time: 735ms
memory: 6664kb

input:

500 1 998244353

output:

824962382

result:

ok 1 number(s): "824962382"

Test #18:

score: 0
Accepted
time: 733ms
memory: 6656kb

input:

500 2 999999999

output:

479167812

result:

ok 1 number(s): "479167812"

Test #19:

score: 0
Accepted
time: 727ms
memory: 6652kb

input:

500 5 987654321

output:

888251427

result:

ok 1 number(s): "888251427"

Test #20:

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

input:

500 499 2

output:

0

result:

ok 1 number(s): "0"

Test #21:

score: 0
Accepted
time: 76ms
memory: 6184kb

input:

500 250 4324

output:

203

result:

ok 1 number(s): "203"

Test #22:

score: 0
Accepted
time: 156ms
memory: 6636kb

input:

500 256 1000000000

output:

0

result:

ok 1 number(s): "0"

Test #23:

score: 0
Accepted
time: 73ms
memory: 6160kb

input:

500 255 1000000000

output:

0

result:

ok 1 number(s): "0"

Test #24:

score: 0
Accepted
time: 69ms
memory: 6200kb

input:

500 254 1000000000

output:

0

result:

ok 1 number(s): "0"

Test #25:

score: 0
Accepted
time: 74ms
memory: 6168kb

input:

500 253 1000000000

output:

0

result:

ok 1 number(s): "0"

Test #26:

score: 0
Accepted
time: 75ms
memory: 6260kb

input:

500 252 1000000000

output:

0

result:

ok 1 number(s): "0"

Test #27:

score: 0
Accepted
time: 76ms
memory: 6260kb

input:

500 251 1000000000

output:

0

result:

ok 1 number(s): "0"

Test #28:

score: 0
Accepted
time: 183ms
memory: 6728kb

input:

500 240 1000000000

output:

78752

result:

ok 1 number(s): "78752"

Test #29:

score: 0
Accepted
time: 400ms
memory: 6608kb

input:

500 127 1000000000

output:

735856900

result:

ok 1 number(s): "735856900"

Test #30:

score: 0
Accepted
time: 387ms
memory: 6704kb

input:

500 128 1000000000

output:

752639907

result:

ok 1 number(s): "752639907"

Test #31:

score: 0
Accepted
time: 545ms
memory: 6772kb

input:

500 64 1000000000

output:

696747666

result:

ok 1 number(s): "696747666"

Test #32:

score: 0
Accepted
time: 546ms
memory: 6692kb

input:

500 63 1000000000

output:

372258537

result:

ok 1 number(s): "372258537"

Test #33:

score: 0
Accepted
time: 49ms
memory: 6200kb

input:

333 123 303739951

output:

0

result:

ok 1 number(s): "0"

Test #34:

score: 0
Accepted
time: 568ms
memory: 6660kb

input:

497 55 842080168

output:

0

result:

ok 1 number(s): "0"

Test #35:

score: 0
Accepted
time: 23ms
memory: 6652kb

input:

395 291 982483005

output:

0

result:

ok 1 number(s): "0"

Test #36:

score: 0
Accepted
time: 20ms
memory: 6772kb

input:

481 389 968737780

output:

0

result:

ok 1 number(s): "0"

Test #37:

score: 0
Accepted
time: 186ms
memory: 6648kb

input:

341 74 211356241

output:

0

result:

ok 1 number(s): "0"

Test #38:

score: 0
Accepted
time: 561ms
memory: 6652kb

input:

447 6 220551443

output:

0

result:

ok 1 number(s): "0"

Test #39:

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

input:

117 53 229852993

output:

0

result:

ok 1 number(s): "0"

Test #40:

score: 0
Accepted
time: 214ms
memory: 6672kb

input:

374 92 655232919

output:

510631436

result:

ok 1 number(s): "510631436"

Test #41:

score: 0
Accepted
time: 22ms
memory: 6136kb

input:

161 24 522915247

output:

0

result:

ok 1 number(s): "0"

Test #42:

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

input:

296 264 921737931

output:

0

result:

ok 1 number(s): "0"

Test #43:

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

input:

123 59 249153627

output:

0

result:

ok 1 number(s): "0"

Test #44:

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

input:

321 289 374745139

output:

0

result:

ok 1 number(s): "0"

Test #45:

score: 0
Accepted
time: 40ms
memory: 6660kb

input:

449 321 564028761

output:

0

result:

ok 1 number(s): "0"

Test #46:

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

input:

67 65 193423543

output:

0

result:

ok 1 number(s): "0"

Test #47:

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

input:

272 268 89068990

output:

0

result:

ok 1 number(s): "0"

Test #48:

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

input:

491 483 929064777

output:

0

result:

ok 1 number(s): "0"

Test #49:

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

input:

344 328 489724616

output:

0

result:

ok 1 number(s): "0"

Test #50:

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

input:

362 330 987111640

output:

0

result:

ok 1 number(s): "0"

Test #51:

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

input:

255 191 825170913

output:

0

result:

ok 1 number(s): "0"

Test #52:

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

input:

297 169 682131614

output:

0

result:

ok 1 number(s): "0"

Test #53:

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

input:

372 116 897520833

output:

406985347

result:

ok 1 number(s): "406985347"

Test #54:

score: 0
Accepted
time: 173ms
memory: 6644kb

input:

351 95 801600616

output:

0

result:

ok 1 number(s): "0"

Test #55:

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

input:

427 299 527480415

output:

0

result:

ok 1 number(s): "0"

Test #56:

score: 0
Accepted
time: 610ms
memory: 6704kb

input:

493 35 345854681

output:

0

result:

ok 1 number(s): "0"

Test #57:

score: 0
Accepted
time: 508ms
memory: 6660kb

input:

466 45 705433124

output:

405583388

result:

ok 1 number(s): "405583388"

Test #58:

score: 0
Accepted
time: 202ms
memory: 6640kb

input:

295 20 478460925

output:

0

result:

ok 1 number(s): "0"

Test #59:

score: 0
Accepted
time: 513ms
memory: 6672kb

input:

459 38 692239363

output:

0

result:

ok 1 number(s): "0"

Test #60:

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

input:

3 1 1000

output:

0

result:

ok 1 number(s): "0"

Test #61:

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

input:

3 2 1000

output:

0

result:

ok 1 number(s): "0"

Test #62:

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

input:

4 1 1000

output:

1

result:

ok 1 number(s): "1"

Test #63:

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

input:

4 2 1000

output:

1

result:

ok 1 number(s): "1"

Test #64:

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

input:

4 3 1000

output:

0

result:

ok 1 number(s): "0"

Test #65:

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

input:

8 3 2

output:

0

result:

ok 1 number(s): "0"

Test #66:

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

input:

6 1 100

output:

3

result:

ok 1 number(s): "3"

Test #67:

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

input:

6 2 100

output:

2

result:

ok 1 number(s): "2"

Test #68:

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

input:

6 3 100

output:

2

result:

ok 1 number(s): "2"

Test #69:

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

input:

256 128 123981492

output:

1

result:

ok 1 number(s): "1"

Test #70:

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

input:

254 127 1000000000

output:

877

result:

ok 1 number(s): "877"

Test #71:

score: 0
Accepted
time: 739ms
memory: 5692kb

input:

500 14 958912859

output:

650304186

result:

ok 1 number(s): "650304186"

Test #72:

score: 0
Accepted
time: 620ms
memory: 6732kb

input:

500 42 591829519

output:

133671197

result:

ok 1 number(s): "133671197"

Test #73:

score: 0
Accepted
time: 738ms
memory: 6600kb

input:

499 1 999912321

output:

0

result:

ok 1 number(s): "0"

Test #74:

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

input:

499 498 984129849

output:

0

result:

ok 1 number(s): "0"

Test #75:

score: 0
Accepted
time: 727ms
memory: 6720kb

input:

498 1 918239128

output:

604086379

result:

ok 1 number(s): "604086379"

Test #76:

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

input:

498 497 984192849

output:

0

result:

ok 1 number(s): "0"

Test #77:

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

input:

254 127 877

output:

0

result:

ok 1 number(s): "0"

Test #78:

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

input:

254 125 729

output:

0

result:

ok 1 number(s): "0"

Test #79:

score: 0
Accepted
time: 454ms
memory: 6628kb

input:

500 100 613156101

output:

0

result:

ok 1 number(s): "0"

Test #80:

score: 0
Accepted
time: 457ms
memory: 6616kb

input:

500 99 755405164

output:

3

result:

ok 1 number(s): "3"

Test #81:

score: 0
Accepted
time: 459ms
memory: 6692kb

input:

500 99 924361444

output:

924361439

result:

ok 1 number(s): "924361439"

Test #82:

score: 0
Accepted
time: 465ms
memory: 6664kb

input:

500 97 6974800

output:

1

result:

ok 1 number(s): "1"

Test #83:

score: 0
Accepted
time: 464ms
memory: 6676kb

input:

500 96 42601567

output:

42601566

result:

ok 1 number(s): "42601566"

Test #84:

score: 0
Accepted
time: 749ms
memory: 6664kb

input:

500 1 2

output:

1

result:

ok 1 number(s): "1"

Test #85:

score: 0
Accepted
time: 743ms
memory: 6704kb

input:

500 1 5

output:

2

result:

ok 1 number(s): "2"

Test #86:

score: 0
Accepted
time: 737ms
memory: 6652kb

input:

500 1 14

output:

5

result:

ok 1 number(s): "5"

Test #87:

score: 0
Accepted
time: 729ms
memory: 6724kb

input:

500 1 42

output:

33

result:

ok 1 number(s): "33"

Test #88:

score: 0
Accepted
time: 733ms
memory: 6704kb

input:

500 1 132

output:

123

result:

ok 1 number(s): "123"

Test #89:

score: 0
Accepted
time: 738ms
memory: 6732kb

input:

500 1 429

output:

57

result:

ok 1 number(s): "57"

Test #90:

score: 0
Accepted
time: 747ms
memory: 6660kb

input:

500 1 3

output:

0

result:

ok 1 number(s): "0"

Extra Test:

score: 0
Extra Test Passed