多項式平方的题解
记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。
在解题之前提交题解的代码会导致封禁。
作者：
Subtask 1
把一個數字平方有很難嗎？（WA 20%）
Subtask 1~2
\((ax+b)^2 = a^2x^2 + 2abx + b^2\)。（WA 40%）
Subtask 3
檢查常數項的平方是否正確。（WA 20%）
Subtask 1~4
直接用雙層迴圈模擬直式乘法，\(O(tn^2)\)。（TLE 80%）
Subtask 1~5
Solution 1
Karatsuba，\(O(tn^{1.585})\)。（AC 100%）
Solution 2
FFT，\(O(tnlgn)\)。（AC 100%）
值得一提的是，numpy 有內建 FFT 多項式乘法，但是實測 TLE 80%。（如果放這個過就太水了）
以上兩種作法都可以拿到填充題最後一題的分數。
Solution 3
隨機生成幾個 \(x\)，代入 \(f(x)^2\) 和 \(g(x)\)，並在模 \(M\)（一個夠大的質數）下做加跟乘的運算，比對兩者答案是否相同。這種方式失敗的機率是 \(O(M^{-k})\)，其中 \(k\) 是代入的 \(x\) 個數，只要 \(M, k\) 夠大就幾乎不會錯，時間複雜度 \(O(tkn)\)。（AC 100%）
Solution 4
注意到「至多只會有一個係數算錯」。因此，我們只要代入 \(x = 1\)（也就是係數和）就可以確認正確性了。因為 \(a_i \le 1000\)，連模都不用，只要開 int64_t 就好。\(O(tn)\)。（AC 100%）
Solution(?) 5
其實還有另一個可以直接求出多項式的平方的方法：把係數壓進一個大數裡（i.e. \(F = \sum a_i * X\)，\(X\) 是一個足夠大的數），然後用 GMP（內部 FFT）或 Java BigInteger（內部 Toom-Cook）的大數乘法平方。不過常數極大，TLE 80%。
標程
C++ 隨機 hash（by ）
#include<bits/stdc++.h>
#define maxn 100010
#define M 1000000007
using namespace std;
long long a[maxn],b[maxn];
long long p[3][maxn],c[3]={11,13,17};
int main()
{
cin.tie(0);ios_base::sync_with_stdio(false);
for(int i=0;i<3;i++)
{
p[i][0]=1;
for(int j=1;j<maxn;j++)
{
p[i][j]=(p[i][j-1]*c[i])%M;
}
}
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
for(int i=0;i<=n;i++)cin>>a[i];
for(int i=0;i<=n+n;i++)cin>>b[i];
long long u=0,v=0,f=1;
for(int l=0;l<3;l++)
{
u=v=0;
for(int i=0;i<=n;i++)u=(u+a[i]*p[l][i])%M;
for(int i=0;i<=n*2;i++)v=(v+b[i]*p[l][i])%M;
if((u*u)%M!=v){f=0;cout<<"No"<<'\n';break;}
}
if(f)cout<<"Yes"<<'\n';
}
return 0;
}
C++ Karatsuba（by ）
#include<bits/stdc++.h>
using namespace std;
vector<long long>square(vector<long long> a)
{
vector<long long>ans;
//if(a.size()==1){a[0]=a[0]*a[0];a.push_back(0);return a;}
if(a.size()<130)
{
for(int i=0;i<a.size()*2;i++)ans.push_back(0);
for(int i=0;i<a.size();i++)
for(int j=0;j<a.size();j++)ans[i+j]+=a[i]*a[j];
return ans;
}
vector<long long>tmp,b,c,d;
for(int i=0;i<a.size()/2;i++)tmp.push_back(a[i]);
b=square(tmp);
for(int i=0;i<a.size()/2;i++)tmp[i]+=a[i+a.size()/2];
c=square(tmp);
for(int i=0;i<a.size()/2;i++)tmp[i]-=a[i];
d=square(tmp);
for(int i=0;i<a.size()*2;i++)ans.push_back(0);
for(int i=0;i<a.size();i++)
{
ans[i]+=b[i];
ans[i+a.size()/2]+=c[i]-d[i]-b[i];
ans[i+a.size()]+=d[i];
}
return ans;
}
int main()
{
cin.tie(0);ios_base::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
vector<long long>tmp;
int n,f=1;
cin>>n;
for(int i=0;i<=n;i++)
{
long long x;
cin>>x;
tmp.push_back(x);
}
while(tmp.size()!=(tmp.size()&(-tmp.size())))tmp.push_back(0);
tmp=square(tmp);
for(int i=0;i<=n+n;i++)
{
long long x;
cin>>x;
if(x!=tmp[i])f=0;
}
if(f)cout<<"Yes"<<'\n';
else cout<<"No"<<'\n';
}
return 0;
}
Scala \(x = 1\)（by ）
object x006 extends App {
val Mod = (1E9 + 7).toInt
def sum(x: Long, y: Long) = (x + y) % Mod
for (_ <- 1 to io.StdIn.readInt()) {
val n = io.StdIn.readInt()
val fS, gS = io.StdIn.readLine().split(" ").view.map(_.toLong).reduce(sum)
println(if (fS * fS % Mod == gS) "Yes" else "No")
}
}
评论