题解 P3321 【[SDOI2015]序列统计】

ZigZagKmp

2020-02-22 13:28:34

题解

题目大意

给定一个集合S，\forall x\in S,s\in [0,m-1]，求从这个集合S中选取n个数，使得乘积为x的方案数。

算法分析

这其实是一类非常经典的问题。

引入例题1

给定一个集合S，\forall x\in S,s\in [1,n]，在这个集合中选取2个数（可以重复），使得加和为A的方案数。

不难想到可以从数值角度入手，我们运用桶思想，设在集合中i这个数字出现了h(i)次，则不难得到答案为

\sum_{i=1}^Ah(i)\times h(A-i)

显然这个可以O(n)求解，具体实现不再赘述。

当然这个式子符合多项式卷积的一般形式，所以也可以O(n\log n)求解。（不过一道普及组难度的题目被搞成这样好吗）

引入例题2

给定一个集合S，\forall x\in S,s\in [1,n]，在这个集合中选取3个数（可以重复），使得加和为A的方案数。

类比于上一道例题，不难得到答案为

\sum_{i=1}^A\sum_{j=1}^{A-i}h(i)\times h(j)\times h(A-i-j)

时间复杂度是O(n^2)，似乎不是很好。

这个能不能优化呢？

1+2=3

选取3个数可以看作在选取1个数的集合S_1和选取2个数的集合S_2中分别选取1个数。

我们可以先求出选取2个数的方案，记从S中选取2个数加和为i的方案数为h_2(i)，则不难得到答案为

\sum_{i=1}^Ah(i)\times h_2(A-i)

那如何快速求出h_2呢？

由上一道例题可得

h_2(x)=\sum_{i=1}^xh(i)\times h(x-j)

这是标准的卷积形式，可以使用FFT/NTT快速求出h_2，时间复杂度为O(n\log n)。

推荐题目：

【bzoj3513】[MUTC2013]idiots
【bzoj3771】Triple

引入例题3

给定一个集合S，\forall x\in S,s\in [1,n]，在这个集合中选取k个数（可以重复），使得加和为A的方案数。

类比于例题2，不难得到一种方法：设h_t(i)表示从集合中选取t个数加和为i的方案数，则有如下的递推式：

h_t(x)=\sum_{i=1}^nh_{t-1}(i)\times h(x-i)

这样时间复杂度是O(km\log m)，还有一定的优化空间。

考虑倍增，设h_t(i)表示从集合中选取2^t个数加和为i的方案数。选取2^t个数相当于在选取2^{t-1}个数的集合中选取2个数，则不难得到如下的递推式：

h_t(x)=\sum_{i=1}^nh_{t-1}(i)\times h_{t-1}(x-i)

这样预处理出h_t，把k二进制拆解，类比于快速幂，可以在O(m\log m\log k)的时间复杂度下实现。

核心代码如下：

ans[0]=1;//初始化
for(int i=30;~i;i--){
    if((k>>i)&1){
        mul(h[i],ans,ans);
    }
}

引入例题4

给定一个集合S，\forall x\in S,s\in [0,n-1]，在这个集合中选取k个数（可以重复），使得加和在\bmod \ n意义下为A的方案数。

和上一题相比，这一题需要的是模意义下的加法，因此核心算法和上一题一样，只是有一个细节要注意：多项式乘法后，需要把\ge n的那些项累加到对应模运算以后的位置，因为这些也是可能的方案，对答案有贡献。

可能用代码表示会更加清楚：

void mul(int *f,int *g,int *ans){
    f-->tmp1
    g-->tmp2//复制两个数组，保证f,g本身对应的数组不发生改变
    ntt(tmp1,1);ntt(tmp2,1);
    for(int i=0;i<N;i++)tmp1[i]=tmp1[i]*tmp2[i]%mod;
    ntt(tmp1,-1);
    // 以上为ntt常规操作
    for(int i=0;i<n;i++)ans[i]=tmp1[i];
    for(int i=n;i<N;i++)ans[i%n]=(ans[i%n]+tmp1[i])%mod;//这就是上述的变化
}

