[SDOI2014] 数数

• 题意:问有多少个<=n(\(10^{1201}\))的数满足下面所给的模式串没有在其中出现过
• 思路:首先一堆串没在构造的串中，套路就是AC自动机上dp,不经过cnt[]>0的点。
  不过<=n怎么做呢？从n范围容易想到数位dp。
  不过有一种更巧妙的方法：
  首先位数 （类似康托展开：每次讨论每一位取值，值 ps.处理前导零
  因此状态需要：\(dp[i][j]\):从\(j\)点走\(i\)步可以构成串的方案数。也很好转移。
• code:

#include
using namespace std;
const int N=1e5+5;
const int mod=1e9+7;
typedef long long ll;
char s[N],a[N];
int n;
struct AC {
	int go[N][11],nd,cnt[N],fail[N];
	ll dp[1999][2005];
	void Insert() {
		int sz=strlen(s),u=0;
		for(int i=0;i