HUST 1569(Burnside定理+容斥+数位dp+矩阵快速幂)

传送门：Gift

题意：由n（n<=1e9）个珍珠构成的项链，珍珠包含幸运数字（有且仅由4或7组成），取区间[L,R]内的数字，相邻的数字不能相同，且旋转得到的相同的数列为一种，为最终能构成多少种项链。

分析：这是我做过的最为综合的一道题目（太渣了），首先数位dp筛选出区间[L,R]内的幸运数字总数，dp[pos]表示非限制条件下还有pos位含有的幸运数字个数，然后记忆化搜索一下，随便乱搞的（直接dfs不知会不会超时，本人做法900+ms险过，应该直接dfs会超时），再不考虑旋转相同的情况，可以dp再构造矩阵，dp[i][0]表示到达第i位时，最后一个珠子与第一个珠子不同，dp[i][1]表示到达第i位最后一个珠子与第一个相同，则状态转移方程为：

dp[i][0]=dp[i-1][0]*(m-2)+dp[i-1][1]*(m-1)(m为幸运数字种类).

dp[i][1]=dp[i-1][0]*1

上面构造矩阵快速幂求出总数后再由Burnside定理+容斥得到答案，这个问题较为常见，可参考poj2888做法。

#include <stdio.h>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstdlib>
#define LL long long
#define N 25
#define mod 1000000007
using namespace std;
/**************************矩阵快速幂**************************/
struct matrix
{
    LL m[][];
    void init()
    {
        for(int i=;i<;i++)
            for(int j=;j<;j++)
            m[i][j]=(i==j);
    }
}M;
matrix mult(matrix a,matrix b)
{
    matrix c;
    memset(c.m,,sizeof(c.m));
    for(int k=;k<;k++)
    for(int i=;i<;i++)
    {
        if(a.m[i][k]==)continue;
        for(int j=;j<;j++)
        {
            c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
        }
    }    return c;
}
matrix quick_pow(matrix a,int n)
{
    matrix res;
    res.init();
    while(n)
    {
        if(n&)res=mult(res,a);
        a=mult(a,a);
        n>>=;
    }
    return res;
}
LL calc(LL n,LL m)
{
    matrix res;
    res.m[][]=m-;res.m[][]=m-;
    res.m[][]=;res.m[][]=;
    res=quick_pow(res,n-);
  //  printf("m=%lld n=%lld res=%lld\n",m,n,res.m[0][1]);
    return m*res.m[][]%mod;
}
/**************************矩阵快速幂**************************/
LL POW(LL a,LL n)
{
    LL res=;
    a%=mod;
    while(n)
    {
        if(n&)res=res*a%mod;
        a=a*a%mod;
        n>>=;
    }
    return res;
}
/**********************容斥**************************/
#define MAXN 12
#define MAXM 32000
#define EPS 1e-8
bool p[MAXM];
vector<int> prime;
vector<int> factor;
vector<int> primefactor;
void Init() {
    int i, j;
    prime.clear();
    memset(p, true, sizeof(p));
    for (i = ; i < ; i++) {
        if (p[i]) {
            for (j = i * i; j < MAXM; j += i)
                p[j] = false;
        }
    }
    for (i = ; i < MAXM; i++) {
        if (p[i])
            prime.push_back(i);
    }
}
void Prime(int x) {
    int i, tmp;
    primefactor.clear();
    tmp = (int) (sqrt((double) x) + EPS);
    for (i = ; prime[i] <= tmp; i++) {
        if (x % prime[i] == ) {
            primefactor.push_back(prime[i]);
            while (x % prime[i] == )
                x /= prime[i];
        }
    }
    if (x > )
        primefactor.push_back(x);
}
int Mul(int x, int &k) {
    int i, ans;
    ans = ;
    for (i = k = ; x; x >>= , i++) {
        if (x & ) {
            k++;
            ans *= primefactor[i];
        }
    }
    return ans;
}
LL Phi(int x) {
    int i, j, t, ans, tmp;
    Prime(x);
    ans = ;
    t = (int) primefactor.size();
    for (i = ; i < ( << t); i++) {
        tmp = Mul(i, j);
        if (j & )
            ans += x / tmp;
        else
            ans -= x / tmp;
    }
    return (x - ans) %mod;
}
/**********************容斥**************************/
LL solve(LL n,LL m)
{
    LL ans=;
    for(int i=;i*i<=n;i++)
    {
        if(n%i==)
        {
            int a=i,b=n/i;
            if(i*i==n)
            {
                ans=(ans+Phi(n/a)*calc(a,m))%mod;
            }
            else
            {
                ans=(ans+Phi(n/a)*calc(a,m))%mod;
                ans=(ans+Phi(n/b)*calc(b,m))%mod;
            }
        }
    }
    ans=ans*POW(n,mod-)%mod;
    return ans;
}
/************************数位dp**********************/
LL dig[],dp[];
LL dfs(int pos,int flag,int limit,int fzore)
{
    if(pos==)return flag;
    if(!fzore&&!limit&&~dp[pos])return dp[pos];
    int len=limit?dig[pos]:;
    LL ans=;
    for(int i=;i<=len;i++)
    {
        if(i==||i==||i==){
        if(fzore&&i==)ans+=dfs(pos-,,i==len&&limit,);
        else if(i==||i==)ans+=dfs(pos-,,i==len&&limit,);}
    }
    if(!fzore&&!limit)dp[pos]=ans;
    return ans;
}
LL fun(LL x)
{
    int len=;
    if(x<)return ;
    while(x)
    {
        dig[++len]=x%;
        x/=;
    }
    return dfs(len,,,);
}
/************************数位dp**********************/
int main()
{
    LL n,L,R;
    Init();
    memset(dp,-,sizeof(dp));
    while(scanf("%lld%lld%lld",&n,&L,&R)>)
    {
        LL num=fun(R)-fun(L-);
        if(n==)
        {
            puts("");continue;
        }
        if(n==)
        {
            printf("%d\n",num%mod);
            continue;
        }
        printf("%d\n",solve(n,num));    }
}