题意
给出两个长度为n的01字符串S和T。
选出k个字典序在S和T之间的长度为n的01字符串，使得尽可能多的字符串满足其是所选字符串中至少一个串的前缀。
这是一道思路比较奇怪的类似计数dp的题。
首先考虑如果把选出的这些串插入到一个trie树中的话，算产生的贡献可以理解为，从根节点向下画了k条长度为n的线，最大化它们所经过的点的总个数。
进一步发现，每一层节点如果不受s和t的限制的话，一定可以满足每一层都有k个点被经过。
因此，剩下要做的就是算一下这个s和t的限制，即每一层有多少个节点。
记dp[i][0/1][0/1]表示第i层，满足前i位是否与s相同，前i位是否与t相同，按照定义转移即可，复杂度O(n)。
最后统计答案的时候把每一层的节点个数和k取min后加入答案即可。
#include<iostream>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#define N 1100000
#define L 1000000
#define eps 1e-7
#define ll long long
using namespace std;
inline ll read()
{char ch=0;ll x=0,flag=1;while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;}while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return x*flag;
}
const ll inf=1e14+7;
char s[N],t[N];
ll dp[N][2][2];
int main()
{ll n=read(),m=read();scanf("%s",s+1);scanf("%s",t+1);dp[0][1][1]=1;for(ll i=0;i<n;i++){if(s[i+1]==t[i+1])dp[i+1][1][1]=dp[i][1][1];else dp[i+1][1][0]=dp[i+1][0][1]=dp[i][1][1];dp[i+1][1][0]+=dp[i][1][0];dp[i+1][0][1]+=dp[i][0][1]; dp[i+1][0][0]=min(2*dp[i][0][0],inf);if(s[i+1]=='a')dp[i+1][0][0]=min(dp[i+1][0][0]+dp[i][1][0],inf);if(t[i+1]=='b')dp[i+1][0][0]=min(dp[i+1][0][0]+dp[i][0][1],inf);}ll ans=0;for(ll i=1;i<=n;i++){ll tot=0;for(ll j=0;j<=1;j++)for(ll k=0;k<=1;k++)tot=min(tot+dp[i][j][k],m);ans+=tot;}printf("%lld",ans);return 0;
}