P11338 题解

huangrenheluogu · 2025-01-04 18:09:08 · 题解

发现性质：对于一种『选择开始认为的左/右方向，并在恰好 K 个节点改变方向认知的方案』，最后到达的节点是不同的。证明或者感性理解都是容易的。

因此，对于最终到达的节点计数可以转化为对路径计数。

数位 dp，f_{d,k,o} 表示剩余 d 层，剩余 k 次改变机会，走到点的权值数量/权值和是多少，转移是容易的。

#include<bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 1005, mod = 1e9 + 7;
int n, k, op[N], ll[N], rr[N], a[N];
int ans1, ans2, ans, qp[N];
char str[N];
pii f[N][N][2];
bool vis[N][N][2];
inline void add(int &x, int y){
    x += y;
    if(x >= mod) x -= mod;
}
inline int pls(int x, int y){
    x += y;
    if(x >= mod) x -= mod;
    return x;
}
inline pii operator + (pii x, pii y){
    add(x.fi, y.fi), add(x.se, y.se);
    return x;
}
inline pii work(int d, int k, int o, int lim){
    // determine 2 ^ (d - 1)
    if(k < 0 || k > d) return {0, 0};
    if(!d) return {0, !k};
    if(!lim && vis[d][k][o]) return f[d][k][o];
    pii res = {0, 0}, tmp;
    int x, up = lim ? a[d] : 1;
    x = o ^ op[d];
    if(!lim || x <= up){
        tmp = work(d - 1, k, o, lim && (x == up));
        res = res + tmp;
        if(x) add(res.fi, 1ll * qp[d - 1] * tmp.se % mod);
    }
    x ^= 1;
    if(!lim || x <= up){
        tmp = work(d - 1, k - 1, o ^ 1, lim && (x == up));
        res = res + tmp;
        if(x) add(res.fi, 1ll * qp[d - 1] * tmp.se % mod);
    }
    if(!lim){
        vis[d][k][o] = 1;
        f[d][k][o] = res;
    }
    return res;
}
inline int calc(int *arr, int o){
    if(o){
        arr[n - 1]--;
        for(int i = n - 1; i && arr[i] < 0; i--){
            arr[i] += 2, arr[i - 1]--;
        }
        if(arr[0] < 0) return 0;
    }
    for(int i = 1; i < n; i++){
        a[i] = arr[i];
    }
    reverse(a + 1, a + n);
    pii res = {0, 0};
    res = res + work(n - 1, k, 0, 1);
    res = res + work(n - 1, k, 1, 1);
    int sum = 0;
    sum = res.fi;
    add(sum, 1ll * res.se * qp[n - 1] % mod);
    return sum;
}
int main(){
    // freopen("maze.in", "r", stdin);
    // freopen("maze.out", "w", stdout);
    scanf("%d%d%s", &n, &k, str + 1);
    for(int i = 1; i < n; i++){
        op[n - i] = (str[i] == 'L' ? 0 : 1);
    }
    scanf("%s", str);
    for(int i = 1; i < n; i++){
        ll[i] = str[i] - '0';
    }
    scanf("%s", str);
    for(int i = 1; i < n; i++){
        rr[i] = str[i] - '0';
    }
    qp[0] = 1;
    for(int i = 1; i <= n; i++){
        qp[i] = pls(qp[i - 1], qp[i - 1]);
    }
    ans1 = calc(rr, 0);
    ans2 = calc(ll, 1);
    ans = pls(ans1, mod - ans2);   
    printf("%d\n", ans);
    return 0;
}