\(f_{i,u,v},i\)位，AC自动机上\(u\)位置，\(v\)次匹配的最大值

大菜鸡又去翻题解

两边取对数！！！

\[ams=\sqrt[c]{\prod_{i=1}^cw_i} \]

\[lnans=\frac1c\sum_{i=1}^clnw_i \]

分数规划，二分DP即可

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f==1?x:-x;
}
const int N=1504;
const double eps=1e-8,inf=1e9;
vector<int>e[N];
int n,m,tot=1,sz[N],fail[N],ch[N][12],fi[N][N],fu[N][N];
double f[N][N],w[N];
void dfs(int x){
	for(auto v:e[x]){
		sz[v]+=sz[x];
		w[v]+=w[x];
		dfs(v);
	}
}
#define re register
inline void buildAC(){
	for(re int i=0;i<=9;++i)ch[0][i]=1;
	queue<int>q;
	q.push(1);
	while(!q.empty()){
		int x=q.front();q.pop();
		e[fail[x]].push_back(x); 
		for(re int i=0,u;i<=9;++i){
			u=ch[x][i];
			if(!u){
				ch[x][i]=ch[fail[x]][i];
				continue;
			} 
			fail[u]=ch[fail[x]][i];
			q.push(u);
		}
	}
	dfs(1);
} 
inline int cmp(double x,double y){
	if(fabs(x-y)<eps)return 0;
	return (x<y)?-1:1;
}
inline void update(int p,int x,int f1,int f2,double mid){
	double v=f[p-1][f1]+w[x]-mid*sz[x];
	if(v>f[p][x]){
		f[p][x]=v;
		fi[p][x]=f1;
		fu[p][x]=f2;
	}
} 
char s[N],c[N];
inline bool check(double mid){
	for(re int i=0;i<=n;++i)
		for(re int j=1;j<=tot;++j)f[i][j]=-inf;
	f[0][1]=0;
	for(re int i=0;i<n;++i)
		for(re int j=1;j<=tot;++j){
			if(!cmp(f[i][j],-inf))continue;
			if(s[i+1]=='.')for(int u=0;u<=9;u++)
				update(i+1,ch[j][u],j,u,mid);
			else update(i+1,ch[j][s[i+1]^48],j,s[i+1]^48,mid);
		}
	for(re int j=1;j<=tot;++j)
		if(cmp(f[n][j],0)==1)return 1;
	return 0;
}
void out(int p,int u){
	if(!p)return;
	out(p-1,fi[p][u]);
	putchar(fu[p][u]|48);
}
int main(){
	cerr<<log(inf);
	n=read();m=read();
	scanf("%s",s+1);
	for(re int i=1,p,u;i<=m;++i){
		scanf("%s",c+1);
		p=1;
		for(re int j=1,len=strlen(c+1);j<=len;++j){
			u=(c[j]^48);
			if(!ch[p][u])ch[p][u]=++tot;
			p=ch[p][u];
		}
		w[p]+=log(read());
		sz[p]++;
	}
	buildAC();
	double l=0,r=24,mid,ans=0;
	for(re int T=1;T<=40;++T){
		mid=(l+r)/2;
		if(check(mid))ans=l=mid;
		else r=mid;
	}
	check(ans);
	int id=1;
	for(re int i=2;i<=tot;++i)
		if(f[n][i]>f[n][id])id=i;
	out(n,id);
	return (0-0);
}