QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #126559 | #618. 多项式乘法 | SoyTony# | 0 | 143ms | 25188kb | C++14 | 2.9kb | 2023-07-18 17:11:22 | 2023-07-18 17:11:24 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxn=(1<<20)+10;
inline int read(){
int x=0,w=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
return x*w;
}
inline int q_pow(int A,int B,int P){
int res=1;
while(B){
if(B&1) res=1ll*res*A%P;
A=1ll*A*A%P;
B>>=1;
}
return res;
}
inline ll exgcd(ll A,ll B,ll &X,ll &Y){
if(!B){
X=1,Y=0;
return A;
}
ll D=exgcd(B,A%B,Y,X);
Y-=A/B*X;
return D;
}
int rev[maxn];
int base,w[maxn];
struct Poly{
const static int g=3;
int deg;
vector<ull> f;
ull& operator[](const int &i){return f[i];}
ull operator[](const int &i)const{return f[i];}
inline void set(int L){deg=L;f.resize(L);}
inline void clear(int L,int R){for(int i=L;i<=R;++i)f[i]=0;}
inline void output(int L){for(int i=0;i<L;++i)printf("%llu ",f[i]);printf("\n");}
inline void NTT(int L,bool type,int P){
set(L);
int inv_g=q_pow(g,P-2,P);
for(int i=1;i<L;++i){
rev[i]=(rev[i>>1]>>1)+(i&1?L>>1:0);
if(i<rev[i]) swap(f[i],f[rev[i]]);
}
for(int d=1;d<L;d<<=1){
base=q_pow(type?g:inv_g,(P-1)/(2*d),P);
w[0]=1;
for(int i=1;i<d;++i) w[i]=1ll*w[i-1]*base%P;
for(int i=0;i<L;i+=d<<1){
for(int j=0;j<d;++j){
ull x=f[i+j],y=f[i+d+j]*w[j]%P;
f[i+j]=x+y,f[i+d+j]=x-y+P;
}
}
}
for(int i=0;i<L;++i) f[i]%=P;
if(!type){
int inv_L=q_pow(L,P-2,P);
for(int i=0;i<L;++i) f[i]=f[i]*inv_L%P;
}
}
}F,G,H[3];
int n,m,p;
int a[maxn],b[maxn],c[maxn];
ll mod[3]={998244353,1004535809,469762049};
inline int solve(ll A,ll B,ll C){
ll X1,Y1,X2,Y2;
exgcd(mod[0],mod[1],X1,Y1);
X1=(X1%mod[1]+mod[1])%mod[1];
X1=((B-A)%mod[1]+mod[1])%mod[1]*X1%mod[1];
exgcd(mod[0]*mod[1],mod[2],X2,Y2);
X2=(X2%mod[2]+mod[2])%mod[2];
X2=((C-(X1*mod[0]+A)%(mod[0]*mod[1]))%mod[2]+mod[2])%mod[2]*X2%mod[2];
return X2*mod[0]*mod[1]+X1*mod[0]+A;
}
int main(){
n=read(),m=read();
for(int i=0;i<=n;++i) a[i]=read();
for(int i=0;i<=m;++i) b[i]=read();
int L=1;
while(L<n+m+1) L<<=1;
F.set(L),G.set(L);
for(int i=0;i<=2;++i){
H[i].set(L);
F.clear(0,L-1),G.clear(0,L-1);
for(int j=0;j<=n;++j) F[j]=a[j];
for(int j=0;j<=m;++j) G[j]=b[j];
F.NTT(L,1,mod[i]),G.NTT(L,1,mod[i]);
for(int j=0;j<L;++j) H[i][j]=F[j]*G[j]%mod[i];
H[i].NTT(L,0,mod[i]);
}
for(int i=0;i<=n+m;++i) c[i]=solve((ll)H[0][i],(ll)H[1][i],(ll)H[2][i]);
for(int i=0;i<=n+m;++i) printf("%d ",c[i]);
printf("\n");
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 9936kb
input:
96 96 600395131 184265451 942971382 534262851 830366882 542271170 294355449 501371170 797809599 964826049 276651245 375755165 662619442 941920605 328216963 507795473 460271147 874920847 818231910 156789488 590591583 732194508 793983630 93566697 836155866 305319153 432040686 621119061 835023373 57138...
output:
-1664720001 -1434804583 -35971679 -278352516 658919398 -576798870 1465301786 269601564 796599 457095320 1535079143 1629926720 -1787757281 219989181 -1211055547 1170304175 -117444897 102100099 357200012 205546155 1323730151 1636191101 310924154 -814079849 -628775485 -200707432 -10921396 1211159547 -8...
result:
wrong answer 1st numbers differ - expected: '683858396', found: '-1664720001'
Test #2:
score: 0
Wrong Answer
time: 5ms
memory: 10120kb
input:
4992 4994 471194390 313639917 705341086 119536186 430124603 244978845 185588341 13731324 707132801 88167972 927324568 846658454 523684029 5133605 767200778 502476309 539772401 778154025 266136872 183516351 260704325 49303370 475056182 928574546 740424153 277920667 708439854 746983628 839491869 53579...
output:
-1848709536 927322114 1082541767 -624462630 -123368418 433459032 -2035922546 1531277535 489902848 1504055400 762760299 -1413866630 -478869365 -2144918386 1652055044 837054745 1691186842 -9183279 -2145509122 -1423452948 2099125957 -1501827195 1124613544 1818059924 -1656372109 -614505299 -1278038049 -...
result:
wrong answer 1st numbers differ - expected: '700935456', found: '-1848709536'
Test #3:
score: 0
Wrong Answer
time: 38ms
memory: 12384kb
input:
29995 29992 417238081 53580806 733071257 224121793 786137422 127072245 129083351 988357079 246853229 150935424 596994106 975796660 838029970 619117898 328485797 948485083 574261409 79312345 596346086 489787404 929520168 515647000 211731260 50868568 811515357 428215135 498099163 644485329 802849075 3...
output:
356678907 1048727941 1132558915 -387293730 1380932827 858823701 458272044 -852512117 799532989 -1383397031 -1016143144 1260860015 -363942122 -1655446614 -1137290510 -909997097 -672958756 -50271061 -121786704 41596007 1024056221 -2020179343 1938062947 -1139325847 71860621 -1308181211 607695653 -62979...
result:
wrong answer 1st numbers differ - expected: '115270920', found: '356678907'
Test #4:
score: 0
Wrong Answer
time: 143ms
memory: 25188kb
input:
100000 99993 812398607 947396010 797321381 883949986 56052416 586258761 193247973 611124334 773505112 142179482 565466227 140875825 79890768 893500101 553768089 648879319 480419657 915530184 799329430 494818755 793895824 851865180 459534006 259473419 610037701 472768430 868914058 887444584 588850309...
output:
-308582505 1483972887 -903808887 -2053146096 2061484322 -1533740688 -826925276 1768916919 -572660470 -396304970 44397362 -2097467110 657123341 -871036500 -1514689947 -1422532792 475861143 -1676928366 1138929890 -1394806551 -2049755933 -1458935765 -1773598959 1167532467 -442731785 -1571784397 1356858...
result:
wrong answer 1st numbers differ - expected: '821875273', found: '-308582505'
Test #5:
score: 0
Runtime Error
input:
999993 999994 388529697 811245378 165909114 295553883 667981275 78502012 400874009 139394758 249494489 4636487 997712665 259780805 431039016 716944209 709300152 356513646 823185021 699568300 650937921 859190797 899514799 785648601 933470757 627225124 349752104 471458923 456404256 48134357 315599086 ...