CF433E Tachibana Kanade's Tofu

题意略。

考虑数位 dp，设 $f_{i,j,k,0/1,0/1}$ 表示转移到第 $i$ 位，位于 AC 自动机上 $j$ 号节点，获得价值 $k$，是否紧贴上边界，当且是否已经离开前导 $0$ 的范围（可以产生新贡献）。 转移是平凡的，需要进行简单的容斥。

code:

#include<bits/stdc++.h>
#define N 5005
#define pii pair<int,int>
#define psi pair<string,int>
#define pb push_back
#define fi first
#define se second
#define M 1000000007
using namespace std;
int n,m,k;
struct ACAM{
	int rt=1,cn=1,tr[N][25],fail[N],ans[N]; vector<int>g[N];
	void addE(int x,int y){g[x].pb(y),g[y].pb(x);}
	void ins(int *s,int ln,int val){
		int u=rt;
		for(int i=0;i<ln;i++){
			int &v=tr[u][s[i]];
			if(!v) v=(++cn); u=v;
		}ans[u]=min(ans[u]+val,k+1);
	}void build(){
		queue<int>q; q.push(1);
		memset(fail,0,sizeof(fail));
		for(int i=0;i<m;i++) tr[0][i]=1;
		while(!q.empty()){
			int u=q.front(); q.pop();
			for(int i=0;i<m;i++)
				if(tr[u][i]) fail[tr[u][i]]=tr[fail[u]][i],q.push(tr[u][i]);
				else tr[u][i]=tr[fail[u]][i];
			if(u>1) g[fail[u]].pb(u);
		}return;
	}void dfs(int x){for(int &u:g[x]) ans[u]=min(ans[u]+ans[x],k+1),dfs(u);}
}T; int L[N],R[N],la,lb,f[205][205][505][2][2],a[N];
void inc(int &x,int y){x+=y; if(x>=M) x-=M;}
int dfs(int bt,int po,int va,int pl,int o){
	if(va>k) return 0; if(bt<0) return 1;
	int &sum=f[bt][po][va][pl][o];
	if(sum>=0) return sum; sum=0; int ri=(pl?m-1:a[bt]);
	for(int i=0;i<=ri;i++){
		int nx=T.tr[po][i],ol=(o|(i>0)),v0=va+(ol?T.ans[nx]:0);
		inc(sum,dfs(bt-1,ol?nx:po,min(v0,k+1),pl|(i<ri),ol));
	}return sum;
}signed main(){
	scanf("%d%d%d",&n,&m,&k),memset(f,-1,sizeof(f));
	scanf("%d",&la); for(int i=0;i<la;i++) scanf("%d",&L[i]);
	scanf("%d",&lb); for(int i=0;i<lb;i++) scanf("%d",&R[i]);
	reverse(L,L+la),reverse(R,R+lb);
	for(int i=1;i<=n;i++){
		int ln,val; scanf("%d",&ln);
		for(int j=0;j<ln;j++) scanf("%d",&a[j]);
		scanf("%d",&val); T.ins(a,ln,val);	
	}T.build(),T.dfs(T.rt); 
	for(int i=0;i<=lb;i++) a[i]=R[i];
	int ans=dfs(lb-1,T.rt,0,0,0);
	memset(f,-1,sizeof(f)); int u=T.rt,sum=0;
	for(int i=0;i<=la;i++) a[i]=L[i];
	ans=(ans+M-dfs(la-1,T.rt,0,0,0))%M;
	for(int i=la-1;~i;i--) sum=min(sum+T.ans[u=T.tr[u][L[i]]],k+1);
	return !printf("%d\n",ans+(sum<=k));
}