HDU 6442 GuGu Convolution CCPC 2018 網絡賽

題意：

給出兩個生成函數，求他們的卷積的第n項的系數。要求輸出形如

的最簡形式。

題解：

首先根據題意可以得出答案就是：

可以如下化簡：

可以類比快速幂的求法：

需要注意的是：

由于模數p可能與2不互質，是以運算時對（p*2）取模，求出答案後除以2即可。

由于要帶根号的最簡形式，是以對B分解因數。

代碼：

#include<bits/stdc++.h>
#define N 60010
#define INF 0x3f3f3f3f
#define eps 1e-10
#define pi 3.141592653589793
#define LL long long
#define pb push_back
#define cl clear
#define si size
#define lb lowwer_bound
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;

vector<int>v;
bool f[1000];

int ppp(int n)
{
    if(n==1) return 1;
    int res=1;
    for(auto i:v)
    {
        if(n%i==0)
        {
           int num=1;
           while (n%i==0)
           {
               n/=i;
               num++;
               if (num&1) res*=i;
           }
        }
        if (i*i>n) break;
    }
    return res;
}

LL qmi(LL p,LL q,LL n,LL mod,LL B)
{
    LL a=1,b=1,t1,t2;
    while(n)
    {
        if (n&1)
        {
            t1=(a*p+b*q%mod*B)%mod;
            t2=(a*q+b*p)%mod;
            a=t1;b=t2;
        }
        t1=(p*p+q*q%mod*B)%mod;
        t2=(p*q*2)%mod;
        p=t1;q=t2;
        n>>=1;
    }
    return b;
}

int main()
{
    for (int i=2;i<1000;i++) if (!f[i]) { v.push_back(i); for (int j=i+i;j<1000;j+=i) f[j]=1; }
    int T; LL n,A,B,p,ans;
    sc(T);
    while(T--)
    {
        scanf("%I64d%I64d%I64d%I64d",&A,&B,&n,&p);
        p<<=1;
        ans=(qmi(A,1,n,p,B)-qmi(A,-1,n,p,B)+p)%p;
        ans>>=1; p>>=1;
        int k=ppp(B);
        ans=ans*k%p; B=B/k/k;
        printf("1 %I64d %I64d\n",ans,B);
    }
}