TCO2013 Wildcard 1000-SemiMultiple

2016.04.07 16:45 Thu | 48次阅读 | 旧日oi | 固定链接 | 源码

题目大意

求n位的二进制数中有多少个数,不是m的倍数,但是把某一位取反能变成m的倍数。n,m<=2000

题解

dp

一道神题。
先讲一个nm^2做法。
预处理出前i位任选,模m等于j的方案数g[i][j],那么由此也可以推出任意连续k位,模m等于j的方案数。
我们枚举原数模m的值,然后找出所有取反后可以满足答案的位置,那么除了这些位置,其它位置的数可以任意选。这些位置中,我们可以让最小的那个位置代表这个数,这样我们就可以列出dp方程f[i][j][k]表示原数模m等于i,前j个位置中无法改变某一位使得最后的数能被m整除,且前j个位置模m等于k的方案数。
转移的话只要看这一位能否通过取反满足答案,如果不可以,那么直接转移,如果可以,那么让后面的数任意选,统计答案,然后在转移的时候不把改变后能符合条件的值转移过去。

这个做法有一个不好的地方在于做了大量的重复更新,很多的更新都是一样的,一共只有n个数的更新需要特殊处理,而这个算法做了n*m次。

怎么解决?设m等于2^p*q,那么前p位中如果有1,那么只能有一个,且后边的数要是m的倍数,这个很好算。如果没有1,就等于把m变成q,原序列右移p位,此时m是个奇数。
然后,我们发现,2^i次方模m是有循环节的!也就是说,模m等于k的2^i中的i是等差的,并且每组都一样!所以我们可以把循环节len找出来,然后设f2[i][j]表示前i项任意取值,但是2^i=1,m-1(mod m)的i不参加对应转移的方案数。最后用总方案数减去不合法方案数确定答案。
然后我们就可以把dp分成两段搞了,上个图。


这么对于2^i和m-2^i搞两遍,还有一些细节,比如前半段有一个位置不能特殊取之类的……写起来太麻烦了……看代码理解一下吧。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 2005
int n,m,mod;
ll f[N][N],g[N][N],f2[N][N],p[N],tmp[N],ans;
int rk[N];
bool vis[N];
int main()
{
    cin>>n>>m>>mod;
    int cnt=0,l=0,t=0;
    while(~m&1) m>>=1,cnt++,n--;
    p[0]=1;for(int i=1;i<n;i++) p[i]=p[i-1]*2%m;
    for(int k=1,i=1;i<=n;i++)
    {
        if(k==m-1) t=i;
        if(i>1&&k==1) {l=i-t;break;}
        rk[i]=k;k=k*2%m;
    }
    f[0][0]=g[0][0]=1;
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    if(f[i][j])
    {
        (f[i+1][j]+=f[i][j])%=mod;
        (f[i+1][(j+p[i])%m]+=f[i][j])%=mod;
    }
    ans=f[n][0]*cnt%mod;
    if(m==1)
    {
        printf("%lld\n",ans);
        return 0;
    }
    memset(f2,0,sizeof(f2));f2[0][0]=1;
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    if(f2[i][j])
    {
        (f2[i+1][(j+j+1)%m]+=f2[i][j])%=mod;
        if(i+1!=l) (f2[i+1][(j+j)%m]+=f2[i][j])%=mod;
    }
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    if(g[i][j])
    {   
        if(p[i]!=m-1) (g[i+1][j]+=g[i][j])%=mod;
        if(p[i]!=1) (g[i+1][(j+p[i])%m]+=g[i][j])%=mod;
    }
    for(int i=1;i<=n;i++)
    if(!vis[p[i-1]])
    {
        vis[p[i-1]]=1;
        (ans+=f[n][p[i-1]])%=mod;
        memset(tmp,0,sizeof(tmp));
        for(int k=0;k<m;k++) (tmp[p[i-1]*k%m]+=g[n-i+1][k])%=mod;
        for(int k=0;k<m;k++) (ans+=mod-tmp[k]*f2[i-1][(p[i-1]-k+m)%m]%mod)%=mod;
    }
    memset(f2,0,sizeof(f2));f2[0][0]=1;
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    {
        (f2[i+1][(j+j)%m]+=f2[i][j])%=mod;
        if(i+1!=l) (f2[i+1][(j+j+1)%m]+=f2[i][j])%=mod;
    }
    memset(g,0,sizeof(g));g[0][0]=1;
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    if(g[i][j])
    {   
        if(p[i]!=1) (g[i+1][j]+=g[i][j])%=mod;
        if(p[i]!=m-1) (g[i+1][(j+p[i])%m]+=g[i][j])%=mod;
    }
    for(int i=1;i<=n;i++)
    if(!vis[m-p[i-1]])
    {   
        vis[m-p[i-1]]=1;
        (ans+=f[n][m-p[i-1]])%=mod;
        memset(tmp,0,sizeof(tmp));
        for(int k=0;k<m;k++) (tmp[p[i-1]*k%m]+=g[n-i+1][k])%=mod;
        for(int k=0;k<m;k++) (ans+=mod-tmp[k]*f2[i-1][(m-p[i-1]-k+m)%m]%mod)%=mod;
    }
    printf("%lld\n",ans);
}