QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#66858 | #5169. 夹娃娃 | Kostlin | 30 | 945ms | 458424kb | C++14 | 5.2kb | 2022-12-09 12:16:35 | 2022-12-09 12:16:38 |
Judging History
answer
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
#define fi first
#define sc second
#define mkp make_pair
#define pii pair<int,int>
typedef long long ll;
#define pll pair<ll,ll>
const int N=550,L=520,oo=1e9,mod=998244353,G=3,invG=(mod+1)/3;
inline int read() {
int x=0,flag=0;char ch=getchar();
while(ch<'0'||ch>'9') {flag|=(ch=='-');ch=getchar();}
while('0'<=ch&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return flag?-x:x;
}
inline int mx(int x,int y) {return x>y?x:y;}
inline int mn(int x,int y) {return x<y?x:y;}
inline void swp(int &x,int &y) {x^=y^=x^=y;}
inline int as(int x) {return x>0?x:-x;}
int n,q,m,f[N],g[N],sum[N],M[52105],dn[52105];
char s[N];
namespace POLY {
struct Po {
int f[N<<2];
}A,B,C;
inline int ksm(int a,int b=mod-2) {
int ans=1;
while(b) {
if(b&1) ans=1ll*ans*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return ans;
}
int tr[N<<2],gg[2][25][N<<2],lim;
unsigned long long F[N<<2];
inline void NTT(int*f,int lim,int op) {
for(int i=0;i<lim;++i)
if(i<tr[i]) swp(f[i],f[tr[i]]);
for(int i=0;i<lim;++i) F[i]=f[i];
for(int p=2,t=0;p<=lim;p<<=1,++t) {
int len=p>>1;
for(int k=0;k<lim;k+=p) {
int now;
for(int i=0;i<len;++i) {
now=1ll*F[k|i|len]*gg[op][t][i]%mod;
F[k|i|len]=F[k|i]-now+mod;
F[k|i]+=now;
}
}
if(t==4)
for(int i=0;i<lim;++i) F[i]%=mod;
}
for(int i=0;i<lim;++i) f[i]=F[i]%mod;
if(!op) {
int invn=ksm(lim);
for(int i=0;i<lim;++i) f[i]=1ll*f[i]*invn%mod;
}
}
inline void prep() {
lim=1;
while(lim<=2*L+1) lim<<=1;
for(int i=0;i<lim;++i) tr[i]=((tr[i>>1]>>1)|((i&1)?lim>>1:0));
}
inline Po operator *(Po x,Po y) {
NTT(x.f,lim,1); NTT(y.f,lim,1);
for(int i=0;i<lim;++i) x.f[i]=1ll*x.f[i]*y.f[i]%mod;
NTT(x.f,lim,0);
for(int i=L+1;i<lim;++i) x.f[i]=0;
return x;
}
Po H[20],P[(1<<15)+5],Ans[52105];
}using namespace POLY;
int val[(1<<15)+5],len[(1<<15)+5],kk[20],ans[52105];
vector< pii > qry[N];
int main() {
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
n=read();q=read();read();
for(int i=0;i<n;++i) {
m=read();
f[0]=1;
for(int j=1;j<=L;++j) f[j]=0;
int qaq=0;
for(int j=1,x,y;j<=m;++j) {
x=read();y=read();
qaq=mn(qaq+x*y,L+1);
sum[0]=1;
for(int p=1;p<=L;++p) {
sum[p]=f[p];
if(p>=x) sum[p]=(sum[p]+sum[p-x])%mod;
if(p>=x*(y+1)) sum[p]=(sum[p]-f[p-x*(y+1)]+mod)%mod;
g[p]=sum[p];
}
for(int p=1;p<=L;++p) f[p]=g[p];
}
kk[i]=qaq;
for(int j=0;j<=L;++j) H[i].f[j]=f[j];
}
for(int i=0,p=2;i<=20;++i,p<<=1) {
gg[0][i][0]=gg[1][i][0]=1;
gg[0][i][1]=ksm(invG,(mod-1)/p),
gg[1][i][1]=ksm(G,(mod-1)/p);
for(int j=2;j<=(L<<2);++j)
gg[0][i][j]=1ll*gg[0][i][j-1]*gg[0][i][1]%mod,
gg[1][i][j]=1ll*gg[1][i][j-1]*gg[1][i][1]%mod;
}
prep();
P[0].f[0]=1;
for(int i=1,pos;i<(1<<n);++i) {
pos=0;
for(int j=0;j<n;++j)
if((i>>j)&1) {
pos=j;
break;
}
P[i]=H[pos]*P[i^(1<<pos)];
pos=i;
while(pos) {
++len[i];
pos-=pos&-pos;
}
}
int maxn=0;
for(int i=1,S;i<=q;++i) {
scanf("%s",s);
M[i]=read();dn[i]=read();
S=0; bool fl=0;
for(int j=0;j<n;++j)
if(s[j]=='0') S|=(1<<j);
else {
if(kk[j]<dn[i]) {
fl=1;break;
}
}
if(fl) continue;
Ans[i]=P[S];
for(int j=1;j<=L;++j)
Ans[i].f[j]=(Ans[i].f[j-1]+Ans[i].f[j])%mod;
if(((1<<n)-1)^S) {
qry[dn[i]].push_back(mkp(((1<<n)-1)^S,i));
maxn=mx(maxn,dn[i]);
} else {
ans[i]=Ans[i].f[M[i]];
}
}
for(int V=1;V<=maxn;++V) {
for(int i=1;i<(1<<n);++i) {
val[i]=1;
for(int j=0;j<n;++j)
if((i>>j)&1)val[i]=1ll*val[i]*H[j].f[V-1]%mod;
if(len[i]&1) val[i]=(mod-val[i])%mod;
}
for(int i=(1<<n)-1;i>=1;--i) {
for(int t=(i-1)&i;;t=(t-1)&i) {
for(int p=(V-1)*len[i^t];p<=L;++p)
P[i].f[p]=(P[i].f[p]+1ll*P[t].f[p-(V-1)*len[i^t]]*val[i^t])%mod;
if(t==0) break;
}
}
for(auto&now:qry[V])
for(int j=0;j<=M[now.sc];++j)
ans[now.sc]=(ans[now.sc]+1ll*Ans[now.sc].f[j]*P[now.fi].f[M[now.sc]-j])%mod;
}
for(int i=1;i<=q;++i)
printf("%d\n",ans[i]);
return 0;
}
詳細信息
Subtask #1:
score: 3
Accepted
Test #1:
score: 3
Accepted
time: 4ms
memory: 13116kb
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: 8ms
memory: 19884kb
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: 25ms
memory: 42032kb
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: 44ms
memory: 81324kb
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: 249ms
memory: 453400kb
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: 523ms
memory: 456356kb
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: 945ms
memory: 458424kb
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: 872ms
memory: 455944kb
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: 0
Time Limit Exceeded
Dependency #3:
100%
Accepted
Test #15:
score: 0
Time Limit Exceeded
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:
result:
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Skipped
Dependency #6:
0%