bzoj 3530: [Sdoi2014]数数 数位dp
题目
我们称一个正整数N是幸运数，当且仅当它的十进制表示中不包含数字串集合S中任意一个元素作为其子串。例如当S=(22，333，0233)时，233是幸运数，2333、20233、3223不是幸运数。
给定N和S，计算不大于N的幸运数个数。
题解
有一道scoi2013的数数比这道题丧病多了...
这道题还是比较好做的。
给定范围的时给定了n的长度，并且要求计算数的个数。
所以可以基本确定这是一道数位dp了。
然后又要求有一部分串不能出现
这是经典的在AC自动机上的dp了.
所以我们需要在拿到的数不超过n的情况下在AC自动机上dp.
可以这么设定状态:
\(f[i][j]\)表示从高位向低位逐个确定了\(n\)位，走到了自动机的节点\(j\)
但是要求我们找出来的串的大小不得超过\(n\),所以我们现在的状态无法支持转移.
原因就在于我们没有办法确定下一位取值的范围,可能是\([0,a_i]\)，也可能是\([0,9]\)
所以需要多加一维的状态表示我们前面的数字是不是顶到顶了.
所谓顶到顶的意思就是下一位只能取\([0,a_i]\)范围内的数.
所以我们两维状态交替更新即可.细节看代码.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;static char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
#define rg register int
#define rep(i,a,b) for(rg i=(a);i<=(b);++i)
#define per(i,a,b) for(rg i=(a);i>=(b);--i)
const int maxn = 2048;
const int mod = 1e9+7;
int ch[maxn][10],nodecnt,fail[maxn],q[maxn],l,r;
bool danger[maxn];
inline void insert(char *s){
int nw = 0;
for(rg i=0,c;s[i];++i){
c = s[i] - '0';
if(ch[nw][c] == 0) ch[nw][c] = ++ nodecnt;
nw = ch[nw][c];
}danger[nw] = true;
}
void build(){
l = 0;r = -1;
rep(c,0,9){
if(ch[0][c] != 0){
fail[ch[0][c]] = 0;
q[++r] = ch[0][c];
}
}
while(l <= r){
int u = q[l++];
rep(c,0,9){
int t = ch[fail[u]][c];
if(ch[u][c] == 0) ch[u][c] = t;
else{
danger[ch[u][c]] |= danger[t];
fail[ch[u][c]] = t;
q[++r] = ch[u][c];
}
}
}
}
char num[maxn],s[maxn];
int f[maxn][maxn][2],a[maxn];
int main(){
scanf("%s",num+1);
int n = strlen(num+1);
rep(i,1,n) a[i] = num[i] - '0';
int m;read(m);
while(m--){
scanf("%s",s);
insert(s);
}build();
rep(i,1,a[1]) if(!danger[ch[0][i]]){
f[1][ch[0][i]][i == a[1]] += 1;
}
rep(i,1,n-1) rep(j,0,nodecnt){
if(f[i][j][1]){
rep(k,0,a[i+1]){
if(danger[ch[j][k]]) continue;
f[i+1][ch[j][k]][k == a[i+1]] += f[i][j][1];
if(f[i+1][ch[j][k]][k == a[i+1]]>=mod)f[i+1][ch[j][k]][k == a[i]] -= mod;
}
}
if(f[i][j][0]){
rep(k,0,9){
if(danger[ch[j][k]]) continue;
f[i+1][ch[j][k]][0] += f[i][j][0];
if(f[i+1][ch[j][k]][0] >= mod) f[i+1][ch[j][k]][0] -= mod;
}
}
}
ll ans = 0;
rep(i,0,nodecnt){
ans += f[n][i][0] + f[n][i][1];
if(ans >= mod) ans -= mod;
}
memset(f,0,sizeof f);
rep(i,1,9) if(!danger[ch[0][i]]) f[1][ch[0][i]][0] += 1;
rep(i,1,n-2) rep(j,0,nodecnt){
if(f[i][j][0]){
rep(k,0,9){
if(danger[ch[j][k]]) continue;
f[i+1][ch[j][k]][0] += f[i][j][0];
if(f[i+1][ch[j][k]][0] >= mod) f[i+1][ch[j][k]][0] -= mod;
}
}
}
rep(i,1,n-1){
rep(j,0,nodecnt){
ans += f[i][j][0];
if(ans >= mod) ans -= mod;
}
}
printf("%lld\n",ans);
return 0;
}
1、http.StripPrefix 的参数含义
2、浅析Linux Kernel中的那些链表
3、 下一版本Windows® CE 开发工具Smart Device Extensions for Microsoft Visual Studio® .NET
4、开博客啦，
5、ASP.NET页面间数据传递(转)