数位DP AC十道题目以上 成就达成
八月份！三个月！想想就令人兴奋呢
开始写总结啦
貌似简单的数位DP只需要改改模板就可以啦
就按照我的做题顺序开始总结吧
先是学习了一发模板：http://www.cnblogs.com/jffifa/archive/2012/08/17/2644847.html
但是一开始学的不是很深刻，导致后来做题的时候犯了很多错误
hdu 2089
数字中不能出现62和4
一开始设计的状态是f[i][j]表示长度为i且上一个数字为j，然后写了一发过来
其实状态是可以精简的，可以精简成f[i][0/1]表示长度为i上一个数字是否为6
精简后的状态比裸DP快的多，精简后的代码
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
int L,R;
int f[12][2];//0 无6 1 有6
int Num[12],len=0;
void check(int n){
memset(Num,0,sizeof(Num));len=0;
if(!n){Num[++len]=0;return;}
while(n)Num[++len]=n%10,n/=10;
}
int DFS(int pos,int six,int flag){
if(!pos)return 1;
if(!flag&&f[pos][six]!=-1)return f[pos][six];
int tmp=0,u=flag?Num[pos]:9;
for(int i=0;i<=u;++i){
if(i==4)continue;
if(six&&i==2)continue;
tmp+=DFS(pos-1,i==6,flag&&i==u);
}return flag?tmp:f[pos][six]=tmp;
}
int main(){
while(scanf("%d%d",&L,&R)==2){
if(!L&&!R)break;
check(R);memset(f,-1,sizeof(f));
R=DFS(len,0,1);
check(L-1);memset(f,-1,sizeof(f));
L=DFS(len,0,1);
printf("%d
",R-L);
}return 0;
}
hdu 3555
数字中不能出现49，跟上道题目做法一样
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
LL n;
LL f[22][2];//0 不是4 1 是4
int T;
int Num[22],len;
void check(LL n){
memset(Num,0,sizeof(Num));len=0;
if(!n){Num[++len]=0;return;}
while(n)Num[++len]=n%10,n/=10;
}
LL DFS(int pos,int four,int flag){
if(!pos)return 1;
if(!flag&&f[pos][four]!=-1)return f[pos][four];
LL tmp=0;
int u=flag?Num[pos]:9;
for(int i=0;i<=u;++i){
if(four&&i==9)continue;
tmp+=DFS(pos-1,i==4,flag&&i==u);
}return flag?tmp:f[pos][four]=tmp;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%lld",&n);
check(n);memset(f,-1,sizeof(f));
printf("%lld
",n+1-DFS(len,0,1));
}return 0;
}
hdu 3652
数字中要求有13这个子串同时自身能被13整除
加一维0/1/2表示当前数字和13的匹配长度
再加一维记录余数即可
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int t[13];
int f[13][13][3];
int Num[13],len=0;
void check(int n){
memset(Num,0,sizeof(Num));len=0;
if(!n){Num[++len]=0;return;}
while(n)Num[++len]=n%10,n/=10;
}
int DFS(int pos,int mod,int one,int flag){
if(!pos){
if(one==2&&!mod)return 1;
return 0;
}
if(!flag&&f[pos][mod][one]!=-1)return f[pos][mod][one];
int tmp=0,u=flag?Num[pos]:9;
for(int i=0;i<=u;++i){
int now=one;
if(now!=2){
if(now==1&&i==3)now=2;
else if(i==1)now=1;
else now=0;
}
tmp+=DFS(pos-1,(mod+i*t[pos])%13,now,flag&&i==u);
}return flag?tmp:f[pos][mod][one]=tmp;
}
int main(){
t[1]=1;
for(int i=2;i<=10;++i)t[i]=t[i-1]*10;
while(scanf("%d",&n)==1){
check(n);memset(f,-1,sizeof(f));
n=DFS(len,0,0,1);
printf("%d
",n);
}return 0;
}
codeforces #55 D
求能被自己各位非零数字整除的数字
我们发现我们需要记录这个数字%(1-9)的值，如果强行加维会爆炸
但是我们发现对于%p来说，假设我们知道一个数字%(k*p)的值，我们就可以知道其%p的值
那么我们只需要记录这个数字%2520的余数就可以了(LCM(1-9)=2520)
之后我们需要知道这个数字中那些数字出现过，在这里其实我们只需要知道2-9是否出现过就可以了
可以在加一维状态压缩来记录
更好一点的做法是我们发现%2=0和%5=0我们只需要判断最后一位数字就可以了
而去掉2和5之后的LCM=252，这样我们就可以把状态数变成了原来的1/10
但是本人还是写的2520的QAQ
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
int T;
int Num[22],len=0;
LL f[22][2520][256];
LL t[22];
LL L,R;
void check(LL n){
memset(Num,0,sizeof(Num));len=0;
if(!n){Num[++len]=0;return;}
while(n)Num[++len]=n%10,n/=10;
}
LL DFS(int pos,int mod,int S,int flag){
if(!pos){
for(int i=0;i<8;++i){
if(S>>i&1){
if(mod%(i+2))return 0;
}
}return 1;
}
if(!flag&&f[pos][mod][S]!=-1)return f[pos][mod][S];
LL tmp=0;
int u=flag?Num[pos]:9;
for(int i=0;i<=u;++i){
int now=S;
if(i>1)now|=(1<<(i-2));
tmp=tmp+DFS(pos-1,(mod+i*t[pos])%2520,now,flag&&i==u);
}return flag?tmp:f[pos][mod][S]=tmp;
}
int main(){
t[1]=1;
for(int i=2;i<=20;++i)t[i]=t[i-1]*10;
scanf("%d",&T);
memset(f,-1,sizeof(f));
while(T--){
scanf("%lld%lld",&L,&R);
check(R);
R=DFS(len,0,0,1);
check(L-1);
L=DFS(len,0,0,1);
printf("%lld
",R-L);
}return 0;
}
poj 3252
求有多少个二进制串中0的数量不少于1的数量
状态是很显然的，f[i][j]表示长度为i，1的数量为j
然后直接裸上DP就可以了，注意此时前导零对答案会有影响
所以我采用的方法是<len的直接预处理计算
=len的采用记忆化搜索
其实可以直接记忆化搜索，在多传一个参数表示是否是首位就可以啦
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;
int L,R;
int Num[35],len=0;
int f[35][35],ans;
int dp[35][35];
void check(int n){
memset(Num,0,sizeof(Num));len=0;
if(!n){Num[++len]=0;return;}
while(n)Num[++len]=(n&1),n>>=1;
}
int DFS(int pos,int num_one,int flag){
if(!pos){
if(num_one<=(len>>1))return 1;
return 0;
}
if(!flag&&f[pos][num_one]!=-1)return f[pos][num_one];
int tmp=0,u=flag?Num[pos]:1;
for(int i=(pos==len?1:0);i<=u;++i){
tmp=tmp+DFS(pos-1,num_one+(i==1),flag&&i==u);
}
return flag?tmp:f[pos][num_one]=tmp;
}
int main(){
scanf("%d%d",&L,&R);
dp[1][1]=1;
for(int i=1;i<32;++i){
for(int j=0;j<=i;++j){
dp[i+1][j+1]+=dp[i][j];
dp[i+1][j]+=dp[i][j];
}
}
check(R);memset(f,-1,sizeof(f));
R=DFS(len,0,1);
for(int i=1;i<len;++i){
for(int j=0;j<=(i>>1);++j)R+=dp[i][j];
}
check(L-1);memset(f,-1,sizeof(f));
L=DFS(len,0,1);
for(int i=1;i<len;++i){
for(int j=0;j<=(i>>1);++j)L+=dp[i][j];
}
printf("%d
",R-L);
return 0;
}
hdu 3709
定义平衡数是存在一个重心，使得左右连边的权重和相等的数
求给定区间内有多少个平衡数
首先我们可以证明在没有前导零的情况下，一个平衡数最多只有一个重心
因为重心移动一定是一边加上一个正整数，另一边减去一个正整数，不可能存在继续平衡的可能性
那么由于位数很小，我们不妨枚举重心，我们发现实际上可能的权重和也很小
就设f[i][j]表示位数为i，权重和为j的方案就可以啦
然后如果考虑不考虑前导零的话，最后还要减去000000这种情况
由于L>=0,所以要特判L=0的情况
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
int T,now,cur;
LL L,R;
LL f[22][3010];
int Num[22],len=0;
void check(LL n){
memset(Num,0,sizeof(Num));len=0;
if(!n){Num[++len]=0;return;}
while(n)Num[++len]=n%10,n/=10;
}
LL DFS(int pos,int sum,int flag){
if(!pos){
if(sum==0)return 1;
return 0;
}
if(!flag&&f[pos][sum]!=-1)return f[pos][sum];
LL tmp=0;int u=flag?Num[pos]:9;
for(int i=0;i<=u;++i){
int QAQ=sum+i*(pos-now);
if(QAQ<0)continue;
tmp+=DFS(pos-1,QAQ,flag&&i==u);
}return flag?tmp:f[pos][sum]=tmp;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%lld%lld",&L,&R);
check(R);R=0;cur=len;
for(int i=1;i<=len;++i){
now=i;
memset(f,-1,sizeof(f));
R+=DFS(len,0,1);
}
if(L==0)L=0,len=1;
else{
check(L-1);L=0;
for(int i=1;i<=len;++i){
now=i;
memset(f,-1,sizeof(f));
L+=DFS(len,0,1);
}
}printf("%lld
",R-L-(cur-len));
}return 0;
}
SPOJ BALNUM
求有多少个数字出现的每个偶数数字出现了奇数次，出现的每个奇数数字出现了偶数次
我们发现一个数字最多只有3种情况，没出现，出现奇数次，出现偶数次
用三进制表示状态压缩即可，自己的代码写的略丑
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long LL;
int T;
int Num[22],len=0;
bool vis[60010];
int code[12];
LL f[22][60010];
LL L,R;
//0 没出现 1 出现奇数 2 出现偶数
void decode(int S,int *code){
for(int i=0;i<=9;++i){
code[i]=S%3;S/=3;
}return;
}
int encode(int *code){
int S=0;
for(int i=9;i>=0;--i)S=S*3+code[i];
return S;
}
bool judge(int S){
decode(S,code);
for(int i=0;i<=9;++i){
if(i&1){
if(code[i]==1)return false;
}else if(code[i]==2)return false;
}return true;
}
void check(LL n){
memset(Num,0,sizeof(Num));len=0;
if(!n){Num[++len]=0;return;}
while(n)Num[++len]=n%10,n/=10;
}
LL DFS(int pos,int S,int flag,int first){
if(!pos){
if(vis[S])return 1;
return 0;
}
if(!flag&&f[pos][S]!=-1)return f[pos][S];
LL tmp=0;int u=flag?Num[pos]:9;
int ch[12];
for(int i=0;i<=u;++i){
decode(S,ch);
if(i==0&&first);
else{
if(ch[i]==0)ch[i]=1;
else if(ch[i]==1)ch[i]=2;
else ch[i]=1;
}
tmp+=DFS(pos-1,encode(ch),flag&&i==u,first&&i==0);
}return flag?tmp:f[pos][S]=tmp;
}
int main(){
scanf("%d",&T);
for(int i=0;i<59049;++i)if(judge(i))vis[i]=true;
while(T--){
scanf("%lld%lld",&L,&R);
check(R);memset(f,-1,sizeof(f));
R=DFS(len,0,1,1);
check(L-1);memset(f,-1,sizeof(f));
L=DFS(len,0,1,1);
printf("%lld
",R-L);
}return 0;
}
BZOJ 1026
windy数，没什么好说的
只是实验一下新模板的效果
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;
int L,R;
int f[12][12];
int dp[12][12];
int Num[12],len=0;
void check(int n){
memset(Num,0,sizeof(Num));len=0;
if(!n){Num[++len]=0;return;}
while(n)Num[++len]=n%10,n/=10;
}
int DFS(int pos,int la,int flag){
if(!pos)return 1;
if(!flag&&f[pos][la]!=-1)return f[pos][la];
int tmp=0,u=flag?Num[pos]:9;
for(int i=(pos==len?1:0);i<=u;++i){
if(pos!=len&&abs(i-la)<2)continue;
tmp+=DFS(pos-1,i,flag&&i==u);
}return flag?tmp:f[pos][la]=tmp;
}
int main(){
scanf("%d%d",&L,&R);
for(int i=1;i<=9;++i)dp[1][i]=1;
for(int i=1;i<10;++i){
for(int j=0;j<=9;++j){
if(dp[i][j]){
for(int k=0;k<=9;++k){
if(abs(j-k)<2)continue;
dp[i+1][k]+=dp[i][j];
}
}
}
}
memset(f,-1,sizeof(f));
check(R);R=DFS(len,0,1);
for(int i=1;i<len;++i)for(int j=0;j<=9;++j)R+=dp[i][j];
check(L-1);L=DFS(len,0,1);
for(int i=1;i<len;++i)for(int j=0;j<=9;++j)L+=dp[i][j];
printf("%d
",R-L);
return 0;
}
BZOJ 4521
CQOI的模板题目，限定11位真是兹磁啊，留下了L=10^11的大陷阱
加一维表示上一个数是多少
再加一维0/1/2/3表示连续的数字个数
再加一维表示是否有8，再加一维表示是否有4
模板写起来就好啦
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long LL;
int Num[13],len=0;
LL L,R;
LL f[13][10][4][2][2];// 位数 0/1/2/3 是否有8 是否有4
void check(LL n){
memset(Num,0,sizeof(Num));len=0;
if(!n){Num[++len]=0;return;}
while(n)Num[++len]=n%10,n/=10;
}
LL DFS(int pos,int la,int go_num,int eight,int four,int flag){
if(!pos){
if((go_num!=3)||(eight&&four))return 0;
return 1;
}
if(!flag&&f[pos][la][go_num][eight][four]!=-1)return f[pos][la][go_num][eight][four];
LL tmp=0;int u=flag?Num[pos]:9;
for(int i=(pos==len?1:0);i<=u;++i){
int now=go_num;
if(now==3);
else{
if(i==la)now++;
else now=1;
}
tmp+=DFS(pos-1,i,now,eight|(i==8),four|(i==4),flag&&i==u);
}return flag?tmp:f[pos][la][go_num][eight][four]=tmp;
}
int main(){
scanf("%lld%lld",&L,&R);
memset(f,-1,sizeof(f));
check(R);R=DFS(len,0,0,0,0,1);
check(L-1);
if(len==11)L=DFS(len,0,0,0,0,1);
else L=0;
printf("%lld
",R-L);
return 0;
}
hdu 4734
一开始被吓到了，开始考虑如何暴力的时候很惊讶的发现F(x)的范围很小，不到20000
那么我们缀一维表示F(x)的值就可以啦
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long LL;
int T,fit,A,B,kase;
int f[12][20010];
int Num[12],len=0;
void check(int n){
memset(Num,0,sizeof(Num));len=0;
if(!n){Num[++len]=0;return;}
while(n)Num[++len]=n%10,n/=10;
}
int DFS(int pos,int sum,int flag){
if(!pos)return sum>=0;
if(sum<0)return 0;
if(!flag&&f[pos][sum]!=-1)return f[pos][sum];
int tmp=0,u=flag?Num[pos]:9;
for(int i=0;i<=u;++i){
tmp+=DFS(pos-1,sum-i*(1<<(pos-1)),flag&&i==u);
}return flag?tmp:f[pos][sum]=tmp;
}
int main(){
scanf("%d",&T);
memset(f,-1,sizeof(f));
while(T--){
scanf("%d%d",&A,&B);kase++;
check(A);fit=0;
for(int i=1;i<=len;++i)fit=fit+Num[i]*(1<<(i-1));
check(B);B=DFS(len,fit,1);
printf("Case #%d: %d
",kase,B);
}return 0;
}
hdu 4507
不能有7，转移的时候直接判
缀两维表示两个限制%7的余数
唯一的问题是求平方和
式子参照我在cojs上出的题目就可以啦
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;
typedef long long LL;
const int mod=1e9+7;
int T;
int Num[22],len=0;
LL L,R;
LL t[22];
struct num{
LL s0,s1,s2;
void clear(){s0=s1=s2=0;}
}f[22][7][7];
void check(LL n){
memset(Num,0,sizeof(Num));len=0;
if(!n){Num[++len]=0;return;}
while(n)Num[++len]=n%10,n/=10;
}
num DFS(int pos,int num_mod,int sum_mod,int flag){
if(!pos){
num tmp;tmp.clear();
if(num_mod!=0&&sum_mod!=0)tmp.s0=1;
else tmp.s0=0;
return tmp;
}
if(!flag&&f[pos][num_mod][sum_mod].s0!=-1)return f[pos][num_mod][sum_mod];
num tmp;tmp.clear();
int u=flag?Num[pos]:9;
for(int i=0;i<=u;++i){
if(i==7)continue;
num now=DFS(pos-1,(num_mod+i*t[pos])%7,(sum_mod+i)%7,flag&&i==u);
LL sum=i*t[pos]%mod;
tmp.s0=tmp.s0+now.s0;if(tmp.s0>=mod)tmp.s0-=mod;
tmp.s1=tmp.s1+now.s1;if(tmp.s1>=mod)tmp.s1-=mod;
tmp.s1=tmp.s1+now.s0*sum%mod;if(tmp.s1>=mod)tmp.s1-=mod;
tmp.s2=tmp.s2+now.s2;if(tmp.s2>=mod)tmp.s2-=mod;
tmp.s2=tmp.s2+now.s1*sum%mod*2%mod;if(tmp.s2>=mod)tmp.s2-=mod;
tmp.s2=tmp.s2+now.s0*sum%mod*sum%mod;if(tmp.s2>=mod)tmp.s2-=mod;
}return flag?tmp:f[pos][num_mod][sum_mod]=tmp;
}
int main(){
t[1]=1;
for(int i=2;i<=20;++i)t[i]=t[i-1]*10;
scanf("%d",&T);
memset(f,-1,sizeof(f));
while(T--){
scanf("%lld%lld",&L,&R);
check(R);num A=DFS(len,0,0,1);
check(L-1);num B=DFS(len,0,0,1);
printf("%lld
",(A.s2-B.s2+mod)%mod);
}return 0;
}
hdu 4352
求[L,R]中有多少个数字的LIS恰好为K
首先注意到LIS最大是10，我们考虑如何求LIS
我们nlogn求LIS的时候对于每个长度记录最小的结尾即可
这样我们就可以状态压缩了
压缩的原理是这样的：如果某个数字i对应压缩位为1，那么[0,i]中有多少个1就是长度，这个数字表示这个长度的最小结尾
每次数位DP增加一个数字后更新即可
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;
typedef long long LL;
int T,k,kase;
int Num[22],len=0;
int num[1024];
LL L,R;
LL f[22][1024][11];
void check(LL n){
memset(Num,0,sizeof(Num));len=0;
if(!n){Num[++len]=0;return;}
while(n)Num[++len]=n%10,n/=10;
}
void encode(int &S,int pos){
for(int i=pos;i<=9;++i){
if(S>>i&1){S^=(1<<i);break;}
}S|=(1<<pos);return;
}
LL DFS(int pos,int S,int flag,int first){
if(!pos)return num[S]==k;
if(!flag&&f[pos][S][k]!=-1)return f[pos][S][k];
LL tmp=0;int u=flag?Num[pos]:9;
for(int i=0;i<=u;++i){
int now=S;
if(first&&i==0);
else encode(now,i);
tmp+=DFS(pos-1,now,flag&&i==u,first&&i==0);
}return flag?tmp:f[pos][S][k]=tmp;
}
int main(){
scanf("%d",&T);
for(int i=1;i<1024;++i)num[i]=num[i>>1]+(i&1);
memset(f,-1,sizeof(f));
while(T--){
scanf("%lld%lld",&L,&R);
scanf("%d",&k);kase++;
check(R);R=DFS(len,0,1,1);
check(L-1);L=DFS(len,0,1,1);
printf("Case #%d: %lld
",kase,R-L);
}return 0;
}
ZOJ 3494
给定一个把十进制数字转化的方法
之后给定若干的禁止串，求[L,R]中不含禁止串的数字有多少个
建立AC自动机，之后设f[i][j]表示走了i步走到了AC自动机的j节点
预处理判断是否合法就可以了
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<queue>
using namespace std;
typedef long long LL;
const int maxn=2010;
const int mod=1000000009;
int T,n,len;
char s[maxn];
char Num[maxn];
int Go[maxn][10];
LL f[210][maxn];
LL L,R;
queue<int>Q;
struct trie{
int cnt;
int next[maxn][2];
int fail[maxn];
bool vis[maxn];
void init(){
cnt=1;fail[1]=0;vis[1]=false;
next[1][0]=next[1][1]=0;
}
int Newnode(){
++cnt;next[cnt][0]=next[cnt][1]=0;
fail[cnt]=0;vis[cnt]=false;return cnt;
}
void insert(){
int L=strlen(s+1),now=1;
for(int i=1;i<=L;++i){
int nxt=s[i]-'0';
if(!next[now][nxt])next[now][nxt]=Newnode();
now=next[now][nxt];
}vis[now]=true;return;
}
void build_fail(){
Q.push(1);fail[1]=0;
while(!Q.empty()){
int u=Q.front();Q.pop();
vis[u]|=vis[fail[u]];
for(int i=0;i<2;++i){
int k=fail[u];
while(k&&!next[k][i])k=fail[k];
if(next[u][i]){
fail[next[u][i]]=k?next[k][i]:1;
Q.push(next[u][i]);
}else next[u][i]=k?next[k][i]:1;
}
}return;
}
int Let_Go(int now,int num){
if(vis[now])return -1;
for(int i=3;i>=0;--i){
now=next[now][num>>i&1];
if(vis[now])return -1;
}return now;
}
}AC;
void Get_Pre(){
memset(f,-1,sizeof(f));
for(int i=1;i<=AC.cnt;++i){
for(int j=0;j<=9;++j){
Go[i][j]=AC.Let_Go(i,j);
}
}return;
}
void flip(){for(int i=1;i<=len;++i)Num[len-i+1]=s[i]-'0';}
LL DFS(int pos,int S,int flag,int first){
if(!pos)return 1;
if(!flag&&!first&&f[pos][S]!=-1)return f[pos][S];
LL ans=0;
if(first){
ans+=DFS(pos-1,S,flag&&Num[pos]==0,true);
if(ans>=mod)ans-=mod;
}else{
if(Go[S][0]!=-1)ans+=DFS(pos-1,Go[S][0],flag&&Num[pos]==0,false);
if(ans>=mod)ans-=mod;
}
int u=flag?Num[pos]:9;
for(int i=1;i<=u;++i){
if(Go[S][i]!=-1){
ans+=DFS(pos-1,Go[S][i],flag&&i==u,false);
if(ans>=mod)ans-=mod;
}
}return (flag||first)?ans:f[pos][S]=ans;
}
int main(){
scanf("%d",&T);
while(T--){
AC.init();
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%s",s+1);
AC.insert();
}AC.build_fail();
Get_Pre();
scanf("%s",s+1);
len=strlen(s+1);
for(int i=len;i>=1;--i){
if(s[i]>'0'){s[i]--;break;}
s[i]='9';
}
flip();L=DFS(len,1,1,1);
scanf("%s",s+1);
len=strlen(s+1);
flip();R=DFS(len,1,1,1);
printf("%lld
",(R-L+mod)%mod);
}return 0;
}
BZOJ 3530
上面那道题的弱化版，直接写就可以啦
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long LL;
const int maxn=1510;
const int mod=1e9+7;
int n,len;
char s[maxn];
char p[maxn];
char Num[maxn];
queue<int>Q;
int Go[maxn][10];
LL f[maxn][maxn];
LL ans;
struct trie{
int cnt;
int next[maxn][10];
int fail[maxn];
bool vis[maxn];
void init(){cnt=1;}
void insert(){
int L=strlen(p+1),now=1;
for(int i=1;i<=L;++i){
int nxt=p[i]-'0';
if(!next[now][nxt])next[now][nxt]=++cnt;
now=next[now][nxt];
}vis[now]=true;return;
}
void build_fail(){
Q.push(1);
while(!Q.empty()){
int u=Q.front();Q.pop();
vis[u]|=vis[fail[u]];
for(int i=0;i<10;++i){
int k=fail[u];
while(k&&!next[k][i])k=fail[k];
if(next[u][i]){
fail[next[u][i]]=k?next[k][i]:1;
Q.push(next[u][i]);
}else next[u][i]=k?next[k][i]:1;
}
}return;
}
LL DFS(int pos,int S,int flag,int first){
if(!pos)return 1;
if(!flag&&!first&&f[pos][S]!=-1)return f[pos][S];
LL tmp=0;
if(first){
tmp+=DFS(pos-1,S,flag&&Num[pos]==0,1);
if(tmp>=mod)tmp-=mod;
}else{
if(!vis[next[S][0]]){
tmp+=DFS(pos-1,next[S][0],flag&&Num[pos]==0,0);
if(tmp>=mod)tmp-=mod;
}
}
int u=flag?Num[pos]:9;
for(int i=1;i<=u;++i){
if(!vis[next[S][i]]){
tmp+=DFS(pos-1,next[S][i],flag&&i==Num[pos],0);
if(tmp>=mod)tmp-=mod;
}
}return (flag||first)?tmp:f[pos][S]=tmp;
}
}AC;
void flip(){for(int i=1;i<=len;++i)Num[len-i+1]=s[i]-'0';}
int main(){
scanf("%s",s+1);
AC.init();scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%s",p+1);
AC.insert();
}AC.build_fail();
len=strlen(s+1);
memset(f,-1,sizeof(f));
flip();ans=AC.DFS(len,1,1,1);
printf("%lld
",(ans-1+mod)%mod);
return 0;
}
BZOJ 3209
枚举1的个数然后做数位DP，之后快速幂乘起来就好啦
值得一提的是这个题可以直接用组合数算数位DP的结果
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long LL;
const int mod=10000007;
LL n,ans;
LL f[72][72];
int Num[72],len=0;
LL pow_mod(LL v,LL p){
LL tmp=1;
while(p){
if(p&1)tmp=tmp*v%mod;
v=v*v%mod;p>>=1;
}return tmp;
}
void check(LL n){
memset(Num,0,sizeof(Num));len=0;
if(!n){Num[++len]=0;return;}
while(n)Num[++len]=(n&1),n>>=1;
}
LL DFS(int pos,int one,int flag){
if(one<0)return 0;
if(!pos){
if(!one)return 1;
return 0;
}
if(!flag&&f[pos][one]!=-1)return f[pos][one];
LL tmp=0;int u=flag?Num[pos]:1;
for(int i=0;i<=u;++i){
tmp=tmp+DFS(pos-1,one-(i==1),flag&&i==u);
}return flag?tmp:f[pos][one]=tmp;
}
int main(){
scanf("%lld",&n);
check(n);ans=1;memset(f,-1,sizeof(f));
for(int i=1;i<=len;++i){
LL now=DFS(len,i,1);
ans=ans*pow_mod(1LL*i,now)%mod;
}printf("%lld
",ans);
return 0;
}
BZOJ 3329
x^3x=2x等价于x^2x=3x
我们知道异或是不进位加法
又因为x+2x=3x
所以当且仅当满足x中任意相邻两个数不都是1才是方程的一组解
即x&(x<<1)=0
对于第一问我们直接做数位DP就可以了
第二问我们设f[i][0/1]表示i位且上一位是0/1
f[i][0]=f[i-1][0]+f[i-1][1]
f[i][1]=f[i-1][0]
之后直接矩阵乘法就可以了
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long LL;
const int mod=1e9+7;
int T;
int Num[72],len=0;
LL f[72][2];//上一位是多少
LL n,sum;
struct Matrix{
LL a[2][2];
Matrix(){memset(a,0,sizeof(a));}
}A,ans;
void check(LL n){
memset(Num,0,sizeof(Num));len=0;
if(!n){Num[++len]=0;return;}
while(n)Num[++len]=(n&1),n>>=1;
}
LL DFS(int pos,int la,int flag){
if(!pos)return 1;
if(!flag&&f[pos][la]!=-1)return f[pos][la];
LL tmp=0;int u=flag?Num[pos]:1;
for(int i=0;i<=u;++i){
if(la==1&&i==1)continue;
tmp=tmp+DFS(pos-1,i,flag&&i==u);
}return flag?tmp:f[pos][la]=tmp;
}
void build_Matrix(){
A.a[0][0]=1;A.a[0][1]=1;
A.a[1][0]=1;A.a[1][1]=0;
}
Matrix operator *(const Matrix &A,const Matrix &B){
Matrix C;
for(int i=0;i<2;++i){
for(int j=0;j<2;++j){
for(int k=0;k<2;++k){
C.a[i][j]=C.a[i][j]+A.a[i][k]*B.a[k][j]%mod;
if(C.a[i][j]>=mod)C.a[i][j]-=mod;
}
}
}return C;
}
Matrix pow_mod(Matrix v,LL p){
Matrix tmp;
for(int i=0;i<2;++i)tmp.a[i][i]=1;
while(p){
if(p&1)tmp=tmp*v;
v=v*v;p>>=1;
}return tmp;
}
int main(){
scanf("%d",&T);
memset(f,-1,sizeof(f));
build_Matrix();
while(T--){
scanf("%lld",&n);
check(n);
sum=DFS(len,0,1);
printf("%lld
",sum-1);
ans.a[0][0]=1;ans.a[0][1]=0;
ans=ans*pow_mod(A,n);
printf("%lld
",(ans.a[0][1]+ans.a[0][0])%mod);
}return 0;
}
hdu 3943
求(L,R]第k个nya数，nya数定义为恰好有x个4和y个7的数
我们二分之后问题转化成了数位DP，直接做就可以了，略坑的是这个区间是左开右闭的
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;
typedef long long LL;
int T,x,y,n,kase;
int Num[22],len=0;
LL P,Q,L,R,k;
LL f[22][22][22];
void check(LL n){
memset(Num,0,sizeof(Num));len=0;
if(!n){Num[++len]=0;return;}
while(n)Num[++len]=n%10,n/=10;
}
LL DFS(int pos,int four,int seven,int flag){
if(four<0||seven<0)return 0;
if(!pos){
if(!four&&!seven)return 1;
return 0;
}
if(!flag&&f[pos][four][seven]!=-1)return f[pos][four][seven];
LL tmp=0;int u=flag?Num[pos]:9;
for(int i=0;i<=u;++i){
tmp=tmp+DFS(pos-1,four-(i==4),seven-(i==7),flag&&i==u);
}return flag?tmp:f[pos][four][seven]=tmp;
}
int main(){
scanf("%d",&T);
memset(f,-1,sizeof(f));
while(T--){
scanf("%lld%lld",&P,&Q);
scanf("%d%d",&x,&y);kase++;
check(P);L=DFS(len,x,y,1);
check(Q);R=DFS(len,x,y,1);
printf("Case #%d:
",kase);
scanf("%d",&n);
while(n--){
scanf("%lld",&k);
if(R-L<k){printf("Nya!
");continue;}
LL l=P,r=Q;
while(l<r){
LL mid=(l+r)>>1;
check(mid);
LL ans=DFS(len,x,y,1);
if(ans-L<k)l=mid+1;
else r=mid;
}printf("%lld
",r);
}
}return 0;
}
BZOJ 2757
求[L,R]中各位数字的乘积为k的数有多少个
首先我们会发现k只会有2,3,5,7这4个素因子
而进一步我们很容易发现满足这个条件的k是很少的
那么我们可以把满足条件的k哈希掉，数位DP即可
注意当k=0时，数位中只要至少有一个0就可以了，我采取的处理方法是又写了另外一个数位DP
这道题目我的代码略丑，其实一开始处理出来所以合法的k是最好的，在中间过程处理的话会变麻烦
至于求数字和，都求过平方和了这就随意做了
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int mod=20120427;
const int maxn=300010;
const int MOD=1333331;
int T;
LL L,R,k;
LL t[22];
struct num{
LL s0,s1;
void clear(){s0=s1=0;}
}dp[22][2],f[22][maxn],A,B;
int Num[22],len=0;
struct HASHMAP{
int cnt;
int h[MOD+10],next[maxn];
LL st[maxn];
int ask(LL S){
int key=S%MOD;
for(int i=h[key];i;i=next[i]){
if(st[i]==S)return i;
}
++cnt;next[cnt]=h[key];h[key]=cnt;
st[cnt]=S;return cnt;
}
}H;
void check(LL n){
memset(Num,0,sizeof(Num));len=0;
if(!n){Num[++len]=0;return;}
while(n)Num[++len]=n%10,n/=10;
}
num DP(int pos,int zero,int flag,int first){
if(!pos){
num tmp;tmp.clear();
tmp.s0=zero;
return tmp;
}
if(!flag&&!first&&dp[pos][zero].s0!=-1)return dp[pos][zero];
num tmp,now;tmp.clear();
if(first){
now=DP(pos-1,0,0,1);
tmp.s0=tmp.s0+now.s0;if(tmp.s0>=mod)tmp.s0-=mod;
tmp.s1=tmp.s1+now.s1;if(tmp.s1>=mod)tmp.s1-=mod;
}else{
now=DP(pos-1,1,flag&&Num[pos]==0,0);
tmp.s0=tmp.s0+now.s0;if(tmp.s0>=mod)tmp.s0-=mod;
tmp.s1=tmp.s1+now.s1;if(tmp.s1>=mod)tmp.s1-=mod;
}
int u=flag?Num[pos]:9;
for(int i=1;i<=u;++i){
now=DP(pos-1,zero,flag&&i==u,0);
tmp.s0=tmp.s0+now.s0;if(tmp.s0>=mod)tmp.s0-=mod;
tmp.s1=tmp.s1+now.s1;if(tmp.s1>=mod)tmp.s1-=mod;
tmp.s1=tmp.s1+i*t[pos]*now.s0%mod;if(tmp.s1>=mod)tmp.s1-=mod;
}return (flag||first)?tmp:dp[pos][zero]=tmp;
}
num DFS(int pos,LL mul,int flag,int first){
if(!pos){
num tmp;tmp.clear();
if(!first&&mul==1)tmp.s0=1;
return tmp;
}
int cur=H.ask(mul);
if(!first&&!flag&&f[pos][cur].s0!=-1)return f[pos][cur];
num tmp,now;tmp.clear();
if(first){
now=DFS(pos-1,mul,0,first);
tmp.s0=tmp.s0+now.s0;if(tmp.s0>=mod)tmp.s0-=mod;
tmp.s1=tmp.s1+now.s1;if(tmp.s1>=mod)tmp.s1-=mod;
}
int u=flag?Num[pos]:9;
for(int i=1;i<=u;++i){
if(mul%i==0){
now=DFS(pos-1,mul/i,flag&&i==u,0);
tmp.s0=tmp.s0+now.s0;if(tmp.s0>=mod)tmp.s0-=mod;
tmp.s1=tmp.s1+now.s1;if(tmp.s1>=mod)tmp.s1-=mod;
tmp.s1=tmp.s1+i*t[pos]*now.s0%mod;if(tmp.s1>=mod)tmp.s1-=mod;
}
}return (flag||first)?tmp:f[pos][cur]=tmp;
}
bool judge(LL k){
for(int i=2;i<=9;++i){
while(k%i==0)k/=i;
}return k>1;
}
int main(){
scanf("%d",&T);
t[1]=1;
for(int i=2;i<=20;++i)t[i]=t[i-1]*10%mod;
memset(f,-1,sizeof(f));
memset(dp,-1,sizeof(dp));
while(T--){
scanf("%lld%lld%lld",&L,&R,&k);
if(k==0){
check(L-1);A=DP(len,0,1,1);
check(R);B=DP(len,0,1,1);
}else{
if(judge(k)){printf("0
");continue;}
check(L-1);A=DFS(len,k,1,1);
check(R);B=DFS(len,k,1,1);
}printf("%lld
",(B.s1-A.s1+mod)%mod);
}return 0;
}
BZOJ 3131
跟上面的题思路是一样的，先预处理出所有合法的k
设s[i]表示第i个合法的k在[1,n]中有多少乘积为k的数，做数位DP
之后用优先队列实现多路归并即可，循环K次即可
注意放进队列里的时候不要取模
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long LL;
const int mod=1e9+7;
const int maxn=200010;
const int MOD=1333331;
LL n;
LL f[22][20010];
LL s[20010];
int Num[22],len,k;
struct pos{
int a,b;
LL num;
pos(int a=0,int b=0,LL num=0):a(a),b(b),num(num){}
bool operator <(const pos &A)const{
return num<A.num;
}
};
priority_queue<pos>Q;
bool cmp(const LL &A,const LL &B){return A>B;}
struct HASHMAP{
int cnt;
int h[MOD+10],next[maxn];
LL st[maxn];
void insert(LL S){
int key=S%MOD;
for(int i=h[key];i;i=next[i]){
if(st[i]==S)return;
}
++cnt;next[cnt]=h[key];h[key]=cnt;
st[cnt]=S;return;
}
int ask(LL S){
int key=S%MOD;
for(int i=h[key];i;i=next[i]){
if(st[i]==S)return i;
}return 0;
}
}H;
void check(LL n){
memset(Num,0,sizeof(Num));len=0;
if(!n){Num[++len]=0;return;}
while(n)Num[++len]=n%10,n/=10;
}
LL DFS(int pos,LL mul,int flag,int first){
if(!pos){
if(!first&&mul==1)return 1;
return 0;
}
int cur=H.ask(mul);
if(!flag&&!first&&f[pos][cur]!=-1)return f[pos][cur];
LL tmp=0;
if(first)tmp=tmp+DFS(pos-1,mul,0,1);
int u=flag?Num[pos]:9;
for(int i=1;i<=u;++i){
if(mul%i==0)tmp=tmp+DFS(pos-1,mul/i,flag&&i==u,0);
}return (flag||first)?tmp:f[pos][cur]=tmp;
}
LL mul(LL a,LL b){
LL s=0;
while(b){
if(b&1)s=(s+a)%mod;
a=(a<<1)%mod;b>>=1;
}return s;
}
int main(){
scanf("%lld%d",&n,&k);
check(n);memset(f,-1,sizeof(f));
for(int i=1;i<=9;++i)H.insert(i);
for(int i=2;i<=len;++i){
int now=H.cnt;
for(int k=1;k<=now;++k){
LL S=H.st[k];
for(int j=1;j<=9;++j)H.insert(S*j);
}
}
for(int i=1;i<=H.cnt;++i){
LL S=H.st[i];
if(S>n)continue;
s[i]=DFS(len,S,1,1);
}
sort(s+1,s+H.cnt+1,cmp);
for(int i=1;i<=H.cnt;++i){
Q.push(pos(i,1,s[i]*s[1]));
}
LL ans=0;
for(int i=1;i<=k;++i){
if(Q.empty())break;
pos tmp=Q.top();Q.pop();
ans=ans+tmp.num%mod;
if(ans>=mod)ans-=mod;
if(tmp.b+1<=H.cnt){
Q.push(pos(tmp.a,tmp.b+1,s[tmp.a]*s[tmp.b+1]));
}
}printf("%lld
",ans);
return 0;
}
留下两道题目当做最后复习：一道是BZOJ的大新闻，一道是CF的题
关于今天换的模板的一些总结：
1、首先对于flag=1的时候我们不需要记忆化，因为flag=1的状态只会转移到一个唯一的状态
2、使用这个模板要在DFS的过程中判掉几乎所有的限制，然后由于记录的只是flag=0的时候的状态，所以与L和R无关
每次DP不需要清空
3、有关于前导零的处理：我是有三种方法的：
第一种：当前导零对答案无影响时，补全前导零直接DP
第二种：先DP预处理，之后查询的时候先加上<len的，再去记忆化解决=len的
第三种: 增加传参first，表示当前是否是首位来判断对于状态是否有贡献，至于是否对first进行记忆化要根据题目来定
通常情况下不需要对first记忆化
4、有关于一些坑点：
数位DP一个最需要注意的问题是要注意整数溢出
其次要考虑一些边界情况，譬如当L=0的时候，如果要Solve(R)-Solve(L-1)就挂掉了
之后考虑题目的性质是否可减，通常情况下是可减的，我们转化成Solve(R)-Solve(L-1)
5、关于模板的一些细节：
注意在判断是否已经记忆化之前要判断flag
注意记忆化的时候要判断flag
注意每次循环的上界要判断flag
6、对于状态，数位DP的状态一般很好想
但是精简的状态可能会要动些脑子，一定要考虑我们到底需要记录什么
另外数位DP写的时候一定要细心，考虑所有边界，争取一遍写对
然后考试的时候数位DP一定要拍，错的话要耐心去想去改
未完待更(以后要做一些更好的数位DP,做一做论文题）
八月份！三个月！Fighting！