回到原题

引入例题4和原题之间只有一步之遥，唯一的变化是加法变成了乘法。（变量名不统一这类的就不考虑了）

这里我们把乘法变成加法！

回想初等函数，我们发现有2种函数可以实现乘法与加法的互化：指数函数和对数函数。

这里略讲一下指数函数和对数函数，防止有些同学没学过。

指数函数，形如f(x)=a^x,a\ge 0,a\neq1，根据幂运算性质，不难得到：f(x+y)=f(x)\times f(y)。

取对数运算，对于a^x=N，则有\log_aN=x，根据a^x\times a^y=a^{x+y}，不难得出\log_aa^x+\log_aa^y=\log_aa^{x+y}=\log_a(a^x\times a^y)，推广可得\log_ax+\log_ay=\log_a(x\times y)。

对数函数，形如f(x)=\log_ax,a\ge 0,a\neq 1,x>0，根据对数运算相关性质，不难得到f(xy)=f(x)+f(y)。

指数函数可以使加法转化为乘法，对数函数可以使乘法转化为加法。

但是指对运算都是在实数域上的，而本题是在模意义下的，怎么处理呢？

模意义下的指数/对数？

求指数还是很容易的，随便以一个数为底（设为a），在模意义下求出a^x,x\in[1,m-1]，那么根据对数的定义，则可令\log_a(a^x\bmod m)=x，这样建立映射关系。

看上去似乎没有问题？

我们举一个例子，如果m=7,a=2，那么a^1 \equiv a^4\equiv 2 \ (\bmod\ m)，那么\log_a(2)=?

我们发现这种映射关系必须是一一对应的，因此并不是随便取一个数为底就可以的。

我们需要找到一个底数a，使得a^1,a^2,\cdots,a^{m-1}在\bmod \ m意义下互不相同。

注意：这里没有包含a^0，这是因为在\bmod \ m意义下不存在一个数x使得a^x\equiv 0(\bmod \ m)，因此实际上只有m-1个可对应位置，在本题中S集合中的0对答案无贡献，故忽略a^0。

这个东西似乎很熟悉啊，这好像就是原根。

对于p的原根g，满足g^1,g^2,\cdots,g^{p-1}在\bmod \ p意义下互不相同。

因此我们只需要找到m的一个原根，即可把乘法转化为加法。

综上，我们得到这一题的解决方法：

求出m的原根，并把集合S中的数x转化为\log_gx。
求出h_t，含义与上面引入例题的类似，其中h_0(i)表示集合S中满足\log_gx=i数的数量。
将n进行二进制拆分，并做多项式卷积，求出在去过对数的集合中选取n个数加和为i的方案数为ans(i)。
对于输入的X，答案即为ans(\log_gX)。

时间复杂度为O(m\log m\log n)

代码实现

#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
#define maxm 2000005
#define inf 0x3f3f3f3f
#define int long long
#define mod 1004535809
#define local
template <typename Tp> void read(Tp &x){
    int fh=1;char c=getchar();x=0;
    while(c>'9'||c<'0'){if(c=='-'){fh=-1;}c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c&15);x%=mod;c=getchar();}x*=fh;
}
int ksm(int B,int P,int Mod){int ret=1;while(P){if(P&1)ret=1ll*ret*B%Mod;B=1ll*B*B%Mod;P>>=1;}return ret;}

