QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#75614 | #4922. 生活在对角线下 | 4182_543_731 | 50 | 1114ms | 85316kb | C++ | 5.4kb | 2023-02-05 22:06:30 | 2023-02-05 22:06:33 |
Judging History
answer
#include<cstdio>
using namespace std;
#define N 530001
#define M 11
#define mod 998244353
int pw(int a,int p){int as=1;while(p){if(p&1)as=1ll*as*a%mod;a=1ll*a*a%mod;p>>=1;}return as;}
int fr[N],ifr[N],gr[2][N*2],rev[N*2];
void init(int l=19)
{
fr[0]=1;for(int i=1;i<=1<<l;i++)fr[i]=1ll*i*fr[i-1]%mod;
ifr[1<<l]=pw(fr[1<<l],mod-2);for(int i=1<<l;i>=1;i--)ifr[i-1]=1ll*i*ifr[i]%mod;
for(int s=2;s<=1<<l;s<<=1)for(int i=1;i<s;i++)rev[i+s]=(rev[(i>>1)+s]>>1)+((i&1)*(s>>1));
for(int t=0;t<2;t++)
for(int s=2;s<=1<<l;s<<=1)
{
int tp=pw(3,(mod-1)/s);
if(!t)tp=pw(tp,mod-2);
int vl=1;
for(int i=0;i<s;i++)gr[t][s+i]=vl,vl=1ll*vl*tp%mod;
}
}
int f[N],g[N],ntt[N];
void dft(int s,int *a,int t)
{
for(int i=0;i<s;i++)ntt[rev[i+s]]=a[i];
for(int l=2;l<=s;l<<=1)
for(int i=0;i<s;i+=l)
for(int j=0;j<l>>1;j++)
{
int v1=ntt[i+j],v2=1ll*ntt[i+j+(l>>1)]*gr[t][j+l]%mod;
ntt[i+j]=(v1+v2)%mod;ntt[i+j+(l>>1)]=(v1+mod-v2)%mod;
}
int tp=t?1:pw(s,mod-2);
for(int i=0;i<s;i++)a[i]=1ll*ntt[i]*tp%mod;
}
void polyinv(int n,int *s,int *t)
{
if(n==1){t[0]=pw(s[0],mod-2);return;}
polyinv((n+1)>>1,s,t);
int l=1;while(l<=n*2+4)l<<=1;
for(int i=0;i<l;i++)f[i]=g[i]=0;
for(int i=0;i<n;i++)f[i]=s[i],g[i]=t[i];
dft(l,f,1);dft(l,g,1);for(int i=0;i<l;i++)f[i]=1ll*g[i]*(2+mod-1ll*f[i]*g[i]%mod)%mod;
dft(l,f,0);
for(int i=0;i<n;i++)t[i]=f[i];
}
int cl[N],ls[M][N],vl[M][N],fi[M][N],tp[N],rs[N],iri[N],ri[N],c[M][M];
void solve_cl(int n,int p,int q)
{
for(int i=0;i<=10;i++)c[i][0]=c[i][i]=1;
for(int i=2;i<=10;i++)for(int j=1;j<i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
int l=1;while(l<=n*4+3)l<<=1;
cl[0]=1;for(int i=1;i<=n;i++)cl[i]=1ll*cl[i-1]*(4*i-2)%mod*pw(i+1,mod-2)%mod;
for(int i=0;i<=n;i++)rs[i]=cl[i];
dft(l,rs,1);
for(int a=0;a<=p;a++)for(int b=0;b<=q;b++)
{
//ls*rs
for(int i=0;i<=n;i++)ls[a*(q+1)+b][i]=1ll*cl[i]*pw(i+1,a)%mod*pw(i,b)%mod;
dft(l,ls[a*(q+1)+b],1);
for(int i=0;i<l;i++)ls[a*(q+1)+b][i]=1ll*ls[a*(q+1)+b][i]*rs[i]%mod;
//fi
for(int i=0;i<=n;i++)fi[a*(q+1)+b][i]=1ll*cl[i]*pw(i,a)%mod*pw(i+1,b)%mod;
dft(l,fi[a*(q+1)+b],1);
}
// / 1-ls_0*x
dft(l,ls[0],0);
ri[0]=1;for(int i=1;i<=n;i++)ri[i]=mod-ls[0][i-1];
polyinv(n+1,ri,iri);
dft(l,iri,1);
dft(l,ls[0],1);
for(int a=0;a<=p;a++)for(int b=0;b<=q;b++)
{
for(int i=0;i<l;i++)tp[i]=0;
//vl_(a,b)=x*(vl_(a,b)+f_i)*ls+c
if(a+b==0)
{
for(int i=0;i<=n;i++)tp[i]=cl[i];
dft(l,tp,1);
}
for(int a1=0;a1<=a;a1++)for(int b1=0;b1<=b;b1++)
for(int i=0;i<l;i++)tp[i]=(tp[i]+1ll*c[a][a1]*c[b][b1]*gr[1][l+i]%mod*
(vl[a1*(q+1)+b1][i]+fi[a1*(q+1)+b1][i])%mod*ls[(a-a1)*(q+1)+(b-b1)][i])%mod;
for(int i=0;i<l;i++)tp[i]=1ll*tp[i]*iri[i]%mod;
dft(l,tp,0);
for(int i=0;i<=n;i++)vl[a*(q+1)+b][i]=tp[i];
dft(l,vl[a*(q+1)+b],1);
}
}
int ls2[M][N],t1[N];
void solve_c2(int n,int p,int q,int d)
{
int l=1;while(l<=n*4+3)l<<=1;
for(int a=0;a<=p;a++)for(int b=0;b<=q;b++)
{
for(int i=0;i<=n;i++)ls2[a*(q+1)+b][i]=1ll*(i?1ll*fr[i*2-1]*ifr[i]%mod*ifr[i-1]%mod:1)*pw(i,a+b)%mod;
dft(l,ls2[a*(q+1)+b],1);
}
for(int a=p;a>=0;a--)for(int b=q;b>=0;b--)
{
for(int i=0;i<l;i++)vl[a*(q+1)+b][i]=1ll*vl[a*(q+1)+b][i]*ls2[0][i]%mod;
for(int a1=0;a1<=a;a1++)for(int b1=0;b1<=b;b1++)if(a1+b1<a+b)
for(int i=0;i<l;i++)vl[a*(q+1)+b][i]=(vl[a*(q+1)+b][i]+1ll*c[a][a1]*c[b][b1]*
vl[a1*(q+1)+b1][i]%mod*ls2[(a-a1)*(q+1)+(b-b1)][i]%mod)%mod;
}
for(int i=0;i<=n;i++)t1[i]=i?1ll*fr[2*i+d-1]*ifr[i+d-1]%mod*ifr[i]%mod:1;
dft(l,t1,1);
for(int a=p;a>=0;a--)for(int b=q;b>=0;b--)
{
for(int i=0;i<l;i++)vl[a*(q+1)+b][i]=1ll*vl[a*(q+1)+b][i]*t1[i]%mod;
dft(l,vl[a*(q+1)+b],0);
}
}
int al[M][N],s1[M][M],t2[N];
void solve_a1(int n,int p,int q,int c)
{
int l=1;while(l<=n*2+3)l<<=1;
for(int i=0;i<=n;i++)t2[i]=1ll*fr[2*i+c]*ifr[i+c]%mod*ifr[i]%mod;
dft(l,t2,1);
for(int a=0;a<=p;a++)for(int b=0;b<=q;b++)
{
for(int i=0;i<=n;i++)al[a*(q+1)+b][i]=1ll*fr[i*2]*ifr[i]%mod*ifr[i]%mod*pw(i,a+b)%mod;
dft(l,al[a*(q+1)+b],1);
for(int i=0;i<l;i++)al[a*(q+1)+b][i]=1ll*al[a*(q+1)+b][i]*t2[i]%mod;
dft(l,al[a*(q+1)+b],0);
}
s1[0][0]=1;
for(int i=1;i<=10;i++)for(int j=1;j<=i;j++)s1[i][j]=1ll*j*(s1[i-1][j]+s1[i-1][j-1])%mod;
for(int i=0;i<=n;i++)
for(int a=0;a<=p&&a<=i;a++)for(int b=0;b<=q&&b<=i+c;b++)
{
int si=1ll*ifr[a]%mod*ifr[b]%mod*ifr[i-a]%mod*ifr[i+c-b]%mod*fr[i*2+c]%mod;
if(a<i)si=(si+1ll*ifr[a]%mod*ifr[b]%mod*ifr[i-a-1]%mod*ifr[i+c-b]%mod*fr[i*2+c]%mod*ifr[a+b+1]%mod*fr[a+b])%mod;
if(b<i+c)si=(si+1ll*ifr[a]%mod*ifr[b]%mod*ifr[i-a]%mod*ifr[i+c-b-1]%mod*fr[i*2+c]%mod*ifr[a+b+1]%mod*fr[a+b])%mod;
for(int a2=a;a2<=p;a2++)for(int b2=b;b2<=q;b2++)
al[a2*(q+1)+b2][i]=(al[a2*(q+1)+b2][i]+1ll*s1[a2][a]*s1[b2][b]*si)%mod;
}
}
int T,d,p,q,n,fg,v[M][M],m;
int main()
{
scanf("%d%d%d%d%d",&T,&d,&p,&q,&n);
init();
if(d<0)p^=q^=p^=q,d*=-1,fg=1;
solve_cl(n,p,q);
solve_c2(n,p,q,d);
if(fg)solve_a1(n,p,q,d);
while(T--)
if(fg)
{
int as=0;
scanf("%*d%d",&m);
for(int i=0;i<=q;i++)for(int j=0;j<=p;j++)scanf("%d",&v[j][i]);
for(int i=0;i<=p;i++)for(int j=0;j<=q;j++)as=(as+1ll*v[i][j]*(al[i*(q+1)+j][m]+mod-vl[i*(q+1)+j][m]))%mod;
printf("%d\n",as);
}
else
{
int as=0;
scanf("%d%*d",&m);
for(int i=0;i<=p;i++)for(int j=0;j<=q;j++)scanf("%d",&v[i][j]);
for(int i=0;i<=p;i++)for(int j=0;j<=q;j++)as=(as+1ll*v[i][j]*vl[i*(q+1)+j][m])%mod;
printf("%d\n",as);
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 1
Accepted
Test #1:
score: 1
Accepted
time: 24ms
memory: 24952kb
input:
1 -10 1 2 1000 825 815 107973512 400177523 812303207 164088430 603506669 337780072
output:
360076089
result:
ok 1 number(s): "360076089"
Test #2:
score: 0
Accepted
time: 22ms
memory: 25200kb
input:
1 424 1 4 576 130 554 926445673 393820912 634481616 292175028 733650737 100427548 899689095 876811717 849191704 696040532
output:
564712546
result:
ok 1 number(s): "564712546"
Test #3:
score: 0
Accepted
time: 28ms
memory: 22916kb
input:
1 -171 2 1 1000 805 634 250066876 719653007 284194184 531322789 491311782 185842441
output:
910556244
result:
ok 1 number(s): "910556244"
Test #4:
score: 0
Accepted
time: 24ms
memory: 25196kb
input:
1 11 4 1 989 142 153 581558550 138798754 575233123 788754497 582314564 303591688 635874631 658261955 615116681 498307457
output:
918405181
result:
ok 1 number(s): "918405181"
Test #5:
score: 0
Accepted
time: 26ms
memory: 26988kb
input:
1 -87 1 2 1000 164 77 264180617 338145439 610918500 800846696 216126209 112962819
output:
629819261
result:
ok 1 number(s): "629819261"
Subtask #2:
score: 9
Accepted
Dependency #1:
100%
Accepted
Test #6:
score: 9
Accepted
time: 115ms
memory: 26956kb
input:
100000 -99 2 1 1000 712 613 238230707 820405654 473765646 826816733 751513618 421153458 209 110 22075351 398854663 148159396 487281124 972932017 200517786 383 284 22252771 205525630 491328752 607545155 561318911 135661425 929 830 156478040 89922795 380802607 32081978 898588032 110586958 956 857 4206...
output:
863094157 570366074 281608243 247495628 396961441 855444791 694374848 782506902 280202079 688077364 610676536 115373962 360154110 834242083 887647721 164293717 759683961 710870451 213441970 863772654 514218158 532711794 558875294 421795761 517787006 458381459 506983637 742686106 435175768 111255264 ...
result:
ok 100000 numbers
Test #7:
score: 0
Accepted
time: 127ms
memory: 27040kb
input:
100000 252 3 1 748 130 382 311369319 709099006 49474431 724072531 761415026 251406187 389170658 169808960 581 833 89779535 938252574 504798466 677842435 654289171 763708659 719082912 762770851 691 943 571693157 187035992 300995260 403041189 726726538 63983502 814000657 315732021 121 373 339102104 42...
output:
516270157 614211606 655396807 981733406 752565578 312973289 850750616 826813023 753739511 227580123 199177890 403714939 559334967 370464926 363937285 583678656 239132195 834163477 111915553 68813179 875627540 299872127 660063389 31474925 464946255 125818391 645016505 267670615 440441568 356463850 84...
result:
ok 100000 numbers
Test #8:
score: 0
Accepted
time: 157ms
memory: 27148kb
input:
100000 195 2 2 805 325 520 266481322 663615421 428019284 968378746 158386978 211891009 161987045 142931644 790431809 621 816 756898302 952132541 196745128 424307295 926376261 130425563 604844618 645296808 252920984 60 255 873310227 887037637 787608776 98214115 355810775 242821836 537250851 650821017...
output:
922269244 757786754 400099571 332972619 780501723 469958234 540206804 924583388 519189002 566620024 244468115 73221163 663221021 159111716 451144022 658783977 656844692 831466434 186871631 60740257 542611012 773315130 755261907 193772041 628947709 363111530 452621670 349808610 264947076 342250907 16...
result:
ok 100000 numbers
Subtask #3:
score: 20
Accepted
Test #9:
score: 20
Accepted
time: 319ms
memory: 42772kb
input:
1 4683 0 0 95317 86560 91243 412303217
output:
952052072
result:
ok 1 number(s): "952052072"
Test #10:
score: 0
Accepted
time: 384ms
memory: 44844kb
input:
1 -24796 0 0 100000 93338 68542 849332154
output:
980840409
result:
ok 1 number(s): "980840409"
Test #11:
score: 0
Accepted
time: 162ms
memory: 33576kb
input:
1 40156 0 0 59844 39551 79707 566086447
output:
620552907
result:
ok 1 number(s): "620552907"
Test #12:
score: 0
Accepted
time: 381ms
memory: 44820kb
input:
1 -714 0 0 100000 72672 71958 817542139
output:
799272798
result:
ok 1 number(s): "799272798"
Test #13:
score: 0
Accepted
time: 325ms
memory: 42664kb
input:
1 23418 0 0 76582 6862 30280 442920403
output:
642352133
result:
ok 1 number(s): "642352133"
Test #14:
score: 0
Accepted
time: 160ms
memory: 33444kb
input:
1 42983 0 0 57017 42753 85736 380012689
output:
828068267
result:
ok 1 number(s): "828068267"
Test #15:
score: 0
Accepted
time: 363ms
memory: 46868kb
input:
1 -25448 0 0 100000 47466 22018 617788426
output:
485886943
result:
ok 1 number(s): "485886943"
Test #16:
score: 0
Accepted
time: 373ms
memory: 46860kb
input:
1 -35138 0 0 100000 49912 14774 472000456
output:
323681794
result:
ok 1 number(s): "323681794"
Test #17:
score: 0
Accepted
time: 325ms
memory: 43680kb
input:
1 15928 0 0 84072 57657 73585 31014982
output:
184096139
result:
ok 1 number(s): "184096139"
Test #18:
score: 0
Accepted
time: 332ms
memory: 43772kb
input:
1 5316 0 0 94684 36186 41502 601085246
output:
51887433
result:
ok 1 number(s): "51887433"
Subtask #4:
score: 20
Accepted
Dependency #3:
100%
Accepted
Test #19:
score: 20
Accepted
time: 189ms
memory: 34716kb
input:
100000 43925 0 0 56075 36770 80695 880793638 55133 99058 946571985 27169 71094 601132030 42027 85952 954509221 1261 45186 326012305 12030 55955 997023025 9914 53839 788665071 39921 83846 193760311 25774 69699 584278712 28428 72353 45133606 32564 76489 40466335 35483 79408 491164633 1587 45512 842380...
output:
332757564 673855662 612475468 823636534 480158617 642667251 497333900 509207503 811150980 417148607 922658720 104640134 806209587 173065009 605751740 862381731 38248058 821044620 841331399 289617079 251770008 141909273 16627417 373489864 231237810 941325561 178798279 674579054 924181592 61271475 964...
result:
ok 100000 numbers
Test #20:
score: 0
Accepted
time: 408ms
memory: 46448kb
input:
100000 -24410 0 0 100000 88811 64401 883320435 98680 74270 679694811 25736 1326 585801443 58045 33635 248117495 75671 51261 370680099 54439 30029 971994977 59364 34954 824527105 83366 58956 743467199 86814 62404 560320056 79263 54853 982330282 31352 6942 755041686 56396 31986 625187969 95451 71041 6...
output:
944753157 183242929 363439527 347484131 162238407 874219996 466587038 69445583 299052607 25676433 596600163 562511304 969440848 734888105 717978251 646284734 285785033 177137639 757127623 981404389 646133036 419072122 570786562 49543639 324434058 643959988 425580060 576826099 385768604 231992533 414...
result:
ok 100000 numbers
Test #21:
score: 0
Accepted
time: 385ms
memory: 46848kb
input:
100000 -5861 0 0 100000 16952 11091 854232561 61287 55426 808396787 36941 31080 498670332 78084 72223 125065027 77939 72078 113005933 66811 60950 561023395 8690 2829 85984152 86780 80919 73284065 24701 18840 962634657 49186 43325 820164989 13544 7683 181059009 82733 76872 475302128 59169 53308 30753...
output:
953252694 312702564 226453117 67575786 903898714 513740725 876463803 777825703 146006471 2374918 297784488 386629852 320437877 988885626 718795318 32469771 761373569 413225682 535374528 890489090 946876926 547336815 741402601 164218598 624314043 440338456 358510966 78123388 844278570 353784116 33016...
result:
ok 100000 numbers
Test #22:
score: 0
Accepted
time: 194ms
memory: 36548kb
input:
100000 36351 0 0 63649 63623 99974 215842464 38932 75283 281762844 36628 72979 412528519 32243 68594 274539771 12583 48934 35262820 58794 95145 584821840 55654 92005 405023451 54594 90945 121054191 13799 50150 945750972 3396 39747 123637787 24436 60787 60557209 28533 64884 16469063 62629 98980 97582...
output:
174547901 368722952 48857280 38439764 222892265 312334973 776332784 870332855 155759525 948664848 557524993 498142735 312543625 96578298 812380665 262256294 625974911 11727861 934671647 410990281 662266734 602386252 129790362 105856770 514479617 606174145 351070683 902755038 185658666 319441312 6292...
result:
ok 100000 numbers
Test #23:
score: 0
Accepted
time: 397ms
memory: 45572kb
input:
100000 -30740 0 0 100000 68807 38067 675336699 46303 15563 123039099 67930 37190 232230088 54579 23839 35352609 92730 61990 284529851 67176 36436 665212494 57299 26559 133796107 49959 19219 33773652 84236 53496 372759887 99484 68744 426876149 34577 3837 572112278 61585 30845 172184077 77857 47117 90...
output:
36920501 226235095 750211143 333187562 373628984 295265220 37657937 466124753 990905489 551665113 446537030 431018050 86173594 169742883 218477019 236694053 535757873 691309698 571533347 44799594 978410954 207318736 924231440 714349634 256005837 765738237 355457430 213887617 753194413 829442039 4620...
result:
ok 100000 numbers
Test #24:
score: 0
Accepted
time: 384ms
memory: 46144kb
input:
100000 -38460 0 0 100000 51513 13053 225553548 46939 8479 742237301 76548 38088 403832837 58372 19912 532371282 69056 30596 227486715 57631 19171 992007340 43442 4982 456446541 98517 60057 139482341 93593 55133 617856070 94670 56210 632588368 61305 22845 540079128 42989 4529 243030634 61305 22845 60...
output:
264377260 988347451 122980170 868000378 424450627 937049667 82203152 65434176 511951571 866041634 172830523 592267120 339840284 510003002 301057898 661439490 614715916 352897087 347380257 99947743 217323734 533045349 197971764 276536330 181518107 810369320 38076519 795663640 628535813 745310656 9165...
result:
ok 100000 numbers
Test #25:
score: 0
Accepted
time: 400ms
memory: 45824kb
input:
100000 -21781 0 0 100000 98045 76264 260148888 51675 29894 775592370 96562 74781 6673060 61291 39510 561247689 51571 29790 374708153 56745 34964 902344534 38026 16245 499287321 46349 24568 80542300 44223 22442 235391104 44474 22693 180934225 73722 51941 571180203 98775 76994 186933783 37624 15843 66...
output:
403860096 918023019 505862766 325574001 758856670 454849577 390589711 142177895 563486806 252645563 120628328 553587845 992851487 933771813 401873497 993790093 184884214 294133840 346874311 513672329 312442149 595232497 772328343 814181956 380438506 927087216 253560503 970622427 910857175 430512071 ...
result:
ok 100000 numbers
Subtask #5:
score: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Dependency #3:
100%
Accepted
Test #26:
score: 0
Time Limit Exceeded
input:
1 -40679 1 3 100000 75191 34512 321693501 896183087 224533692 282076683 38691763 630172019 273852722 127891101
output:
result:
Subtask #6:
score: 0
Time Limit Exceeded
Test #41:
score: 10
Accepted
time: 1114ms
memory: 85316kb
input:
100000 0 2 1 100000 48964 48964 666670967 90494987 74847122 615108201 29533064 582540229 14418 14418 391779909 223696706 701170191 885097597 551643398 25626747 81584 81584 951326734 520293397 13860946 896899117 821166399 282263457 76849 76849 598606953 879771697 930252135 671750715 673503431 3060699...
output:
513261452 727599133 935022075 486566245 581605882 190874624 492903919 212718785 390117408 13902475 85548183 635628561 482394025 962073695 362740677 938001783 889953951 725536236 308635636 699865601 901798869 464425652 743201170 92575030 846809630 169046922 528318328 181301191 961103497 451810607 792...
result:
ok 100000 numbers
Test #42:
score: -10
Time Limit Exceeded
input:
100000 0 4 1 100000 62874 62874 118183474 407193132 685767410 687439227 635193908 610100986 258734574 238431118 899478481 761001837 51740 51740 444395131 500444257 428937362 53260346 30808281 906820217 513141079 288839678 554203046 663643475 35914 35914 356034890 347998675 273353479 349503145 372514...
output:
result:
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
0%