多項式平方的题解


记住在没有思路时使用题解,不要从它复制粘贴代码。请尊重题目和题解的作者。

在解题之前提交题解的代码会导致封禁。

作者: WillyPillow

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 tan7680
#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 tan7680
#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 WillyPillow
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")
  }
}

评论

目前没有评论。