「AHOI2001」多项式乘法

发表于 | 分类于 | | 浏览量： 次

来水一发大模拟QwQ。

传送门

洛谷P2553

题解

好久没写这种处理字符串的大模拟了QwQ。

这题每个多项式的长度都很短，系数也很小，所以直接$O(n^2)$的暴力搞过去就行了。

数据范围大一点的话FFT即可。

注意可能有空格。

注意可能在一行中可能包含一个不完整的表达式（可能没有”*”或者”()”），注意应该什么也不要输出，也要注意不要RE或者怎么样了。

总而言之还是挺好写的QwQ。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<cstdio>
#include<cstring>
using namespace std;
int len,a1[50],a2[50],ans[100];char exp[1000];
int main()
{
	while(gets(exp),exp[0])
	{
		len=strlen(exp);memset(a1,0,sizeof(a1));memset(a2,0,sizeof(a2));memset(ans,0,sizeof(ans));
		int i=1;
		while(exp[i]!=')'&&i<len)
		{
			int x=0,z=0;
			while(exp[i]<'0'||exp[i]>'9') i++;
			x=exp[i]-'0';
			if('0'<=exp[i+1]&&exp[i+1]<='9'){i++;x=x*10+exp[i]-'0';}
			i++;
			if(exp[i]=='a')
			{
				i++;i++;z=exp[i]-'0';
				if('0'<=exp[i+1]&&exp[i+1]<='9'){i++;z=z*10+exp[i]-'0';}
				i++;
			}
			a1[z]+=x;
		}
		i++;
		while(exp[i]!=')'&&i<len)
		{
			int x=0,z=0;
			while(exp[i]<'0'||exp[i]>'9') i++;
			x=exp[i]-'0';
			if('0'<=exp[i+1]&&exp[i+1]<='9'){i++;x=x*10+exp[i]-'0';}
			i++;
			if(exp[i]=='a')
			{
				i++;i++;z=exp[i]-'0';
				if('0'<=exp[i+1]&&exp[i+1]<='9'){i++;z=z*10+exp[i]-'0';}
				i++;
			}
			a2[z]+=x;
		}
		for(int i=0;i<=30;i++)
			for(int j=0;j<=30;j++)
				ans[i+j]+=a1[i]*a2[j];
		bool first=false;
		for(int j=60;j>=0;j--)
		{
			if(!ans[j]) continue;
			if(first) putchar('+');
			else first=true;
			if(j>0) printf("%da^%d",ans[j],j);
			else printf("%d",ans[j]);
		}
		putchar('\n');
		memset(exp,0,sizeof(exp));
	}
	return 0;
}