传送门：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)); }
}