QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#524578 | #8746. 排列游戏 | ucup-team052 | AC ✓ | 2291ms | 43476kb | C++23 | 1.7kb | 2024-08-19 20:14:40 | 2024-08-19 20:14:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int md = 1e9 + 7;
inline int add(int x, int y) {
if (x + y >= md) return x + y - md;
return x + y;
}
inline int sub(int x, int y) {
if (x < y) return x - y + md;
return x - y;
}
inline int mul(int x, int y) {
return 1ull * x * y % md;
}
inline int fpow(int x, int y) {
int ans = 1;
while (y) {
if (y & 1) ans = mul(ans, x);
y >>= 1; x = mul(x, x);
}
return ans;
}
const int N = 505, M = 5005;
vector < pair <int, int> > vec[N];
int f[2][N][M][2];
int ans[1005];
int T, n, m;
inline void upd(int &x, int y) {
x = add(x, y);
}
int main() {
scanf("%d", &T);
for (int i = 1; i <= T; i++) {
scanf("%d%d", &n, &m);
vec[n].emplace_back(m, i);
}
f[0][0][0][0] = 1;
for (int i = 0; i < 500; i++) {
int cur = i & 1;
memset(f[cur ^ 1], 0, sizeof(f[0]));
for (int j = 0; j <= i; j++) {
for (int k = 0; k <= 5000 - j * (j + 1) / 2; k++) {
for (int o = 0; o <= 1; o++) {
if (!f[cur][j][k][o]) continue;
int now = f[cur][j][k][o];
if (j) {
int x = j / 2 * (j / 2);
int y = (j + 1) / 2 * ((j + 1) / 2);
upd(f[cur ^ 1][j - 1][j + k][o], mul(now, x + y));
upd(f[cur ^ 1][j - 1][j + k][o ^ 1], mul(now, j * j - x - y));
}
int x = j / 2 + 1;
upd(f[cur ^ 1][j][j + k][o], mul(now, 2 * x - 1));
upd(f[cur ^ 1][j][j + k][o ^ 1], mul(now, j * 2 + 2 - 2 * x));
upd(f[cur ^ 1][j + 1][j + k][o ^ ((j + 1) % 2)], now);
}
}
}
for (auto j : vec[i + 1]) {
for (int k = 0; k <= j.first; k++) upd(ans[j.second], f[cur ^ 1][0][k][(i + 1) % 2]);
}
}
for (int i = 1; i <= T; i++) printf("%d\n", ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2270ms
memory: 43248kb
input:
6 2 1 3 1 5 2 7 5 10 20 15 24
output:
1 2 7 331 1570446 73880648
result:
ok 6 lines
Test #2:
score: 0
Accepted
time: 2273ms
memory: 43384kb
input:
990 19 16 20 74 15 32 21 22 14 22 13 36 16 58 14 4 19 44 14 46 21 110 22 86 19 32 16 22 19 17 12 28 20 25 20 59 22 65 21 52 13 32 18 48 14 35 19 37 19 23 21 21 22 90 22 72 21 101 17 20 18 46 21 3 7 12 12 36 16 49 14 15 13 17 20 42 13 42 13 11 22 47 15 22 22 32 19 39 19 65 21 98 19 3 16 24 18 6 22 63...
output:
393168729 246435507 711223131 161825104 979987145 971749586 25952856 2012 726099192 449177299 36423651 633817565 948448065 655086320 599308309 200783520 73244890 494204020 502991859 971176215 490633490 493983396 970265909 703034171 617628639 906119212 329471797 918718406 613644638 276565385 62885054...
result:
ok 990 lines
Test #3:
score: 0
Accepted
time: 2246ms
memory: 43476kb
input:
1000 359 358 370 368 428 429 315 312 405 402 455 453 387 384 385 385 339 340 478 475 439 439 301 302 325 322 457 457 394 393 326 324 431 428 338 336 377 376 324 322 412 413 430 430 317 318 361 361 382 381 498 495 353 351 360 361 426 427 455 452 383 382 470 470 332 331 467 466 494 494 490 487 362 362...
output:
45924051 164071423 548365783 659118999 838332377 635378530 846181906 441908095 40677633 401855064 269095899 404527990 415178598 151295576 196186312 881879915 764063734 328303695 316320167 305189158 752842487 128059020 807509283 679892319 891105784 174676386 511431817 725918523 632585428 122380016 38...
result:
ok 1000 lines
Test #4:
score: 0
Accepted
time: 2248ms
memory: 43316kb
input:
1000 414 5000 403 5000 492 5000 426 4997 422 4999 487 4992 433 4992 458 229 463 231 485 4997 445 4995 428 4999 452 4997 500 4994 484 4994 478 4997 451 225 481 4997 409 4993 416 4994 434 4995 485 4995 488 4994 479 4993 415 4996 457 4998 455 5000 484 4997 495 5000 461 5000 440 4994 467 233 478 4992 49...
output:
898775462 391699513 957397551 372004457 171494594 714422938 494882661 316538268 160292807 966868808 973353968 323915672 233988599 488329134 555876530 831872802 975484650 403590785 786688734 764230002 810440283 909509258 449810241 674593949 674793384 569468973 335196435 845894970 413891292 360114865 ...
result:
ok 1000 lines
Test #5:
score: 0
Accepted
time: 2241ms
memory: 43468kb
input:
1000 42 4150 38 529 449 3064 148 1194 225 608 395 261 67 2206 330 1412 442 280 323 4577 114 4578 491 2097 353 1908 104 1457 89 1228 224 63 463 569 357 4108 152 712 285 799 78 4320 343 2187 65 2573 276 1142 232 3251 119 4312 16 935 290 4153 200 2781 188 3692 145 1163 130 776 10 2395 234 4243 262 2781...
output:
313427725 736474183 167778171 483921125 249504291 426630218 640470271 236628570 456175617 133833658 195947577 400554114 32836731 558464694 62988677 390084793 364950769 226938354 555295458 717294565 781468876 970963159 768349275 744743281 310944980 647144599 394870773 919388235 730448114 609516618 62...
result:
ok 1000 lines
Test #6:
score: 0
Accepted
time: 2291ms
memory: 43388kb
input:
1000 256 4996 196 4995 492 386 499 222 499 66 494 129 128 4993 270 4994 498 359 496 308 331 4998 492 372 343 4995 493 189 493 195 494 438 486 4994 493 24 284 4994 500 119 110 4994 493 165 154 4999 176 4999 494 363 12 4998 498 275 385 4999 492 4998 177 4991 494 431 240 4999 492 403 496 246 494 201 49...
output:
651622739 399224728 554375882 39626944 455527272 645049492 989512905 801140014 179099678 60034938 215400726 861168462 696989938 137201040 224649754 945947510 790765487 758221383 692666511 551139017 324852642 861917215 645845740 637323638 934514098 239500800 730940831 860972302 354671366 893747329 64...
result:
ok 1000 lines