数位DP
-
前导零
-
是否压位
例题：
不要62
题面：
求 a 到 b 中不含连续的 62 并且不含 4 的数。
做法：
记 \(g(x)\) 为 0 到 x 之间的 windy 数。
求 \(g(b)-g(a-1)\)
深搜，记长度 x ，上一个数 last,是否压界 k。
枚举此位放几，排除不合法情况，累计答案。
#include<bits/stdc++.h>
using namespace std;
int s[11];
int w;
int dfs(int n,int k,int last)
{
if(n==0) return 1;
int num=0;
int up=k?s[n]:9;
for(int i=0;i<=up;i++)
{
if(i==4) continue;
if(last==6&&i==2) continue;
num+=dfs(n-1,k&(i==s[n]),i);
}
return num;
}
int js(int n)
{
if(n<10){
if(n>=4) return n;
if(n<4) return n+1;
}
w=0;
while(n)
{
w++;
s[w]=n%10;
n=n/10;
}
return dfs(w,1,0);
}
int main()
{
int a,b;
while(scanf("%d%d",&a,&b)){
if(a==0&&b==0) return 0;
printf("%d\n",js(b)-js(a-1));
}
}
P2657 [SCOI2009] windy 数
题面：
不含前导零且相邻两个数字之差至少为 2 的正整数被称为 windy 数。windy 想知道，在 a 和 b 之间，包括 a 和 b ，总共有多少个 windy 数。
做法：
记 \(g(x)\) 为 0 到 x 之间的 windy 数。
求 \(g(b)-g(a-1)\)
设 \(f[x][i]\) 表示长度为 \(x\) 最高位为 \(i\) 的 windy 数的个数
\(0<=i<=9\)
\(0<=x<=10\)
\(f[x][i]=f[x-1][j1]+f[x-1][j2]...\)
\(abs(i-j)>=2\)
记 \(ff[x]\) 为长度小于等于 \(x\) 的 windy 数的个数。
\(ff[x]=ff[x-1]+f[x][0]+f[x][2]+...f[x][9]\)
深搜，记搜到第几位数 x，是否压界 k，上一位数 last。
如果未压界 则可直接返回。
如果压界 根据 last 枚举此位可放的数，搜索并累加答案。
code:
#include<bits/stdc++.h>
using namespace std;
int f[11][11];
int s[11];
int w;
int dfs(int n,int k,int last)
{
if(n==0) return 1;
if(k==0)return f[n+1][last==-2?10:last];
int num=0;
if(last-2>=0)
{
for(int i=0;i<=last-2;i++){
if(i>=s[n]) break;
num+=dfs(n-1,0,i);
}
}
if(last+2<=9)
{
for(int i=last+2;i<=9;i++){
if(i>=s[n]) break;
num+=dfs(n-1,0,i==0?(last==-2?-2:0):i);
}
}
if(abs(s[n]-last)>=2)
num+=dfs(n-1,1,s[n]);
return num;
}
int js(int n)
{
if(n<10) return n+1;
w=0;
while(n)
{
w++;
s[w]=n%10;
n=n/10;
}
return dfs(w,1,-2);
}
int main()
{
for(int i=0;i<=10;i++)
f[1][i]=1;
for(int i=2;i<=10;i++)
{
for(int j=0;j<=9;j++)
{
for(int k=0;k<=9;k++)
{
if(abs(k-j)>=2)
f[i][j]+=f[i-1][k];
}
}
for(int k=1;k<=10;k++)
f[i][10]+=f[i-1][k];
}
int a,b;
cin>>a>>b;
cout<<js(b)-js(a-1);
}
P4124 [CQOI2016]手机号码
题面：
号码中要出现至少 3 个相邻的相同数字；号码中不能同时出现 8 和 4。
手机号码一定是 11 位数，前不含前导的 0。工具接收两个数 L 和 R，自动统计出 [L,R] 区间内所有满足条件的号码数量。
做法：
换汤不换药。
记录剩几位数，上一个数和上上一个数是几，是否有连续的三个数，是否有 4 和 8，是否压界，深搜过程中筛选即可。
code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t[15];
ll r,l,f[12][12][12][2][2][2][2];
ll dfs(int p,int a,int b,bool t3,bool k,bool t4,bool t8)
{
if(t4&&t8) return 0;
if(p==0) return t3;
if(f[p][a][b][t3][k][t4][t8]!=-1) return f[p][a][b][t3][k][t4][t8];
ll num=0;
int up=k?t[p]:9;
for(int i=0;i<=up;i++)
num+=dfs(p-1,b,i,t3||(a==b&&b==i),k&&(i==up),t4||(i==4),t8||(i==8));
return f[p][a][b][t3][k][t4][t8]=num;
}
ll work(ll n)
{
if(n<1e10) return 0;
memset(f,-1,sizeof(f));
int p=0;
while(n){
t[++p]=n%10;
n/=10;
}
ll ans=0;
for(int i=1;i<=t[11];i++)
ans+=dfs(10,-1,i,0,i==t[11],i==4,i==8);
return ans;
}
int main()
{
cin>>l>>r;
cout<<work(r)-work(l-1);
}
P4317 花神的数论题
题面：
设 \(sum_i\) 为 i 二进制下一的个数。
给出一个正整数 N ，花神要问你\(\prod_{i=1}^nsum_i\)
做法：
求出有多少个数有 \(i\) 个一，最后快速幂计算。
总左往右 dp ，找到第一个 1 时将其设为零，后面不压位可 dp，如果遇到 1 （设为第 x 个一），那么可将前 x 个变为一，此为变为 0， 为一种新方案，供后续 dp，计入前面原数为一的为一，此位为零的方案。最后记上全为一的方案。
code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
ll n;
int a[65];
ll mod=10000007;
int p;
ll qm(ll x,int p)
{
if(p==0) return 1;
ll tmp=qm(x,p>>1);
if(p&1) return tmp*tmp%mod*x%mod;
else return tmp*tmp%mod;
}
signed main()
{
cin>>n;
for(int j=49;~j;--j){
for(int i=49;i;--i)
a[i]+=a[i-1];
if(n>>j&1) ++a[p++];
}
a[p]++;
ll ans=1;
for(int i=1;i<=55;i++)
ans=(ans*qm(i,a[i]))%mod;
cout<<ans;
}