QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#224641 | #5169. 夹娃娃 | hos_lyric# | 55 | 1950ms | 182792kb | C++14 | 6.5kb | 2023-10-23 06:54:05 | 2024-07-04 02:21:16 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
static constexpr unsigned M = M_;
unsigned x;
constexpr ModInt() : x(0U) {}
constexpr ModInt(unsigned x_) : x(x_ % M) {}
constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
ModInt pow(long long e) const {
if (e < 0) return inv().pow(-e);
ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
}
ModInt inv() const {
unsigned a = M, b = x; int y = 0, z = 1;
for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
assert(a == 1U); return ModInt(y);
}
ModInt operator+() const { return *this; }
ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
explicit operator bool() const { return x; }
bool operator==(const ModInt &a) const { return (x == a.x); }
bool operator!=(const ModInt &a) const { return (x != a.x); }
friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////
int N, Q, P;
vector<int> A;
vector<vector<int>> B, C;
vector<int> S, M, K;
template <unsigned MO> void run() {
using Mint = ModInt<MO>;
const int maxM = *max_element(M.begin(), M.end());
static Mint F[15][530];
memset(F, 0, sizeof(F));
for (int i = 0; i < N; ++i) {
F[i][0] = 1;
for (int j = 0; j < A[i]; ++j) {
// (1 - x^(b(c+1))) / (1 - x^b)
for (int k = maxM - B[i][j] * (C[i][j] + 1); k >= 0; --k) {
F[i][k + B[i][j] * (C[i][j] + 1)] -= F[i][k];
}
for (int k = 0; k <= maxM - B[i][j]; ++k) {
F[i][k + B[i][j]] += F[i][k];
}
}
// cerr<<"F["<<i<<"] = ";pv(F[i],F[i]+13);
}
vector<vector<int>> qss(maxM + 1);
for (int q = 0; q < Q; ++q) {
qss[min(K[q], maxM)].push_back(q);
}
static Mint want[53000][530];
vector<int> pop(1 << N, 0);
for (int i = 0; i < N; ++i) for (int h = 0; h < 1 << i; ++h) pop[h | 1 << i] = pop[h] + 1;
static Mint gss[1 << 15][530];
memset(gss, 0, sizeof(gss));
gss[0][0] = 1;
// int cost0=0,cost1=0;
for (int k = maxM; k >= 0; --k) {
// add [x^k]
for (int i = 0; i < N; ++i) {
const Mint f = F[i][k];
for (int h0 = 0; h0 < 1 << N; h0 += 2 << i) for (int h = h0; h < h0 + (1 << i); ++h) {
const int hh = h | 1 << i;
const int low = pop[hh] * k + pop[hh >> (i + 1)];
// cost0+=1;cost1+=max(maxM-low+1,0);
for (int l = low; l <= maxM; ++l) {
// gss[hh][l] += gss[h][l - k] * f;
gss[hh][l].x = (gss[hh][l].x + (Int)gss[h][l - k].x * f.x) % MO;
}
}
}
for (const int q : qss[k]) {
copy(gss[S[q]], gss[S[q]] + (maxM + 1), want[q]);
}
}
// cerr<<"cost0 = "<<cost0<<", cost1 = "<<cost1<<endl;
// 1 / (1 - x)
for (int h = 0; h < 1 << N; ++h) {
for (int k = 0; k <= maxM - 1; ++k) {
gss[h][k + 1] += gss[h][k];
}
}
for (int q = 0; q < Q; ++q) {
Mint ans = 0;
// cerr<<"want[q] = ";pv(want[q],want[q]+13);
const int h = (1 << N) - 1 - S[q];
for (int k = 0; k <= M[q]; ++k) {
ans += gss[h][M[q] - k] * want[q][k];
}
printf("%u\n", ans.x);
}
}
int main() {
char buf[20];
for (; ~scanf("%d%d%d", &N, &Q, &P); ) {
A.resize(N);
B.resize(N);
C.resize(N);
for (int i = 0; i < N; ++i) {
scanf("%d", &A[i]);
B[i].resize(A[i]);
C[i].resize(A[i]);
for (int j = 0; j < A[i]; ++j) {
scanf("%d%d", &B[i][j], &C[i][j]);
}
}
S.assign(Q, 0);
M.resize(Q);
K.resize(Q);
for (int q = 0; q < Q; ++q) {
scanf("%s%d%d", buf, &M[q], &K[q]);
for (int i = 0; i < N; ++i) {
S[q] |= (buf[i] - '0') << i;
}
}
if (P == 998244353) {
run<998244353>();
} else {
run<1'000'000'007>();
}
}
return 0;
}
詳細信息
Subtask #1:
score: 3
Accepted
Test #1:
score: 3
Accepted
time: 4ms
memory: 75600kb
input:
1 521 998244353 39 520 520 11 22 414 8 95 18 229 356 26 407 316 10 24 26 19 61 11 130 482 476 420 15 192 193 208 24 19 233 494 217 275 294 26 28 439 20 272 277 28 198 5 335 22 8 28 17 154 78 6 13 175 17 2 5 477 256 200 4 1 36 427 371 439 23 10 65 426 25 24 27 121 29 28 13 12 453 0 520 1 1 519 1 1 51...
output:
38813347 922143638 98254957 38813343 922143633 38813338 98254946 922143620 98254933 922143604 38813302 38813288 922143562 38813247 38813220 38813188 38813150 98254715 38813047 922143273 98254516 38812814 922142999 98254191 922142723 38812257 38812058 98253436 922141847 38811240 922141173 38810463 38...
result:
ok 521 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 77592kb
input:
2 1561 998244353 151 520 520 511 30 121 396 25 16 113 11 6 175 242 20 8 5 61 13 518 447 404 8 220 177 4 19 18 15 70 233 9 14 26 512 17 9 9 19 30 8 495 20 13 27 277 22 396 14 4 29 345 442 19 25 14 5 16 295 19 65 134 10 10 296 245 6 7 30 253 15 187 26 482 454 28 414 170 404 11 27 27 25 13 509 1 5 291 ...
output:
883965618 144348435 762074635 112296779 385763651 821718611 673974966 879750066 927942969 136450507 436584627 612945970 768262217 613885343 39304132 852224740 215596261 151746110 965953558 969833936 664053020 458247365 881060255 878484499 781573019 616944059 850325449 296113117 674829177 887392623 6...
result:
ok 1561 lines
Subtask #2:
score: 13
Accepted
Dependency #1:
100%
Accepted
Test #3:
score: 13
Accepted
time: 11ms
memory: 82004kb
input:
3 4160 998244353 444 520 520 26 332 29 183 25 479 175 14 13 16 1 447 2 293 4 20 64 472 491 11 21 259 75 22 390 401 8 508 405 3 137 4 15 154 164 1 484 13 257 14 44 20 7 13 26 15 26 432 14 9 478 24 18 10 22 28 8 21 260 25 431 22 7 6 20 26 8 27 239 19 1 134 2 322 16 225 6 42 517 6 197 407 268 500 433 5...
output:
516056999 990096150 497048298 345860798 899328070 577475723 191997503 533625761 516056999 863614705 652318084 514747110 811600228 92531482 136793394 218097588 352553395 821305819 739754364 569418540 402235631 844207347 78271439 896568337 516056999 243958673 201200148 634787992 552693501 893938722 98...
result:
ok 4160 lines
Test #4:
score: 0
Accepted
time: 15ms
memory: 89976kb
input:
4 8320 998244353 303 520 520 288 10 15 24 306 456 495 124 20 419 24 473 7 462 365 405 4 30 1 29 15 25 29 324 407 14 30 184 425 451 6 414 7 417 155 12 18 20 2 475 78 174 467 23 300 26 13 15 345 319 10 27 497 25 21 51 24 485 359 268 87 20 509 13 18 261 13 6 20 237 305 26 245 330 514 29 21 197 25 345 1...
output:
857239630 694514392 340827658 834331936 573150389 560202020 302111919 422193966 147386541 201821565 447255018 322990367 192787601 197802108 461775999 315804262 316164169 338416167 240429979 359914423 321666890 541700460 506123940 701447430 823947537 621301718 62107305 163486246 380210777 211911024 9...
result:
ok 8320 lines
Test #5:
score: 0
Accepted
time: 64ms
memory: 182748kb
input:
4 52099 998244353 103 520 520 12 485 23 1 337 514 374 486 210 29 29 1 19 299 3 11 11 22 282 14 12 9 341 286 18 501 3 3 29 364 264 477 22 6 434 14 11 117 22 8 30 268 22 28 10 12 311 58 14 15 234 177 17 238 71 64 14 1 396 23 492 4 1 13 6 8 197 4 7 27 11 370 19 242 12 13 20 185 432 399 24 32 2 516 36 4...
output:
51769626 700322830 226311543 862334239 622358370 748398901 344771107 59670026 558254404 668258250 91212841 493756321 360353830 36696310 321158867 563614481 998042994 565120563 709404804 783802088 511531306 396636746 513730575 451308648 594545675 544172685 900482622 791631384 368742309 537404993 6927...
result:
ok 52099 lines
Subtask #3:
score: 14
Accepted
Dependency #2:
100%
Accepted
Test #6:
score: 14
Accepted
time: 88ms
memory: 180532kb
input:
7 52099 998244353 375 520 520 5 295 315 14 25 329 20 137 280 8 286 20 23 15 1 2 21 48 2 16 11 481 18 3 343 18 75 26 103 449 190 270 451 241 15 18 16 142 8 105 159 446 418 15 76 24 384 23 17 514 504 20 497 18 15 367 11 268 425 449 15 456 8 308 517 468 17 6 8 308 22 1 4 465 14 125 434 111 28 384 22 31...
output:
749892128 0 0 0 0 0 260438093 290693060 0 448909491 0 219322656 387184158 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 619977128 447966638 0 681308080 0 0 681648223 0 0 214156868 691259433 912802497 929329058 63245351 0 944326280 86464571 0 0 815255897 146151793 0 0 0 0 0 863159042 312726953 980444251 0 600279...
result:
ok 52099 lines
Test #7:
score: 0
Accepted
time: 105ms
memory: 182776kb
input:
8 52099 998244353 40 520 520 460 30 231 518 11 249 12 19 4 393 288 9 15 27 285 59 19 26 211 6 379 410 422 405 380 375 456 371 319 27 26 402 140 24 70 20 271 312 319 29 368 310 16 456 9 291 13 508 26 65 5 22 401 3 365 127 211 3 17 98 24 290 26 171 409 28 17 9 516 93 2 18 24 25 181 2 6 141 315 520 520...
output:
0 121472646 0 0 868501509 0 0 0 0 311676707 0 0 0 0 0 0 708345252 0 0 0 0 186486401 0 0 467064132 0 0 154691791 0 0 0 0 0 0 0 798981714 0 0 733168043 733528284 0 0 0 80512352 0 235570507 0 0 0 0 78997839 0 0 452560485 0 0 0 0 46384876 0 0 433696320 653100986 0 299555135 0 593915472 0 0 534577853 0 0...
result:
ok 52099 lines
Test #8:
score: 0
Accepted
time: 110ms
memory: 182580kb
input:
8 52099 998244353 27 520 520 137 195 11 296 397 165 52 434 18 30 7 392 364 205 347 226 175 292 16 69 8 24 54 15 26 29 121 75 23 22 321 11 88 3 19 100 54 118 5 30 2 30 77 11 420 20 4 4 19 1 24 6 117 520 520 8 96 357 13 23 4 147 415 113 86 499 18 14 23 12 15 431 27 3 406 8 13 26 23 102 19 12 24 26 357...
output:
611640132 300436849 327055017 766720771 275032937 904593053 463655376 369893628 214854225 929700933 174664089 812989004 625111481 812138767 845347445 833479053 735408106 735408106 503061044 986829167 458414549 917511270 397433661 828381114 545635279 261016968 690895096 234181435 793843962 377062472 ...
result:
ok 52099 lines
Subtask #4:
score: 0
Time Limit Exceeded
Test #9:
score: 0
Time Limit Exceeded
input:
15 52099 998244353 1 9 3 1 9 4 1 9 2 1 8 10 1 4 4 1 3 1 1 2 5 1 4 9 1 1 4 1 9 4 1 7 6 1 1 6 1 2 5 1 5 2 1 3 5 101000000001010 516 1 010001001010101 520 2 000000101000001 519 2 101011111100011 518 1 010110001000111 520 2 000110111100111 516 1 000100101001011 519 3 000111001010011 518 1 00001110010111...
output:
result:
Subtask #5:
score: 25
Accepted
Dependency #3:
100%
Accepted
Test #15:
score: 25
Accepted
time: 1950ms
memory: 182628kb
input:
15 52099 998244353 187 520 520 21 25 475 247 297 180 3 22 17 13 8 362 153 23 203 492 444 270 7 17 12 27 30 5 316 281 441 11 518 34 10 23 12 403 213 467 351 22 178 8 54 37 28 22 29 209 209 25 16 286 447 7 6 25 334 14 25 29 304 9 347 26 63 199 470 72 25 151 29 289 38 3 484 16 202 28 410 25 1 16 25 6 1...
output:
201142254 985793518 564689787 837651171 952915437 762762080 897212365 485394694 151682224 355049473 991697782 935162062 569171609 820415101 307382351 656056448 129648294 453468980 525403207 592935067 213396919 885501164 267000229 922880031 692668969 196055884 417004259 335278083 351024493 143284895 ...
result:
ok 52099 lines
Test #16:
score: 0
Accepted
time: 1938ms
memory: 180608kb
input:
15 52099 998244353 147 520 520 2 5 2 5 1 5 16 5 8 5 8 5 4 5 4 5 4 5 2 5 4 5 2 5 8 5 2 5 8 5 4 5 16 5 8 5 2 5 4 5 16 5 4 5 1 5 4 5 2 5 4 5 4 5 8 5 8 5 1 5 16 5 1 5 2 5 2 5 16 5 8 5 1 5 2 5 16 5 1 5 16 5 4 5 8 5 2 5 4 5 16 5 4 5 2 5 8 5 8 5 1 5 4 5 16 5 4 5 4 5 2 5 4 5 2 5 2 5 1 5 8 5 4 5 16 5 8 5 2 5...
output:
242417177 440189754 889617603 872166379 495149640 410397532 183799467 284271642 567153945 819885956 936067343 97379760 591656668 809313699 337549710 743302501 750522784 760325366 729888829 154371602 870414451 492621070 841959842 937587879 518704893 551082366 51801361 87581241 46911456 641967497 2452...
result:
ok 52099 lines
Test #17:
score: 0
Accepted
time: 1814ms
memory: 182792kb
input:
15 52099 998244353 56 520 520 1 5 4 5 2 5 8 5 16 5 2 5 2 5 2 5 1 5 16 5 2 5 8 5 2 5 1 5 2 5 4 5 1 5 16 5 16 5 1 5 8 5 1 5 8 5 16 5 8 5 1 5 4 5 4 5 2 5 4 5 16 5 16 5 8 5 1 5 2 5 2 5 2 5 16 5 16 5 16 5 1 5 16 5 1 5 8 5 2 5 16 5 1 5 2 5 2 5 4 5 8 5 16 5 16 5 2 5 2 5 199 520 520 16 5 4 5 2 5 16 5 8 5 8 ...
output:
655514914 814949076 757709972 457383073 190861256 943066055 683365019 620023365 113342367 366236790 468534272 38507289 978444179 331515147 89203381 366707024 465727606 115760514 322816596 872589670 566974623 824662974 652567121 91850187 989609674 11616535 486994045 986455197 709337366 713384782 5428...
result:
ok 52099 lines
Test #18:
score: 0
Accepted
time: 784ms
memory: 182644kb
input:
14 52099 998244353 116 520 520 14 12 17 142 291 15 9 29 24 403 9 51 16 326 174 334 24 306 487 214 349 23 15 231 455 225 230 204 2 30 2 24 512 17 110 475 471 14 30 16 103 501 183 4 29 318 1 106 288 24 222 3 19 183 113 243 292 289 18 41 33 171 7 14 482 142 382 1 87 376 215 384 506 78 122 249 21 12 2 7...
output:
8371400 844306488 885156868 444566620 368294157 441091937 644142943 526182367 425264040 580334976 198436702 789421193 10493696 403876127 386807460 20311851 340533200 103448772 266752233 584259456 693866903 285081465 223535903 282713591 670411142 77966699 87636356 605820420 840821710 829639544 529904...
result:
ok 52099 lines
Test #19:
score: 0
Accepted
time: 372ms
memory: 180716kb
input:
13 52099 998244353 336 520 520 111 475 105 21 259 6 6 494 6 437 5 12 17 21 44 23 28 297 30 399 1 14 91 11 291 3 443 20 21 413 8 106 145 20 10 4 6 14 21 486 4 23 406 10 519 51 23 284 205 488 201 9 24 15 121 9 182 243 8 1 11 17 2 377 20 336 19 499 90 315 21 3 387 8 371 11 7 14 202 6 114 82 114 3 25 48...
output:
978898530 781859008 0 727762075 0 370868626 0 0 491054504 110691014 163646677 455857511 0 318488813 538388935 630014668 453220220 386981233 660702143 0 895630263 0 580231647 0 0 0 0 0 0 528281068 503934902 356945029 343373205 0 0 0 168756452 412241222 0 537181294 0 0 0 490347899 280674870 0 0 701148...
result:
ok 52099 lines
Test #20:
score: 0
Accepted
time: 1945ms
memory: 182652kb
input:
15 52099 998244353 370 520 520 256 22 2 87 142 59 338 17 489 450 3 56 21 22 497 29 6 18 248 286 19 29 427 6 286 367 116 25 27 3 469 28 24 27 30 453 127 22 108 24 2 30 160 262 41 325 22 39 6 7 151 26 236 505 224 25 10 500 241 22 90 24 308 376 303 436 4 337 68 29 14 87 489 316 227 255 121 16 391 363 2...
output:
432288070 651018473 862263277 275458172 219422514 748518338 903371000 291669367 616572740 86170696 2517068 674702278 985641600 130816407 681640370 452342456 935323386 9171509 873128820 396446302 803413024 188736584 756359993 202520176 961216817 566688437 444955439 416142168 755398657 924127646 95009...
result:
ok 52099 lines
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Skipped
Dependency #6:
0%