首页 > 考试 > 其他 > 正文
uoj #86 mx的组合数 FFT 原根
2017-01-07       个评论    来源:make_it_for_good的博客  
收藏    我要投稿

把l,r的条件看成前缀相减,那么就是求Cnx%p(1≤x≤bound)

设n的p进制形式为a1a2a3....acnt

bound的p进制形式为b1b2b3.....bcnt

由lucas定理原式为∏Caixi。

设g[i][j] 表示由低到高前i位的xi任意取值且乘积为j的方案数

f[i][j] 表示前i位组成的数小于n的前i位组成的数且乘积为j的方案数。

转移时枚举x=[0,p?1],设z=Cai+1x

g[i+1][jz%p]+=g[i][j]

f[i+1][jz%p]+=g[i][j](x

f[i+1][jz%p]+=f[i][j](x=bi+1)

设G为p的原根,那么可以把x转成Gind[x] 的形式。

这样就可以把乘法转成加法卷积的形式。

注意ind[0]是不存在的,因此0需要在计算完其他后用总的减掉。

#include 
using namespace std;
#define N 1100000
int n,m,ln,h,r;
char s[N];
int v[N],f[N],sum[N],q[N];
struct SAM
{
    int trs[N<<1][3],fa[N<<1],len[N<<1],cnt,last;
    void init(){cnt=1;last=1;}
    void insert(int x)
    {
        int p=last,np=++cnt,q,nq;
        last=np;len[np]=len[p]+1;
        for(;p&&!trs[p][x];p=fa[p])trs[p][x]=np;
        if(!p)fa[np]=1;
        else
        {
            q=trs[p][x];
            if(len[q]==len[p]+1)fa[np]=q;
            else
            {
                fa[nq=++cnt]=fa[q];
                len[nq]=len[p]+1;
                memcpy(trs[nq],trs[q],sizeof(trs[q]));
                fa[q]=fa[np]=nq;
                for(;p&&trs[p][x]==q;p=fa[p])trs[p][x]=nq;
            }
        }
    }
    void solve()
    {
        int now=1,cnt=0;
        for(int i=1;i<=ln;i++)
        {
            int t=s[i]-'0';
            if(trs[now][t])
                now=trs[now][t],cnt++;
            else
            {
                for(;now&&!trs[now][t];now=fa[now]);
                if(!now)now=1,cnt=0;
                else cnt=len[now]+1,now=trs[now][t];
            }
            v[i]=cnt;
        }
    }
}sam;
int check(int x)
{
    h=1;r=0;f[0]=0;sum[0]=0;
    for(int i=1;i<=ln;i++)
    {
        while(h<=r&&q[h]<=i-v[i])h++;
        f[i]=sum[i-1];
        if(v[i]>=x)
        {
            if(h<=r)f[i]=max(f[i],f[q[h]]+(i-q[h]));
            f[i]=max(f[i],sum[i-v[i]]+v[i]);
        }
        sum[i]=max(sum[i-1],f[i]);
        if(i-x+1>=0)
        {   
            while(h<=r&&f[q[r]]-q[r]<=f[i-x+1]-(i-x+1))r--;
            q[++r]=i-x+1;
        }
    }
    return f[ln]+(1e-8)>=(long double)ln*0.9;
}
int main()
{
    //freopen("tt.in","r",stdin);
    sam.init();
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%s",s+1);
        ln=strlen(s+1);
        for(int j=1;j<=ln;j++)
            sam.insert(s[j]-'0');
        sam.insert(2);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s+1);
        ln=strlen(s+1);
        sam.solve();
        int l=1,r=ln;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(check(mid))l=mid+1;
            else r=mid-1;
        }
        printf("%d\n",r);
    }
    return 0;
}
点击复制链接 与好友分享!回本站首页
相关TAG标签 uoj 编程题
上一篇:(HDU5924)Mr.Frog’sProblem思维水题<2016CCPC东北地区大学生程序设计竞赛-重现赛)
下一篇:BZOJ 1336&1337最小圆覆盖
相关文章
图文推荐
文章
推荐
热门新闻

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训
版权所有: 红黑联盟--致力于做实用的IT技术学习网站