CF585F Digits of Number Pi

还没写，不一定对。/cy

一个 \(naive\) 的想法，暴力枚举 s 的子串，然后找 \([x,y]\) 有多少个子串。但找的话似乎很难实现，直接对 s 建 SAM，之后数位 dp 时记录下现在匹配到哪个节点即可。

我们发现，枚举是不必要的，我们只需要在数位 dp 时记录能匹配到长度多少，对于匹配到长度为 \(\lfloor \dfrac{d}{2}\rfloor\) ，那么后面无论怎样都是可以贡献的，打标记跑下去。边界时看看有没有标记即可。

相信 SAM 上匹配子串已经成了人均，所以不写了。

\(\text{Code}\)

没想到我 WA on #10竟然因为 dp 过程忘记取模了。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define ll long long

using namespace std;
int rd() {
	int f=1,sum=0; char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return sum*f;
}
ll lrd() {
	ll f=1,sum=0; char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return sum*f;
}

const int N=(int)(4e3+5),mod=(int)(1e9+7);
int n,son[10][N],len[N],fa[N],tot=1,las=1;
int cnt,num[60],d;
char s[N],s2[N];

int ins(int c) {
	if(son[c][las]) {
		int pre=las,y=son[c][pre];
		if(len[y]==len[pre]+1) return y;
		int x=++tot; len[x]=len[pre]+1;
		fa[x]=fa[y]; fa[y]=x;
		for(int i=0;i<10;i++) son[i][x]=son[i][y];
		for(;pre&&son[c][pre]==y;pre=fa[pre]) son[c][pre]=x;
		return x;
	}
	int x=++tot,pre=las; len[x]=len[pre]+1;
	for(;pre&&!son[c][pre];pre=fa[pre]) son[c][pre]=x;
	int y=son[c][pre];
	if(!pre) fa[x]=1;
	else if(len[pre]==len[y]+1) fa[x]=y;
	else {
		int p=++tot; len[p]=len[pre]+1;
		fa[p]=fa[y]; fa[x]=fa[y]=p;
		for(int i=0;i<10;i++) son[i][p]=son[i][y];
		for(;pre&&son[c][pre]==y;pre=fa[pre]) son[c][pre]=p;
	}
	return x;
}

void solve(int &pos,int c,int &le) {
	while(pos!=1&&!son[c][pos]) pos=fa[pos],le=len[pos];
	if(son[c][pos]) pos=son[c][pos],++le;
	else le=0;
}

ll f[2][60][60][N];
ll dfs(int lim,int zero,int fl,int x,int le,int pos) {
	if(!x) return fl;
	if(!lim&&!zero&&~f[fl][x][le][pos]) return f[fl][x][le][pos];
	int nex=lim?num[x]:9; ll res=0;
	for(int i=0;i<=nex;i++) {
		if(fl) {
			res+=dfs(lim&(i==nex),zero&(!i),fl,x-1,le,pos),res%=mod; continue;
		}
		int ppos=pos,lee=le; solve(ppos,i,lee);
		//cout<=(d/2)),x-1,lee,ppos),res%=mod;
	}
	if(!lim&&!zero) f[fl][x][le][pos]=res;
	return res;
}

ll solve() {
	cnt=strlen(s2+1); for(int i=1;i<=cnt;i++) num[i]=s2[cnt-i+1]-'0';
	return dfs(1,1,0,cnt,0,1);
}

int main() {
	scanf("%s",s+1); n=strlen(s+1);
	for(int i=1;i<=n;i++) las=ins(s[i]-'0');
	ll ans=0;
	memset(f,-1,sizeof(f));
	scanf("%s",s2+1); d=cnt=strlen(s2+1); s2[cnt--]--;
	while(s2[cnt]-'0'==-1) s2[cnt]--,s2[cnt--]=9+'0';
	ans-=solve();
	scanf("%s",s2+1); ans+=solve();
	ans=(ans%mod+mod)%mod; printf("%lld",ans);
	return 0;
}
SAM数位DP

相关

CentOS开启SELinux导致samba无法访问的解决办法

jmeter_04控制器_controllers_sample_listerer_timer定时器

最新版Chrome跟进的Cookie SameSite策略，你真的了解吗？

ffmpeg之samplefmt

数位dp学习记录

shell find same word in two files

Samba配置

MySQL两个最常用的存储引擎，MyISAM和InnoDB

SAMStat 的安装

[LeetCode] 100. Same Tree

LINUX开启SAMBA服务

[ICPC2020济南L] Bit Sequence - 数位dp

标签