QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#126561 | #618. 多项式乘法 | SoyTony# | 0 | 132ms | 41616kb | C++14 | 1.7kb | 2023-07-18 17:12:42 | 2023-07-18 17:12:45 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long double db;
typedef long long ll;
const int maxn=(1<<21)+10;
const db pi=acos(-1);
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;
}
struct Complex{
db a,b;
Complex()=default;
Complex(db a_,db b_):a(a_),b(b_){}
Complex operator+(const Complex&rhs)const{return Complex(a+rhs.a,b+rhs.b);}
Complex operator-(const Complex&rhs)const{return Complex(a-rhs.a,b-rhs.b);}
Complex operator*(const Complex&rhs)const{return Complex(a*rhs.a-b*rhs.b,a*rhs.b+b*rhs.a);}
}f[maxn],g[maxn],h[maxn],w[maxn];
int n,m,r[maxn];
inline void FFT(int L,Complex *f,bool type){
for(int i=1;i<L;++i){
r[i]=(r[i>>1]>>1)+(i&1?L>>1:0);
if(i<r[i]) swap(f[i],f[r[i]]);
}
for(int d=1;d<L;d<<=1){
Complex base=Complex(cos(pi/d),sin(pi/d));
if(!type) base.b=-base.b;
w[0]=Complex(1,0);
for(int i=1;i<d;++i) w[i]=w[i-1]*base;
for(int i=0;i<L;i+=(d<<1)){
for(int j=0;j<d;++j){
Complex x=f[i+j],y=w[j]*f[i+d+j];
f[i+j]=x+y,f[i+d+j]=x-y;
}
}
}
if(!type){
for(int i=0;i<L;++i) f[i].a/=L;
}
}
int main(){
n=read(),m=read();
for(int i=0;i<=n;++i) scanf("%Lf",&f[i].a);
for(int i=0;i<=m;++i) scanf("%Lf",&g[i].a);
int L=1;
while(L<=n+m) L<<=1;
FFT(L,f,1),FFT(L,g,1);
for(int i=0;i<L;++i) h[i]=f[i]*g[i];
FFT(L,h,0);
for(int i=0;i<=n+m;++i){
printf("%d ",(ll)(h[i].a+0.5));
}
printf("\n");
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 11804kb
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:
-1664722322 -1434806411 -35973433 -278353864 658917519 -576800235 1465300390 269600566 794467 457093840 1535077627 1629925679 -1787758908 219988205 -1211056616 1170303585 -117447424 102098274 357198264 205544853 1323728315 1636189890 310922998 -814080683 -628777561 -200708891 -10922811 1211158643 -8...
result:
wrong answer 1st numbers differ - expected: '683858396', found: '-1664722322'
Test #2:
score: 0
Wrong Answer
time: 4ms
memory: 20168kb
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:
-1848962368 927093674 1082312669 -624666866 -123597723 433254511 -2036126139 1531098368 489673876 1503850489 762555774 -1414046415 -479074289 -2145098899 1651875046 836899578 1690956838 -9388807 -2145714037 -1423633591 2098920375 -1502007869 1124432577 1817904487 -1656578145 -614686669 -1278219188 -...
result:
wrong answer 1st numbers differ - expected: '700935456', found: '-1848962368'
Test #3:
score: 0
Wrong Answer
time: 37ms
memory: 20332kb
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:
354997760 1047108503 1130940432 -388847813 1379313100 857268515 456717103 -854004500 797911826 -1384951519 -1017696351 1259368793 -365500808 -1656942860 -1138784811 -911427847 -674580825 -51828728 -123343059 40105540 1022497440 -2021672649 1936569422 -1140757327 70300106 -1309675010 606202527 -63122...
result:
wrong answer 1st numbers differ - expected: '115270920', found: '354997760'
Test #4:
score: 0
Wrong Answer
time: 132ms
memory: 41616kb
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:
-296608768 1496353711 -891439110 -2040387858 2073862177 -1520976988 -814162214 1782063160 -560300583 -383539052 57156203 -2084321487 669886004 -857885085 -1501542389 -1408996434 488224328 -1664162752 1151689142 -1381661620 -2036994146 -1445781781 -1760450469 1181068576 -429986870 -1558626443 1370007...
result:
wrong answer 1st numbers differ - expected: '821875273', found: '-296608768'
Test #5:
score: 0
Time Limit Exceeded
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 ...