题目
题目描述
请编程序把含有乘法运算的代数多项式表达式改写成不含乘法的代数多项式。为简化计算，特做以下约定：
(1) 代数多项式表达式中只涉及一个代数符号 a ；
(2) 含有乘法运算的代数多项式表达式都是两个不含乘法运算的代数多项式直接相乘的形式，而且这两个参加乘法的代数多项式都用圆括号括起来了。乘法用符号表示，不得省略。
(3) 常数项以外的各项都是 xa^ y 的形式，其中 x 为该项的系数，而 y 是该项的指数。 x = 1时，不得简写成 a^ y ，应写成1a^ y 。
而 y = 1时，不得简写成 xa ，应写成 xa^1。
输入输出格式
输入格式：
文件中每行存放一个含有乘法的代数多项式表达式。
输出格式：
每行输出一个问题的解。要求指数大的项不能出现在指数小的项之后，指数相同的项必须合并同类项。不允许出现不必要的空白字符。
输入输出样例
输入样例#1：
(5a^2+3a^1+2)*(4a^1+1)
(5a^1+1)* (5a^1+1)
输出样例#1：
20a^3+17a^2+11a^1+2
25a^2+10a^1+1
题解
看到题第一眼，就知道这是个暴力处理多项式然后用$FFT$搞就行了……
但是有许多坑点，比如输入字符串中没有*就什么也不输出题目就™不能讲清楚吗
因为这个WA了好几次，又因为只有一个数据点，每次都提示输出多了，我也看不了别人代码对一下……
最后在网上找了一个博客，试了几组数据都正确并且ta还不能处理没有括号的情况
看到ta的代码中有一行：
if(ppos == std::string::npos) continue;
这是干啥啊……似乎是判断有没有*？
然后加上就过了QAQ这种垃圾题还是别出了QAQ
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<cmath>
using namespace std;
const int MAX=1e6+1;
const double Pi=acos(-1.0);
struct complex{
double x,y;
complex(double X=0,double Y=0){x=X,y=Y;}
}a[2][MAX];
int n,m,l,lim=1;
int r[MAX],len[MAX],ans[MAX];
complex operator+ (complex x,complex y)
{
return complex(x.x+y.x,x.y+y.y);
}
complex operator- (complex x,complex y)
{
return complex(x.x-y.x,x.y-y.y);
}
complex operator* (complex x,complex y)
{
return complex(x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x);
}
void fft(complex *A,int tt)
{
for(int i=0;i<lim;++i)
if(i<r[i]) swap(A[i],A[r[i]]);
for(int i=1;i<lim;i<<=1)
{
complex w1=complex(cos(Pi/i),tt*sin(Pi/i));
for(int l=i<<1,j=0;j<lim;j+=l)
{
complex w=complex(1,0);
for(int k=0;k<i;++k,w=w*w1)
{
complex x=A[j+k],y=w*A[j+i+k];
A[j+k]=x+y,A[j+i+k]=x-y;
}
}
}
if(tt==-1)
for(int i=0;i<lim;++i)
A[i].x=(int)(A[i].x/lim+0.5);
}
int main()
{
string s;
while(getline(cin,s))
{
bool fl=0;
int L=s.length(),num=0;
for(int i=0;i<L;++i)
if(s[i]=='*')
{
fl=1;
break;
}
if(!fl) continue;
memset(a,0,sizeof(a));
memset(len,0,sizeof(len));
memset(ans,0,sizeof(ans));
for(int i=0,tt=0;i<L;i+=tt)
{
tt=0;
int x=0;
if(isdigit(s[i]))
{
int j=i;
while(isdigit(s[j])) ++tt,x=x*10+s[j++]-48;
while(s[j]==' ') ++j;
if(s[j]=='a')
{
j+=2,tt+=2;
int y=0;
while(isdigit(s[j])) ++tt,y=y*10+s[j++]-48;
len[num]=max(len[num],y);
a[fl][y].x+=x;
}
else if(s[j]=='+'||s[j]==')'||s[j]=='*'||j==L) a[fl][0].x+=x;
}
if(s[i]=='*'||i+(tt?tt:1)-1==L-1)
{
if(s[i]=='*') ++tt;
if(num>=1)
{
lim=1,l=0;
memset(r,0,sizeof(r));
while(lim<=len[num]+len[num-1]) lim<<=1,++l;
for(int j=0;j<lim;++j)
r[j]=(r[j>>1]>>1)|((j&1)<<(l-1));
fft(a[fl],1),fft(a[fl^1],1);
for(int j=0;j<=lim;++j)
a[fl][j]=a[fl][j]*a[fl^1][j];
fft(a[fl],-1);
for(int j=0;j<=lim;++j)
a[fl][j].y=a[fl^1][j].y=a[fl^1][j].x=0;
len[num]=len[num]+len[num-1];
}
++num,fl^=1;
}
if(!tt) ++tt;
}
bool gg=0;
for(int j=0;j<=len[num]+len[num-1];++j)
{
ans[j]+=a[fl^1][j].x;
if(a[fl^1][j].x!=0) gg=1;
}
if(!gg)
{
printf("0\n");
continue;
}
int Len1=0,Len2=0;
for(int i=0;!ans[i];++i)
++Len1;
Len2=Len1;
for(int i=Len1+1;ans[i]!=0;++i)
++Len2;
if(Len2!=Len1) printf("%da^%d",ans[Len2],Len2);
for(int i=Len2-1;i>Len1;--i)
printf("+%da^%d",ans[i],i);
if(!Len1)
{
if(Len2) printf("+%d\n",ans[0]);
else printf("%d\n",ans[0]);
}
else
{
if(Len2!=Len1) printf("+%da^%d\n",ans[Len1],Len1);
else printf("%da^%d\n",ans[Len1],Len1);
}
}
return 0;
}
