\([Link](https://www.luogu.org/problemnew/show/P2553)\)
\(\color{red}{\mathcal{Description}}\)
给出两个多项式的乘积表达式，请求出它的结果。
啥？乘积表达式？哦，就是酱紫的：
\((4a^3 + 6a^2 + a ^ 1 + 3) * (3a^2 + a ^ 1 + 2)\)
嗯，那么它的结果也要写成这样\(qwq\)但是在这里就不举例子了\(qwq\)
\(\color{red}{\mathcal{Solution}}\)
\(emmmm\)其实吧，我根本不想做这个题，一看是要你扣数的题就觉得……十分的不可做。但是由于我刷了一下午的简单码力题，所以看到这道题感到很亲切\(qwq\)
但是！但是！但是！但是！——
这道题提供的输入的多项式们里，居然可以没有乘号！？并且这种情况应该忽略！？
好吧，还能不能好好地考察FFT了？？？？
qwq真是毒瘤啊……并且好像在Luogu上这个题只有一个测试点……哇塞……只有一个你还那么坑……QAQ、
嗯，这道很迷的题就这么做完啦！
#include#include #include #include #define MAXN 100010#define il inlineconst double pi = acos(-1.0) ;using namespace std ;bool mark ; char s [MAXN << 1];int last, i, j, k, l, r[MAXN] ;int F, L, Lim, to, now, tot1, tot2 ;struct nodes{ double x, y ; nodes (double xx = 0, double yy = 0){ x = xx, y = yy ; }}A[MAXN], B[MAXN], T1[MAXN], T2[MAXN] ;nodes operator * (nodes J, nodes Q) {return nodes(J.x * Q.x - J.y * Q.y , J.x * Q.y + J.y * Q.x) ;}nodes operator + (nodes J, nodes Q) {return nodes(J.x + Q.x , J.y + Q.y) ;}nodes operator - (nodes J, nodes Q) {return nodes(J.x - Q.x , J.y - Q.y ) ;}il bool read(int pos){ now = 0, to = 0 ; while(isdigit(s[pos])) now = now * 10 + s[pos] - 48, pos ++, to ++ ; return to ;}il void init(){ Lim = 1, L = strlen(s), mark = 1, F = tot1 = tot2 = l = 0 ; for(i = 0 ; i < L; i ++) if(s[i] == '*') F = 1 ; if(!F) return ; memset(A, 0, sizeof(A)), memset(B, 0, sizeof(B)), memset(T1, 0, sizeof(T1)), memset(T2, 0, sizeof(T2));}il void prepare(){ for(i = 0; i < L && s[i] != '*'; i ++){ if(read(i)) if(s[i - 1]!= '^') T1[++ tot1].x = now * mark, mark = 1; else if(s[i] == '+') mark = 1 ; else if(s[i] == '-') mark = -1 ; i += ((!to)?to : (to - 1)), last = i ; } for(i = 1; i <= tot1; i ++) A[tot1 - i].x = T1[i].x ; tot1 -- ; for(i = last + 1; i < L; i ++){ if(read(i)) if(s[i - 1]!= '^') T2[++ tot2].x = now * mark, mark = 1 ; else if(s[i] == '+') mark = 1 ; else if(s[i] == '-') mark = -1 ; i += ((!to)?to : (to - 1)) ; } for(i = 1; i <= tot2; i ++) B[tot2 - i].x = T2[i].x ; tot2 -- ;}il void FFT(nodes *J, double flag){ for(i = 0; i < Lim; i ++) if(i < r[i]) swap(J[i], J[r[i]]) ; for(j = 1; j < Lim; j <<= 1){ nodes base(cos(pi / j), flag * sin(pi / j)) ; for(k = 0; k < Lim; k += (j << 1) ){ nodes t(1, 0) ; for(l = 0 ; l < j; l ++, t = t * base){ nodes Nx = J[k + l], Ny = t * J[k + j + l] ; J[k + l] = Nx + Ny ; J[k + j + l] = Nx - Ny ; } } }}int main(){ while(gets(s)){ init(); if(!F) continue ; prepare() ; while(Lim <= tot1 + tot2) Lim <<= 1, l ++ ; for(i = 0; i < Lim; i ++ ) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1)) ; FFT(A, 1), FFT(B, 1) ; for(i = 0; i <= Lim; i ++) A[i] = A[i] * B[i] ; FFT(A, -1) ; for(i = tot1 + tot2; i > 0 ; i --){ printf("%da^%d", (int)(A[i].x / Lim + 0.5), i); if(A[i].x / Lim + 0.5 > 0) putchar('+') ; else putchar('-') ; } cout << (int)(A[0].x / Lim + 0.5) << endl ; }}
\(4ms\)……还挺快？看来我常数挺小的\(233\).