本文主要是介绍BZOJ3992:[SDOI2015]序列统计,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
传送门
这个题大概裸dp这样:dp(i,j)代表已经填了前i个位置,当前乘积为j的方案数C(k)代表集合S中是否存在kdp(i+1,j∗k%m)=∑kdp(i,j)∗C(k)然后这个dp是O(m2n)的,也没啥优化的办法我们尝试将∗转化成+原根是个不错的选择原根可以将m−1个不同的数字(这个题目里0可以不计)对应到m−1个不同的幂上所以我们对应了之后,dp方程就改变了:dp(i+1,(j+k)%(m−1))=∑kdp(i,j)∗C(k)然后这东西大家就很熟悉了吧,FFT呀明显这东西是个线性递推呀然后就直接多项式快速幂就好了qwq这东西是我随便起了个名qwq注意细节就好了 这 个 题 大 概 裸 d p 这 样 : d p ( i , j ) 代 表 已 经 填 了 前 i 个 位 置 , 当 前 乘 积 为 j 的 方 案 数 C ( k ) 代 表 集 合 S 中 是 否 存 在 k d p ( i + 1 , j ∗ k % m ) = ∑ k d p ( i , j ) ∗ C ( k ) 然 后 这 个 d p 是 O ( m 2 n ) 的 , 也 没 啥 优 化 的 办 法 我 们 尝 试 将 ∗ 转 化 成 + 原 根 是 个 不 错 的 选 择 原 根 可 以 将 m − 1 个 不 同 的 数 字 ( 这 个 题 目 里 0 可 以 不 计 ) 对 应 到 m − 1 个 不 同 的 幂 上 所 以 我 们 对 应 了 之 后 , d p 方 程 就 改 变 了 : d p ( i + 1 , ( j + k ) % ( m − 1 ) ) = ∑ k d p ( i , j ) ∗ C ( k ) 然 后 这 东 西 大 家 就 很 熟 悉 了 吧 , F F T 呀 明 显 这 东 西 是 个 线 性 递 推 呀 然 后 就 直 接 多 项 式 快 速 幂 就 好 了 q w q 这 东 西 是 我 随 便 起 了 个 名 q w q 注 意 细 节 就 好 了
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#define LL long long
using namespace std;
inline int read(){int x=0,f=1;char ch=' ';while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return x*f;
}
const int N=2e4+5,mod=1004535809,g=3,gi=334845270;
int n,m,x,S,G,vis[N],H[N],R[N],bin[1<<19];
LL C[N],ans[N];
inline LL ksm(LL a,LL n,int p=mod){LL ans=1LL;while(n){if(n&1)ans=ans*a%p;a=a*a%p;n>>=1;}return ans;
}
inline void init(){for(int i=1;i<m;++i){memset(vis,0,sizeof(vis));int flag=1;for(int j=1;j<m;++j){int tmp=ksm(i,j,m);if(vis[tmp]){flag=0;break;}vis[tmp]=1;}if(flag){G=i;break;}}for(int i=0;i<m;++i)H[ksm(G,i,m)]=i;for(int i=0;i<18;++i)bin[1<<i]=i;
}
inline void NTT(LL *a,int n,int f){int L=bin[n];for(int i=0;i<n;++i)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));for(int i=0;i<n;++i)if(i<R[i])swap(a[i],a[R[i]]);for(int i=1;i<n;i<<=1){LL wn=ksm(f==1?g:gi,(mod-1)/(i<<1));for(int j=0;j<n;j+=(i<<1)){LL w=1LL;for(int k=0;k<i;++k,w=w*wn%mod){LL x=a[j+k],y=w*a[j+k+i]%mod;a[j+k]=(x+y)%mod;a[j+k+i]=(x-y+mod)%mod;}}}if(f==-1)for(int i=0;i<n;++i)a[i]=a[i]*ksm(n,mod-2)%mod;
}
inline void poly_ksm(LL *a,LL *ans,int n,int b){for(int i=0;i<n;++i)ans[i]=a[i];b--;while(b){if(b&1){NTT(ans,n,1);NTT(a,n,1);for(int i=0;i<n;++i)ans[i]=ans[i]*a[i]%mod;NTT(ans,n,-1);NTT(a,n,-1);for(int i=m-1;i<n;++i)ans[i%(m-1)]=(ans[i%(m-1)]+ans[i])%mod;for(int i=m-1;i<n;++i)ans[i]=0;}NTT(a,n,1);for(int i=0;i<n;++i)a[i]=a[i]*a[i]%mod;NTT(a,n,-1);for(int i=m-1;i<n;++i)a[i%(m-1)]=(a[i%(m-1)]+a[i])%mod;for(int i=m-1;i<n;++i)a[i]=0;b>>=1;}
}
int main(){n=read();m=read();x=read();S=read();init();for(int i=1;i<=S;++i){int tmp=read();if(tmp)C[H[tmp]%(m-1)]=1;}int Len;for(Len=1;Len<(m<<1);Len<<=1);poly_ksm(C,ans,Len,n);printf("%lld",ans[H[x]%(m-1)]);return 0;
}
这篇关于BZOJ3992:[SDOI2015]序列统计的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!