【BZOJ3992】序列统计（动态规划，NTT）编程题

18-02-07 来源：[db:作者]

收藏我要投稿

题解

最裸的暴力
设f[i][j]表示前i个数，积在膜意义下是j的方案数
转移的话，每次枚举一个数，直接丢进去就好
复杂度O(nm|S|)，10pts

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
#define RG register
#define MOD 1004535809
inline int read()
{
    RG int x=0,t=1;RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
int n,m,X,T;
int f[2][10000];
int a[10000];
int main()
{
    n=read();m=read();X=read();T=read();
    for(int i=1;i<=T;++i)a[i]=read()%m;
    for(int i=1;i<=T;++i)f[1][a[i]]++;
    for(int i=2;i<=n;++i)
    {
        for(int j=0;j
发现每一步的转移是相同的， 

因此可以矩阵快速幂 

时间复杂度O(lognm3),30pts 

我懒得写了
我们都发现了转移是相同的 

那么不一定只能用矩阵快速幂呀 

我们的转移也是满足结合律的 

所以可以把转移跑快速幂 

复杂度O(lognm2),60pts
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
#define RG register
#define MOD 1004535809
#define MAX 10000
inline int read()
{
    RG int x=0,t=1;RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
int n,m,X,T;
int f[MAX],s[MAX];
int a[MAX],ret[MAX];
int* zy(int *a,int *b)
{
    memset(ret,0,sizeof(ret));
    for(int i=0;i>=1;
    }
    printf("%d\n",s[X]);
    return 0;
}


现在就是最大的问题了

n已经优化到了logn

转移现在才是最大的问题

我们发现转移是这样的：

f[i]?f[j]→f[i?j]

如果它长成这个样子：

f[i]?f[j]→f[i+j]

这样子的话就会做啦

这样就可以跑一遍多项式的卷积
怎么转换呢？

题目给定的条件m是质数

我们知道xφ(m)%m=1

而如果x是m的原根

那么，对于0～φ(m)，

每一个原根的若干次幂恰好对应一个数

那么，这样的话，乘法可以转换成幂的加法
于是，直接跑多项式的卷积就好了

因为要取膜，只能跑NTT
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
#define RG register
#define MOD 1004535809
#define MAX 100000
inline int read()
{
    RG int x=0,t=1;RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
const int pr=3;
const int phi=MOD-1;
int n,m,X,T;
int f[MAX],s[MAX];
int a[MAX],mp[MAX],b[MAX];
int N,M,l,r[MAX],ret[MAX];
int fpow(int a,int b,int P)
{
    int s=1;
    while(b){if(b&1)s=1ll*s*a%P;a=1ll*a*a%P;b>>=1;}
    return s;
}
int ys[MAX],yst;
int getroot(int n)
{
    int tmp=n-1;
    for(int i=2;i*i<=tmp;++i)
        if(tmp%i==0)
        {
            ys[++yst]=i;
            while(tmp%i==0)tmp/=i;
        }
    if(tmp>1)ys[++yst]=tmp;
    for(int g=2;g<=n-1;++g)
    {
        bool fl=true;
        for(int i=1;i<=yst;++i)
            if(fpow(g,(n-1)/ys[i],n)==1){fl=false;break;}
        if(fl)return g;
    }
    return -1;
}
void getmap()
{
    int prm=getroot(m);
    for(int i=0;i>1]>>1)|((i&1)<<(l-1));
}
void NTT(int *P,int opt)
{
    for(int i=0;i<>>=1;
    }
    printf("%d\n",s[mp[X]]);
    return 0;
}

点击复制链接与好友分享!回本站首页

【BZOJ3992】序列统计（动态规划，NTT） 编程题

题解

【BZOJ3992】序列统计（动态规划，NTT）编程题