QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#66637 | #5169. 夹娃娃 | Dual | 3 | 1184ms | 61224kb | C++ | 4.4kb | 2022-12-09 10:15:19 | 2022-12-09 10:15:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 17,V = 520,Lim = 7800; // V 和 Lim 都是是真实上界,没加 1 的那种
struct fastmod {
typedef unsigned long long u64;
typedef __uint128_t u128;
int m;
u64 b;
fastmod(int m) : m(m), b(((u128)1 << 64) / m) {}
int reduce(u64 a) {
u64 q = ((u128)a * b) >> 64;
int r = a - q * m;
return r < m ? r : r - m;
}
} Z(2);
int n,Q,P;
int a[N];
int b[N][V + 5],c[N][V + 5];
int F[N][V + 5]; // F_i 的系数表示
int fac[Lim + 5],ifac[Lim + 5],inv[Lim + 5];
int RLim;
inline int Add(const int &a,const int &b) { return (a + b >= P) ? (a + b - P) : (a + b);}
inline int Sub(const int &a,const int &b) { return (a < b) ? (a - b + P) : (a - b);}
inline void Plus(int &a,const int &b) { a += b;if(a >= P) a -= P;}
inline void Minus(int &a,const int &b) { a -= b;if(a < 0) a += P;}
inline int qpow(int a,int b) { int res = 1;while(b) {if(b&1) res = 1ll * res * a % P;a = 1ll * a * a % P;b >>= 1;} return res;}
inline void init(int n)
{
fac[0] = 1;
for(int i = 1;i <= n;i++) fac[i] = 1ll * fac[i - 1] * i % P;
inv[1] = 1;
for(int i = 2;i <= n;i++) inv[i] = 1ll * (P - P / i) * inv[P % i] % P;
ifac[0] = 1;
for(int i = 1;i <= n;i++) ifac[i] = 1ll * ifac[i - 1] * inv[i] % P;
}
inline void Exp(int *f,int *g,int n)
{
g[0] = 1;
for(int i = 1;i <= n;i++)
{
int res = 0;
for(int j = 1;j <= i;j++)
res = Add(res,Z.reduce(1ll * Z.reduce(1ll * j * f[j]) * g[i - j]) );
g[i] = Z.reduce(1ll * res * inv[i]);
}
}
inline void Do_F(int id)
{
static int lnf[V + 5];
memset(lnf,0,sizeof lnf);
for(int j = 1;j <= a[id];j++)
{
int tmp = b[id][j] * (c[id][j] + 1);
for(int k = 1;tmp * k <= V;k++)
// -x^{ij} / j
Minus(lnf[tmp * k],inv[k]);
tmp = b[id][j];
for(int k = 1;tmp * k <= V;k++)
Plus(lnf[tmp * k],inv[k]);
}
Exp(lnf,F[id],V);
}
int Ys[Lim + 5][N][V + 5]; // 前缀点值
int Pack[Lim + 5][Lim + 5];
inline void init_Largange(int n) // 1 - n + 1
{
static int f[Lim + 5],tmp[Lim + 5];
memset(f,0,sizeof f);
f[0] = 1;
for(int i = 1;i <= n + 1;i++)
{
for(int j = n + 1;j >= 1;j--)
f[j] = Z.reduce(1ll * f[j] * (P - i)),Plus(f[j],f[j - 1]);
f[0] = Z.reduce(1ll * f[0] * (P - i));
}
// printf("f: ");
// for(int i = 0;i <= n + 1;i++) printf("%d ",f[i]);
// printf("\n");
for(int i = 1;i <= n + 1;i++)
{
memcpy(tmp,f,sizeof f);
for(int j = 0;j <= n;j++)
tmp[j] = P - Z.reduce(1ll * tmp[j] * inv[i]),Minus(tmp[j + 1],tmp[j]);
int res = Z.reduce(1ll * ifac[i - 1] * ifac[n + 1 - i]);
if((n + 1 - i) & 1) res = P - res;
Pack[i][0] = Z.reduce(1ll * res * tmp[0]);
for(int j = 1;j <= n;j++)
Pack[i][j] = Add(Pack[i][j - 1] , Z.reduce(1ll * res * tmp[j]) );
}
// for(int j = 1;j <= n;j++) Plus(cst[j],cst[j - 1]);
}
int GetY(const string &S,int k,int X)
{
int res = 1;
for(int i = 1;i <= n;i++)
if(S[i - 1] == '0')
res = Z.reduce(1ll * res * Ys[X][i][0]);
else res = Z.reduce(1ll * res * Ys[X][i][k]);
return res;
}
int Solve(const string &S,int k,int m)
{
int res = 0;
for(int X = 1;X <= RLim + 1;X++)
Plus(res,Z.reduce(1ll * GetY(S,k,X) * Pack[X][m]));
return res;
}
int main()
{
// freopen("a.in","r",stdin);
// freopen("log.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> Q >> P;
Z = fastmod(P);
RLim = V * n;
for(int i = 1;i <= n;i++)
{
cin >> a[i];
for(int j = 1;j <= a[i];j++)
cin >> b[i][j] >> c[i][j];
}
init(RLim + 1);
for(int i = 1;i <= n;i++)
Do_F(i);
// for(int i = 1;i <= n;i++)
// {
// printf("F[%d]:",i);
// for(int j = 0;j <= 50;j++)
// printf("%d ",F[i][j]);
// printf("\n");
// }
// cout << "clock1 :" << 1.0 * clock() / CLOCKS_PER_SEC << endl;
for(int X = 1;X <= RLim + 1;X++) // 插值 1 - Lim + 1,0 不知道可撤销背包的正确性
{
for(int i = 1;i <= n;i++)
{
int nowx = qpow(X,V);
Ys[X][i][V] = Z.reduce(1ll * F[i][V] * nowx);
for(int j = V - 1;j >= 0;j--)
{
nowx = Z.reduce(1ll * nowx * inv[X]);
Ys[X][i][j] = Add(Ys[X][i][j + 1],Z.reduce(1ll * nowx * F[i][j]));
// printf("Ys[%d][%d][%d]=%d\n",X,i,j,Ys[X][i][j]);
}
}
}
// cout << "clock2 :" << 1.0 * clock() / CLOCKS_PER_SEC << endl;
init_Largange(RLim);
// cout << "clock3 :" << 1.0 * clock() / CLOCKS_PER_SEC << endl;
while(Q--)
{
string S;
int k,m;
cin >> S >> m >> k;
cout << Solve(S,k,m) << endl;
}
return 0;
}
详细
Subtask #1:
score: 3
Accepted
Test #1:
score: 3
Accepted
time: 2ms
memory: 23248kb
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: 87ms
memory: 29924kb
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: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Test #3:
score: 13
Accepted
time: 328ms
memory: 45828kb
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: 1184ms
memory: 61224kb
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: -13
Time Limit Exceeded
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:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
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:
993379058 496689529 866368587 797687294 481245176 481245176 39022588 269889529 552778235 769822588 331666941 99789529 903956470 112750588 756797435 519045176 870912000 361582588 594280447 494747647 597778941 178845176 435456000 493445999 461733882 308912117 271186941 496689529 919511294 85533882 894...
result:
Subtask #5:
score: 0
Skipped
Dependency #3:
0%
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Skipped
Dependency #6:
0%