专栏文章

solution of P11338

ff__k_sheep
P11338题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@minvemi0
此快照首次捕获于
2025/12/02 08:59
3 个月前
此快照最后确认于
2025/12/02 08:59
3 个月前
查看原文

P11338 [COI 2019] LJEPOTICA

显然的数位 dp，把 [A,B]\left [ A,B \right ] 拆成 [1,B]\left [ 1,B \right ] - [1,A−1]\left [ 1,A-1 \right ]。
考虑每一步操作的意义。
发现向左走相当于在一个数的二进制位的最后面加入一个 00，向右走相当于在一个数的二进制位的最后面加入一个 11。
而加一个 00 相当于整个数 ×2\times 2，加一个 11 相当于整个数 ×2+1\times 2 +1 。
那么记 fi,j,0/1,0/1f_{i,j,0/1,0/1} 表示当前在考虑第 ii 步操作，已经改变了 jj 次决策，当前是否按照原路径走，是否顶到上界，gi,j,0/1,0/1g_{i,j,0/1,0/1} 表示符合上述条件的数的个数。
转移方程可以自己手推或者结合代码理解。
时间复杂度 O(n2)O(n^2)。

code

CPP
#include<bits/stdc++.h>
#define ll long long
#define R register
#define mk(x,y) make_pair(x,y)
#define PII pair<int,int>
using namespace std;
const int N=1005,mod=1e9+7;
int n,k;
string s1,s2,road;
ll f[N][N][2][2],g[N][N][2][2];
inline ll calc(string s){
	memset(f,0,sizeof f);memset(g,0,sizeof g);
	g[1][0][0][1]=g[1][0][1][1]=1;
	f[1][0][0][1]=f[1][0][1][1]=1;
	for(R int i=2;i<=n;++i){
		for(R int j=0;j<=k;++j){
			if(road[i-1]=='L'){
				f[i][j][0][0]=(f[i][j][0][0]+f[i-1][j][0][0]*2%mod);
				g[i][j][0][0]=(g[i][j][0][0]+g[i-1][j][0][0])%mod;
				if(s[i-1]=='1'){
					f[i][j][0][0]=(f[i][j][0][0]+f[i-1][j][0][1]*2%mod);
					g[i][j][0][0]=(g[i][j][0][0]+g[i-1][j][0][1])%mod;
				}
				if(s[i-1]=='0'){
					f[i][j][0][1]=(f[i][j][0][1]+f[i-1][j][0][1]*2%mod)%mod;
					g[i][j][0][1]=(g[i][j][0][1]+g[i-1][j][0][1])%mod;
				}
				f[i][j][1][0]=(f[i][j][1][0]+f[i-1][j][1][0]*2+g[i-1][j][1][0])%mod;
				g[i][j][1][0]=(g[i][j][1][0]+g[i-1][j][1][0])%mod;
				if(s[i-1]=='1'){
					f[i][j][1][1]=(f[i][j][1][1]+f[i-1][j][1][1]*2+g[i-1][j][1][1])%mod;
					g[i][j][1][1]=(g[i][j][1][1]+g[i-1][j][1][1])%mod;
				}
				if(j<k){
					f[i][j+1][0][0]=(f[i][j+1][0][0]+f[i-1][j][1][0]*2%mod)%mod;
					g[i][j+1][0][0]=(g[i][j+1][0][0]+g[i-1][j][1][0])%mod;
					if(s[i-1]=='1'){
						f[i][j+1][0][0]=(f[i][j+1][0][0]+f[i-1][j][1][1]*2%mod);
						g[i][j+1][0][0]=(g[i][j+1][0][0]+g[i-1][j][1][1])%mod;
					}
					if(s[i-1]=='0'){
						f[i][j+1][0][1]=(f[i][j+1][0][1]+f[i-1][j][1][1]*2%mod)%mod;
						g[i][j+1][0][1]=(g[i][j+1][0][1]+g[i-1][j][1][1])%mod;
					}
					f[i][j+1][1][0]=(f[i][j+1][1][0]+f[i-1][j][0][0]*2+g[i-1][j][0][0])%mod;
					g[i][j+1][1][0]=(g[i][j+1][1][0]+g[i-1][j][0][0])%mod;
					if(s[i-1]=='1'){
						f[i][j+1][1][1]=(f[i][j+1][1][1]+f[i-1][j][0][1]*2+g[i-1][j][0][1])%mod;
						g[i][j+1][1][1]=(g[i][j+1][1][1]+g[i-1][j][0][1])%mod;
					}
				}
			}else{
				f[i][j][0][0]=(f[i][j][0][0]+f[i-1][j][0][0]*2%mod+g[i-1][j][0][0])%mod;
				g[i][j][0][0]=(g[i][j][0][0]+g[i-1][j][0][0])%mod;
				if(s[i-1]=='1'){
					f[i][j][0][1]=(f[i][j][0][1]+f[i-1][j][0][1]*2%mod+g[i-1][j][0][1])%mod;
					g[i][j][0][1]=(g[i][j][0][1]+g[i-1][j][0][1])%mod;
				}
				f[i][j][1][0]=(f[i][j][1][0]+f[i-1][j][1][0]*2)%mod;
				g[i][j][1][0]=(g[i][j][1][0]+g[i-1][j][1][0])%mod;
				if(s[i-1]=='1'){
					f[i][j][1][0]=(f[i][j][1][0]+f[i-1][j][1][1]*2)%mod;
					g[i][j][1][0]=(g[i][j][1][0]+g[i-1][j][1][1])%mod;
				}
				if(s[i-1]=='0'){
					f[i][j][1][1]=(f[i][j][1][1]+f[i-1][j][1][1]*2)%mod;
					g[i][j][1][1]=(g[i][j][1][1]+g[i-1][j][1][1])%mod;
				}
				if(j<k){
					f[i][j+1][0][0]=(f[i][j+1][0][0]+f[i-1][j][1][0]*2%mod+g[i-1][j][1][0])%mod;
					g[i][j+1][0][0]=(g[i][j+1][0][0]+g[i-1][j][1][0])%mod;
					if(s[i-1]=='1'){
						f[i][j+1][0][1]=(f[i][j+1][0][1]+f[i-1][j][1][1]*2%mod+g[i-1][j][1][1])%mod;
						g[i][j+1][0][1]=(g[i][j+1][0][1]+g[i-1][j][1][1])%mod;
					}
					f[i][j+1][1][0]=(f[i][j+1][1][0]+f[i-1][j][0][0]*2)%mod;
					g[i][j+1][1][0]=(g[i][j+1][1][0]+g[i-1][j][0][0])%mod;
					if(s[i-1]=='1'){
						f[i][j+1][1][0]=(f[i][1+j][1][0]+f[i-1][j][0][1]*2)%mod;
						g[i][j+1][1][0]=(g[i][1+j][1][0]+g[i-1][j][0][1])%mod;
					}
					if(s[i-1]=='0'){
						f[i][j+1][1][1]=(f[i][j+1][1][1]+f[i-1][j][0][1]*2)%mod;
						g[i][j+1][1][1]=(g[i][j+1][1][1]+g[i-1][j][0][1])%mod;
					}
				}
			}
		}
	}
	ll sum=(f[n][k][0][0]+f[n][k][0][1]+f[n][k][1][0]+f[n][k][1][1])%mod;
	return sum;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	cin>>n>>k>>road>>s1>>s2;road=" "+road;
	ll tmp=0;
	for(R int i=0;i<n;++i){
		tmp=tmp*2+s1[i]-'0';
		tmp%=mod;
	}
	cout<<(calc(s2)-calc(s1)+tmp+mod)%mod;
	return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...