QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#718388 | #9493. 路径计数 | WrongAnswer_90 | 8 | 253ms | 117852kb | C++23 | 8.0kb | 2024-11-06 20:23:22 | 2024-11-06 20:23:27 |
Judging History
answer
#include<bits/stdc++.h>
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define ll long long
#define lll __int128
#define fi first
#define se second
#define e emplace
#define eb emplace_back
#define db double
#define ef emplace_front
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vll vector<ll>
#define vp vector<pii>
#define vt vector<tup>
#define all(x) x.begin(),x.end()
#define mp make_pair
#define FastI
#define FastO
//#define int ll
bool ST;
static const ll MOD=998244353,Phi=998244352,inv2=499122177,Root=3,iRoot=332748118;
static const ll inf=1073741823,Inf=4294967296,INF=4557430888798830399;
static const ld eps=1e-9,pi=3.1415926535;
char in[1<<20],*p1=in,*p2=in;
char out[1<<20],*p3=out;
using namespace std;
struct tup
{
int x,y,z;
tup(int X=0,int Y=0,int Z=0)
{x=X,y=Y,z=Z;}
inline bool operator <(const tup t)const
{return x<t.x||(x==t.x&&y<t.y)
||(x==t.x&&y==t.y&&z<t.z);}
};
#ifdef FastI
#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#endif
#ifdef FastO
#define putchar(x) (p3-out==1<<20?fwrite(out,1,1<<20,stdout),p3=out,0:0,*p3++=x)
#define puts(x) write(x,'\n')
#endif
namespace FastIO
{
template<typename T> inline void write(T x,char ch=' ')
{
if(is_same<char,T>::value)putchar(x);
else
{
if(x<0)x=-x,putchar('-');
static char st[40];
int top=0;
do st[top++]=x%10+'0',x/=10;while(x);
while(top)putchar(st[--top]);
}
ch!='~'?putchar(ch):0;
}
inline void write(const char*x,char ch=' ')
{
for(int i=0;x[i]!='\0';++i)putchar(x[i]);
ch!='~'?putchar(ch):0;
}
inline void read(char&s){do s=getchar();while(s=='\n'||s==' ');}
inline void read(char s[])
{
int len=0;char st;
do st=getchar();while(st=='\n'||st==' ');
s[++len]=st,st=getchar();
while(st!='\n'&&st!=' '&&st!='\r'&&st!='\0')s[++len]=st,st=getchar();
s[++len]='\0';
}
template<typename T> inline void read(T &s)
{
char ch=getchar();s=0;
while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
bool tf=(ch=='-'&&(ch=getchar()));
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
s=tf?-s:s;
}
inline void edl(){putchar('\n');}
template<typename T1,typename T2> inline void read(pair<T1,T2> &s){read(s.fi),read(s.se);}
template<typename T,typename...Args> inline void write(T x,Args...args){write(x,'~'),write(args...);}
template<typename T,typename...Args> inline void read(T&x,Args&...args){read(x),read(args...);}
#ifdef FastO
struct Writer{~Writer(){fwrite(out,1,p3-out,stdout);}}Writ;
#endif
}
using namespace FastIO;
namespace MTool
{
inline int Cadd(int a,int b){return (ll)a+b>=MOD?(ll)a+b-MOD:a+b;}
inline int Cdel(int a,int b){return a-b<0?a-b+MOD:a-b;}
inline int Cmul(int a,int b){return 1ll*a*b%MOD;}
inline int sqr(int a){return 1ll*a*a%MOD;}
inline void Madd(int&a,int b){a=((ll)a+b>=MOD?(ll)a+b-MOD:a+b);}
inline void Mdel(int&a,int b){a=(a-b<0?a-b+MOD:a-b);}
inline void Mmul(int&a,int b){a=1ll*a*b%MOD;}
inline int Cmod(int x){return (x%MOD+MOD)%MOD;}
inline void Mmod(int&x){x=(x%MOD+MOD)%MOD;}
template<typename T> inline bool Mmax(T&a,T b){return a<b?a=b,1:0;}
template<typename T> inline bool Mmin(T&a,T b){return a>b?a=b,1:0;}
template<typename...Args> inline void Madd(int&a,int b,Args...args){Madd(a,b),Madd(a,args...);}
template<typename...Args> inline void Mmul(int&a,int b,Args...args){Mmul(a,b),Mmul(a,args...);}
template<typename...Args> inline void Mdel(int&a,int b,Args...args){Mdel(a,b),Mdel(a,args...);}
template<typename...Args> inline int Cadd(int a,int b,Args...args){return Cadd(Cadd(a,b),args...);}
template<typename...Args> inline int Cmul(int a,int b,Args...args){return Cmul(Cmul(a,b),args...);}
template<typename...Args> inline int Cdel(int a,int b,Args...args){return Cdel(Cdel(a,b),args...);}
template<typename...Args,typename T> inline bool Mmax(T&a,T b,Args...args){return Mmax(a,b)|Mmax(a,args...);}
template<typename...Args,typename T> inline bool Mmin(T&a,T b,Args...args){return Mmin(a,b)|Mmin(a,args...);}
inline int power(int x,int y){int s=1;for(;y;y>>=1,Mmul(x,x))if(y&1)Mmul(s,x);return s;}
}
using namespace MTool;
namespace WrongAnswer_90
{
const int N=400000;
int fr[N+10],inv[N+10];
inline void init(int n=N)
{
fr[0]=inv[0]=1;
for(int i=1;i<=n;++i)fr[i]=Cmul(fr[i-1],i);
inv[n]=power(fr[n],MOD-2);
for(int i=n-1;i>0;--i)inv[i]=Cmul(inv[i+1],i+1);
}
int c,n,m,p;
int A[200010],B[200010],C[200010],D[200010],E[200010],F[200010];
namespace Poly
{
inline vi fix(vi A,int n){return A.resize(n),A;}
const int MAXN=400000;
int Shape,VBL,Invn[MAXN],R[MAXN<<1],Prt[MAXN<<1],P0[50010],P1[50010];
inline void init()
{
P0[0]=P1[0]=1,VBL=ceil(sqrt(MOD)),Invn[0]=1;
for(int i=1;i<MAXN;++i)Invn[i]=Cmul(Invn[i-1],i);
int tmp=power(Invn[MAXN-1],MOD-2);
for(int i=MAXN-1;i>=1;--i)Invn[i]=Cmul(tmp,Invn[i-1]),Mmul(tmp,i);
for(int i=1;i<=VBL;++i)P0[i]=Cmul(P0[i-1],Root);
for(int i=1;i<=VBL;++i)P1[i]=Cmul(P1[i-1],P0[VBL]);
}
inline int powerr(int x){return Cmul(P0[x%VBL],P1[x/VBL]);}
inline void NTT(vi&A,int n,int opt)
{
static ull B[MAXN<<1],iv;
A.resize(n);
for(int i=0;i<n;++i)B[i]=A[R[i]];
for(int mid=1;mid<n;mid<<=1)
{
for(int j=0;j<n;j+=mid<<1)
{
for(int k=j;k<j+mid;++k)
{
ull x=B[k],y=Prt[mid+k-j]*B[k+mid]%MOD;
B[k]=x+y,B[k+mid]=x+MOD-y;
}
}
}
if(opt)for(int i=0;i<n;++i)A[i]=B[i]%MOD;
else
{
reverse(B+1,B+n),iv=power(n,MOD-2);
for(int i=0;i<n;++i)A[i]=Cmul(B[i]%MOD,iv);
}
}
inline void init(int lim)
{
if(lim==Shape)return;
int n=lim/2;
for(int i=0;i<lim;++i)R[i]=(R[i>>1]>>1)|((i&1)?n:0);
for(int i=1;i<lim;i<<=1)
{
int wm=powerr((MOD-1)/(i<<1));Prt[i]=1;
for(int j=1;j<i;++j)Prt[i+j]=Cmul(Prt[i+j-1],wm);
}
Shape=lim;
}
inline vi FFT(vi A,vi B)
{
int n=A.size(),m=B.size(),N=1;
while(N<=n+m)N<<=1;
init(N),NTT(A,N,1),NTT(B,N,1);
for(int i=0;i<N;++i)A[i]=Cmul(A[i],B[i]);
return NTT(A,N,0),A.resize(n+m-1),A;
}
}
namespace BF
{
int f[5010][5010];
inline void solve()
{
f[0][0]=1;
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)Madd(f[i+1][j+1],Cmul(f[i][j],A[j]));
for(int j=0;j<=m;++j)Madd(f[i+1][j],Cmul(f[i][j],Cadd(B[i],C[j])));
for(int j=1;j<=m;++j)Madd(f[i+1][j-1],Cmul(f[i][j],D[j]));
}
int ans=0;
for(int i=0;i<=n;++i)for(int j=0;j<=m;++j)
Madd(ans,Cmul(f[i][j],E[i],F[j]));
write(ans);
}
}
namespace ac
{
inline void solve()
{
A[m]=B[n]=1;
for(int i=1;i<=m;++i)Mmul(A[i],A[i-1]);
for(int i=1;i<=n;++i)Mmul(B[i],B[i-1]);
vi X(n+1),Y(m+1);
for(int i=0;i<=n;++i)X[i]=inv[i];
Y[0]=F[0];
for(int i=1;i<=m;++i)Y[i]=Cmul(inv[i],A[i-1],F[i]);
vi Z=Poly::FFT(X,Y);
int ans=Cmul(Z[0],E[0]);
for(int i=1;i<=n;++i)Madd(ans,Cmul(fr[i],Z[i],E[i]));
write(ans);
}
}
void mian()
{
init();
Poly::init();
read(c,n,m,p);
for(int i=0;i<m;++i)read(A[i]);
for(int i=0;i<n;++i)read(B[i]);
for(int i=0;i<=m;++i)read(C[i]);
for(int i=1;i<=m;++i)read(D[i]);
for(int i=0;i<=n;++i)read(E[i]);
for(int i=0;i<=m;++i)read(F[i]);
if(c==1)return BF::solve();
if(c==2)return ac::solve();
}
inline void Mian()
{
int T=1;
// read(T);
while(T--)mian();
}
}
bool ED;
signed main()
{
// ios::sync_with_stdio(0);
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
double st=clock();
WrongAnswer_90::Mian();
double ed=clock();
cerr<<endl;
cerr<<"Time: "<<ed-st<<" ms\n";
cerr<<"Memory: "<<abs(&ST-&ED)/1024.0/1024.0<<" MB\n";
return 0;
}
详细
Subtask #1:
score: 3
Accepted
Test #1:
score: 3
Accepted
time: 232ms
memory: 116544kb
input:
1 5000 5000 998244353 121811167 379924090 361631583 174189813 559424693 889647308 193102812 469875055 32237660 96186933 624360154 404866088 859165067 748410791 926700198 368632735 476560636 798138824 17883437 712872225 448819400 33122704 572152288 627010263 336722521 775918346 465722630 681224329 60...
output:
698779876
result:
ok single line: '698779876 '
Test #2:
score: 3
Accepted
time: 220ms
memory: 117852kb
input:
1 4999 4919 998244353 380477138 780960797 787883474 484131625 121182688 933501638 947532778 257948759 108946829 468475856 5564419 677097370 766236309 678789875 533319074 885579006 769287005 710724535 260200529 599758240 380918586 216469888 78561030 325936496 189815268 268769489 232850763 937923688 9...
output:
475720945
result:
ok single line: '475720945 '
Test #3:
score: 3
Accepted
time: 253ms
memory: 117800kb
input:
1 4995 4997 998244353 267305461 291432119 107593765 530653184 893921215 15414240 991509792 601027626 313017049 827685069 650321853 385956762 140661695 303322469 142427516 910941336 265371405 731125266 512689773 723594553 552396112 379799950 43662480 666390792 938399292 144960568 817187890 428532063 ...
output:
568578871
result:
ok single line: '568578871 '
Subtask #2:
score: 5
Accepted
Test #4:
score: 5
Accepted
time: 43ms
memory: 34832kb
input:
2 200000 200000 998244353 903563506 433239074 632684755 970178226 831892753 932120646 157832416 517140217 296101978 998244343 850946564 2367119 708278025 376919151 752106478 994362560 806760771 672325565 9 958330492 343658496 153627310 330649130 983441587 829707074 135609242 706388812 325297147 4972...
output:
108905794
result:
ok single line: '108905794 '
Test #5:
score: 5
Accepted
time: 50ms
memory: 34244kb
input:
2 199910 194100 998244353 587911377 573048398 832688590 809066619 524442920 218487661 649170169 8 150333233 204150153 800582862 464558080 291668841 361834956 998244344 998244349 806341682 775965963 459031329 867640103 425129750 7 998244343 274941091 809744915 443910210 859200100 998244350 725497297 ...
output:
597176160
result:
ok single line: '597176160 '
Test #6:
score: 5
Accepted
time: 40ms
memory: 34224kb
input:
2 150810 200000 998244353 288330007 105173193 991831123 698131025 301828280 273289882 387551340 542768677 115972971 425381688 811911805 962095963 566257196 435928108 337873530 109252306 933737641 967531573 29209951 787608009 497111219 315932660 878605444 903737754 260092904 447237039 37123388 594371...
output:
78643368
result:
ok single line: '78643368 '
Subtask #3:
score: 0
Wrong Answer
Test #7:
score: 0
Wrong Answer
time: 16ms
memory: 20304kb
input:
3 200000 200000 998244353 493605813 622283646 579332647 528537957 211102509 336893985 106292723 166710741 443808575 180234697 744331593 252016663 693453924 975202110 519712748 174749950 250990381 584528219 619047448 641168296 914918741 785005029 433175528 400547992 845115512 278159630 227330862 6407...
output:
result:
wrong answer 1st lines differ - expected: '144815343', found: ''
Subtask #4:
score: 0
Wrong Answer
Dependency #2:
100%
Accepted
Test #11:
score: 0
Wrong Answer
time: 12ms
memory: 18252kb
input:
4 200000 200000 998244353 199752876 397435299 166254444 779278347 182416898 901682085 69090988 738092954 712758505 681482091 950425501 897402866 870967623 36849705 515322829 172446310 900429861 34423824 785446470 553333476 938968413 86270822 973639556 431435054 741273084 677434142 222677171 61928101...
output:
result:
wrong answer 1st lines differ - expected: '65201275', found: ''
Subtask #5:
score: 0
Skipped
Dependency #3:
0%
Subtask #6:
score: 0
Wrong Answer
Test #16:
score: 0
Wrong Answer
time: 19ms
memory: 20304kb
input:
6 200000 200000 998244353 401806059 107033001 530043262 862506025 263940497 48524969 232075248 849682830 420464058 64900333 394986647 954304290 957385577 86269798 579307969 896967626 230611640 527078096 39773429 402432856 495204529 272090833 100466767 562115973 196636941 736050044 580541546 81233872...
output:
result:
wrong answer 1st lines differ - expected: '562220526', found: ''
Subtask #7:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #18:
score: 0
Wrong Answer
time: 15ms
memory: 18264kb
input:
7 200000 20000 998244353 869285118 18064361 457499026 292378234 45941854 157946840 586178769 392380503 830348035 141601898 591275235 100919004 399285791 115436998 586990272 287976693 795031696 836945332 895793688 432697639 828280269 714678411 137052352 516420393 730089484 911809696 350536206 8175289...
output:
result:
wrong answer 1st lines differ - expected: '809172057', found: ''
Subtask #8:
score: 0
Skipped
Dependency #6:
0%
Subtask #9:
score: 0
Skipped
Dependency #5:
0%
Subtask #10:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #32:
score: 0
Wrong Answer
time: 4ms
memory: 20488kb
input:
10 100000 100000 856853193 287061150 779504426 21691247 494814415 381655016 536089292 240188530 458291018 332927950 428352746 351529999 258956585 651084688 268523951 338285674 719419445 165275422 367200319 35308342 563282834 763880581 117326555 284413760 207571906 703023023 622478929 212959189 34094...
output:
result:
wrong answer 1st lines differ - expected: '304611769', found: ''