luoguP4705 玩游戏

川长思鸟来 2021-12-23 14:57 356阅读 0赞

好好玩

![1399631-20190419154323616-1547333298.png][]

即对于k∈\[1,t\] 求(ax+by)^k

**以下图片均来自于：**

**[在Ta的博客查看][Ta]**

## 一 ##

![1399631-20190419154444748-1599344469.png][]

二项式展开：

![1399631-20190419154437947-1719039207.png][]

设：

![1399631-20190419154502659-1319169030.png][]

那么：

![1399631-20190419154528098-209270669.png][]

可以卷积了

## 二 ##

求：

![1399631-20190419154502659-1319169030.png][]

（PS：随机序列的0~k次方和，这是一个经典问题。）

我的思路：O(nk)暴力

神仙思路：求一个毫不沾边的东西，然后写两次，对应上系数。O(nlog^2n)

不妨考虑求A(x)：

先求一个看起来毫不沾边的东西：

![1399631-20190419154800827-160667191.png][]

![1399631-20190419154830245-1308687095.png][]

这个G成为了写两次的东西

解决问题的中轴和杠杆

利用

**分治NTT+求Ln**

现在已经写了一次

写第二次：

![1399631-20190419154817453-358647791.png][]

![1399631-20190419155037132-394391092.png][]

对于单独一项，采用Taylor展开，往多项式方向靠近

![1399631-20190419155152946-1274127367.png][]

合起来：  
![1399631-20190419155210639-1443602007.png][]

交换顺序：

![1399631-20190419155338169-654536119.png][]

哇！

写第二次，

用**Taylor展开+交换求和号**

对应系数直接相等

神仙神仙~！~~~！！~！

## Code ##

多项式全家桶

const int N=1e5+5;
    int n,m,K;
    int a[N],b[N];
    int A[N],B[N];
    int c[N];
    int jie[N],inv[N];
    il Poly divi(int l,int r){
        if(l==r){
            Poly g;g.resize(2);g[0]=1;g[1]=c[l];return g;
        }
        int mid=(l+r)>>1;
        Poly L=divi(l,mid),R=divi(mid+1,r);
        return L*R;
    }
    void wrk(int *a,int *A,int n){    
        for(reg i=1;i<=n;++i) c[i]=a[i];
        Poly G=divi(1,n);
        // G.out();
        G.resize(K+4);
        G=Ln(G);   
        G.resize(K+1);
        // G.out();
        for(reg k=1;k<=K;++k){
            if((k+1)&1){
                A[k]=mod-mul(G[k],k);
            }else{
                A[k]=mul(G[k],k);
            }
        }
    }
    int main(){
        rd(n);rd(m);
        for(reg i=1;i<=n;++i){
            rd(a[i]);
        }
        for(reg i=1;i<=m;++i){
            rd(b[i]);
        }
        rd(K);
        wrk(a,A,n);
        wrk(b,B,m);
        A[0]=n;
        B[0]=m;
        // prt(A,0,K);
        // prt(B,0,K);
    
        Poly f,g;
        f.resize(K+1);g.resize(K+1);
        jie[0]=1;
        for(reg i=1;i<=K;++i) jie[i]=(ll)jie[i-1]*i%mod;
        inv[K]=qm(jie[K],mod-2);
        for(reg i=K-1;i>=0;--i) inv[i]=mul(inv[i+1],i+1);
    
        for(reg i=0;i<=K;++i){
            f[i]=mul(A[i],inv[i]);
            g[i]=mul(B[i],inv[i]);
        }
        f=f*g;
        for(reg i=1;i<=K;++i){
            ll ans=mul(jie[i],f[i]);
            ans=mul(ans,qm(mul(n,m),mod-2));
            printf("%lld\n",ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Miracevin/p/10736482.html

[1399631-20190419154323616-1547333298.png]: /images/20211223/627ded79d6e04f7c9b4f2a566aa4be33.png
[Ta]: https://www.luogu.org/blog/winxp/solution-p4705
[1399631-20190419154444748-1599344469.png]: /images/20211223/518bd8645e344c92a9e3a09fc4c8b37f.png
[1399631-20190419154437947-1719039207.png]: /images/20211223/061a6cfea22f48e28685f6c2c713c63d.png
[1399631-20190419154502659-1319169030.png]: /images/20211223/f1a24c5b0784481cb5a36f80114d03dc.png
[1399631-20190419154528098-209270669.png]: /images/20211223/da79a2f49359466c8b335eef371843ca.png
[1399631-20190419154800827-160667191.png]: /images/20211223/e146823357844d3291e3bb7ac64b71c6.png
[1399631-20190419154830245-1308687095.png]: /images/20211223/d8557564d8db406eaf087dd2e6eacf2c.png
[1399631-20190419154817453-358647791.png]: /images/20211223/7d2b390d21a74c23ae0645cdba96c6ba.png
[1399631-20190419155037132-394391092.png]: /images/20211223/4aa58482ce9d462b9c52f112d4c14493.png
[1399631-20190419155152946-1274127367.png]: /images/20211223/1f97ca476cf34c5f94584f3974c8857c.png
[1399631-20190419155210639-1443602007.png]: /images/20211223/de4de9dd3ddb4e089a601399ae8bf967.png
[1399631-20190419155338169-654536119.png]: /images/20211223/650b0ec798194bb2a029108d95e0ad88.png