2017计蒜之道复赛 A.阿里云秘钥池(莫比乌斯反演+数位DP)

题解

  计蒜之道怎么这么喜欢出数位DP(大雾
  挺显然的一个题,这题用递推+记忆化的写法比较优美,记录一下。
  设fi,jf_{i,j}表示前ii位,上一位为jj的方案数,则有:

fi,j=l=1p1fi1,l×[(j,l)=1]=l=1p1fi1,l×k(j,l)μ(k)=kjμ(k)l=1p1kfi1,k×l\begin{aligned} f_{i,j}&=\sum_{l=1}^{p-1}f_{i-1,l}\times [(j,l)=1]\\ &=\sum_{l=1}^{p-1}f_{i-1,l}\times \sum_{k|(j,l)}\mu(k)\\ &=\sum_{k|j}\mu(k)\sum_{l=1}^{\left \lfloor \frac{p-1}{k} \right \rfloor} f_{i-1,k\times l} \end{aligned}

  YY一下发现从ii转移到i+1i+1可以做到O(p ln p)O(p\ ln\ p),然后这题就完了。
  这么看来计蒜之客要进决赛其实可能也不是很难?

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=100010, inf=1e9;
int n, cntp, T, p;
int pri[maxn], mu[maxn], digit[70];
ll l, r;
ll f[70][maxn], sum[maxn];
bool v[maxn];

inline void read(int &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;	
}

inline void getmu(int n)
{
    mu[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!v[i]) mu[i]=-1, pri[++cntp]=i;
        for(int j=1;pri[j]*i<=n;j++)
        {
            v[pri[j]*i]=1;
            if(i%pri[j]==0) 
            {
                mu[pri[j]*i]=0;
                break;
            }
            mu[pri[j]*i]=-mu[i];
        }
    }
} 

inline int gcd(int a, int b){return b?gcd(b, a%b):a;}

ll dfs(int pos, int pre, bool limit)
{
	if(!pos) return 1ll;
	if(!limit && f[pos][pre]) return f[pos][pre];
	ll ans=0; int up=limit?digit[pos]:p-1;
	for(int i=1;i<=up;i++) if(gcd(pre, i)==1) ans+=dfs(pos-1, i, limit && i==up);
	if(!limit) f[pos][pre]=ans;
	return ans; 
}

inline ll solve(ll x)
{
	if(!x) return 0; 
	int cnt=0; while(x) digit[++cnt]=x%p, x/=p;
	ll ans=0;
	for(int i=0;i<cnt-1;i++) for(int j=1;j<p;j++) ans+=f[i][j];
	ans+=dfs(cnt, 1, 1);
	return ans;
}
 
int main()
{
	getmu(100000); read(T);
	while(T--)
	{
		scanf("%lld%lld", &l, &r); read(p);
		ll x=r; int n=0; 
		while(x) digit[++n]=x%p, x/=p;
		for(int i=0;i<=n-1;i++) for(int j=0;j<p;j++) f[i][j]=0;
		for(int i=0;i<p;i++) f[0][i]=1;
		for(int i=0;i<n-1;i++)
		{
			for(int j=1;j<p;j++)
			{
				ll sum=0;
				for(int k=j;k<p;k+=j) sum+=f[i][k];
				for(int k=j;k<p;k+=j) f[i+1][k]+=sum*mu[j];
			}
		}
		printf("%lld\n", solve(r)-solve(l-1));
	}
}