solution of P11338

· · 题解

P11338 [COI 2019] LJEPOTICA

显然的数位 dp，把 \left [ A,B \right ] 拆成 \left [ 1,B \right ] - \left [ 1,A-1 \right ]。

考虑每一步操作的意义。

发现向左走相当于在一个数的二进制位的最后面加入一个 0，向右走相当于在一个数的二进制位的最后面加入一个 1。

而加一个 0 相当于整个数 \times 2，加一个 1 相当于整个数 \times 2 +1 。

那么记 f_{i,j,0/1,0/1} 表示当前在考虑第 i 步操作，已经改变了 j 次决策，当前是否按照原路径走，是否顶到上界，g_{i,j,0/1,0/1} 表示符合上述条件的数的个数。

转移方程可以自己手推或者结合代码理解。

时间复杂度 O(n^2)。

code

#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;
}