中文题意

你要选择个长度是的字符串，这些字符串要满足字典序大于小于，在输入的第二行和第三行给出，求本质不同的前缀一共有几个。

Solution

如果我们把看作的话，我们就可以构建一颗满二叉树。那么其实我们对应的在满二叉树中有自己的对应编号。

其实就是问你给你两个这样的端点前面你可以选择的节点数一共有多少个。

那么当我们当前可选的区间长度一直都不足的时候，我们就可以把这一层全部的可选节点数都加上。

当我们当前可选区间的长度第一次大于等于之后，因为你上方全部的节点都已经被你计算过了，所以你最多只能在当前层选择个节点，那么这种时候你就不能把这一层可选的节点都拿上去了，只能选择其中的个，那么与之对应，其实你下一层如果还要选，那么节点数也一定大于等于，你从其中挑出个叶子之后，你会发现叶子节点上方的父亲在你上一次就要被选过，不然你这次就不可能拿到这个叶子，所以这对应着你这次任然只能选其中的个节点。

最后总结一下就是，使用二进制判断当前层数可选的节点数，如果小于，直接累加。

如果大于等于，那么现在这一层以及下面的你还没选的层数，每层你都只能选择个节点。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }

const int N = 5e5 + 7;
ll n, k;
char s[N], t[N];

int main() {
    n = read(), k = read();
    scanf("%s", s + 1);
    scanf("%s", t + 1);
    ll ans = 0, len, a = 0, b = 0;
    rep(i, 1, n) {
        a <<= 1, b <<= 1;
        if (s[i] == 'b')    ++a;
        if (t[i] == 'b')    ++b;
        len = b - a + 1;
        if (len >= k) {
            ans += (n - i + 1) * k;
            break;
        }
        ans += len;
    }
    print(ans);
    return 0;
}