namespace Poly{
    const int Gmod=3,invG=334845270;
    int a[maxn],b[maxn];
    int tr[21][maxn];
    int Wn[2][21];
    int LG[maxn];
    int inv[maxn];
    void preprocess(int maxN){
        for(int i=0;(1<<i)<=maxN*2;i++)LG[1<<i]=i;
        for(int i=0;(1<<i)<=maxN*2;i++){
            Wn[0][i]=ksm(invG,(mod-1)/(1<<(i+1)),mod);
            Wn[1][i]=ksm(Gmod,(mod-1)/(1<<(i+1)),mod);
            int N=(1<<i);
            for(int j=0;j<N;j++)tr[i][j]=((tr[i][j>>1]>>1)|((j&1)?(N>>1):0));
        }
        inv[1]=1;
        for(int i=2;i<=maxN*2;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    }
    void ntt(int *f,int N,int typ){
        for(int i=0;i<N;i++)if(i<tr[LG[N]][i])swap(f[i],f[tr[LG[N]][i]]);
        for(int len=1;len<N;len<<=1){
            int wn=Wn[typ==1][LG[len]];
            for(int i=0;i<N;i+=(len<<1)){
                int buf=1;
                for(int j=0;j<len;j++,buf=1ll*buf*wn%mod){
                    int FL=f[i+j],FR=1ll*f[i+j+len]*buf%mod;
                    f[i+j]=(FL+FR)%mod;
                    f[i+j+len]=(FL-FR)%mod;
                }
            }
        }
        if(typ==-1){
            int invN=inv[N];
            for(int i=0;i<N;i++)f[i]=1ll*f[i]*invN%mod;
        }
        for(int i=0;i<N;i++)f[i]=(f[i]+mod)%mod;
    }
    void mul(int *ff,int *gg,int *ans,int n,int m,int mod_x){
        int N;
        for(N=1;N<n+m-1;N<<=1);
        for(int i=0;i<n;i++)a[i]=ff[i];for(int i=n;i<N;i++)a[i]=0;
        for(int i=0;i<m;i++)b[i]=gg[i];for(int i=m;i<N;i++)b[i]=0;
        ntt(a,N,1);ntt(b,N,1);
        for(int i=0;i<N;i++)a[i]=1ll*a[i]*b[i]%mod;
        ntt(a,N,-1);
        for(int i=0;i<mod_x;i++)ans[i]=a[i];
        for(int i=mod_x;i<N;i++)ans[i%n]=(ans[i%n]+a[i])%mod;//这里即为模意义下的的特殊之处，对应引入例题4
        for(int i=mod_x;i<N;i++)ans[i]=0;
    }//多项式问题要注意及时清零，否则可能会有一些比较难调试出来的错误
}

int n,m;
int P,S;
int h[maxn];
int f[35][maxn],g[maxn];
void Ksm(int p){
    g[0]=1;
    for(int i=32;~i;i--){
        if((p>>i)&1)
        Poly::mul(f[i],g,g,m-1,m-1,m-1);
    }
}//二进制拆分，类比于快速幂
int dtol[maxn],ltod[maxn];
//dtol指真数到对数的映射
//ltod指对数到真数的映射（也是指数到幂的映射）
//本题中ltod没有太大作用
bool check(int gg,int x){
    int tmp[8005]={0};
    for(int i=0,tep=1;i<x-1;i++,tep=1ll*tep*gg%x){
        tmp[tep]++;
        if(tmp[tep]>1)return 0;
    }
    return 1;
}//这个是最暴力的原根判定方法，但因为一个质数最小的原根普遍较小，且本题 m 的范围也比较小，因此暴力判断足矣
void get_G(int x){
    int GGG;
    for(int i=2;i<x;i++){
        if(check(i,x)){
            GGG=i;break;
        }
    }
    for(int i=0,tep=1;i<x-1;i++,tep=1ll*tep*GGG%x){
        dtol[tep]=i;ltod[i]=tep;
    }//构造对数表
}
signed main(){
    int X;
    read(n);read(m);Poly::preprocess(m<<2);
    get_G(m);
    read(X);read(S);
    for(int i=1,a;i<=S;i++){
        read(a);
        if(!a)continue;h[dtol[a]]++;
    }
    for(int i=0;i<m;i++)f[0][i]=h[i];
    for(int i=1;i<=32;i++){
        Poly::mul(f[i-1],f[i-1],f[i],m-1,m-1,m-1);
    }//倍增求出f（即为分析中的ht）
    Ksm(n);
    printf("%lld\n",g[dtol[X]]);
    return 0;
}

写在最后

这道题目或许是不少同学接触多项式之后遇到的前几道题目，而题解区的部分题解对刚接触多项式的同学不很友好，过于简洁。故作此题解，同时也对这一类问题稍作总结。