写在前面的话：心可以冷，但手不能停
第一题：C. Flexible String
题目大意：给一个aaa字符串和bbb字符串和数字kkk，首先设置一个计数器cntcntcnt,其中可以对aaa字符串做以下操作：替换aaa中的一个字母xxx，将字母xxx加入到集合QQQ，如果这个字母已经在集合QQQ中了，则cntcntcnt不动，否则cnt++cnt++cnt++，记s[l,r]s[l,r]s[l,r]为在[l,r][l,r][l,r]区间中aaa和bbb的字母全相等。达到的目标为在cnt≤kcnt \leq kcnt≤k的情况下，让s[l,r]s[l,r]s[l,r]的数量最大。
解题思路： 这个题可以这样想，对于任意一个a[i]≠b[i]a[i] \neq b[i]a[i]=b[i]，可以将这个位置记作一个断点，被断点隔开的若干个区间可以用这样的形式来表达s[l,r]s[l,r]s[l,r]的数量:len∗(len+1)/2len*(len+1)/2len∗(len+1)/2,其中len为区间内的字母数量。我们注意到如果将某个满足a[i]≠b[i]a[i] \neq b[i]a[i]=b[i]的字母加入到集合QQQ中，则区间可能被连上，注意可能断点是由两个字母组成的。这样的话，考虑k最大可能为101010，则可以用数位dpdpdp或者dfsdfsdfs等，来枚举所有可能性。枚举出一种可能性，之后只要用O(n)O(n)O(n)判断即可，大概是10810^8108这样的级别，那么这里的枚举状态可以用这种形式表达：

for(int i=0;i<1024;i++)

注意，由于我把集合中的字母用mapmapmap映射，所以所有字母不能映射到000，否则wronganswerontest3wrong\space answer \space on\space test3wrong answer on test3
代码：

#include
#include
#include
#include
#include

第2题：D. Flexible String Revisit
这个题比较有意思
题目大意： 给一个由0和1组成的两个字符串，对字符串a可以做以下操作：可以任选一个数字对其进行反转，问达到两个字符串第一次相等所需要的操作次数期望。
解题思路：
参考文章
代码：

#include
#include
#include
using namespace std;
typedef long long ll;
int mod = 998244353;
const int length = 1e6 + 5;
int f[length][2];
int dp[length];
char a[length];
char b[length];
int ksm(int k)
{int tmp = mod-2;int base = k;int ans = 1;while (tmp){if (tmp % 2 == 1){ans = (ll)ans*base%mod;}base = (ll)base*base%mod;tmp = tmp >> 1;}return ans;
}
int solve(int n, int k)
{f[n][0] = 1;f[n][1] = 1;for (int i = n-1; i >= 0; i--){int now = ((ll)1 - (ll)(n - i)*f[i + 1][1]%mod *ksm(n) % mod + mod) % mod;f[i][0] = ((ll)1 + (ll)(f[i+1][0])*(n-i)%mod*ksm(n) % mod) % mod*ksm(now)%mod;f[i][1] = (ll)i*ksm(n) % mod*ksm(now) % mod;}dp[0] = f[0][0];for (int i = 1; i <= k; i++){dp[i] = (ll)((ll)dp[i - 1] * f[i][1] % mod + f[i][0]) % mod;}return dp[k];
}
int main(void)
{int t;scanf_s("%d", &t);for (int i = 0; i < t; i++){int n;scanf_s("%d", &n);int k = 0;getchar();scanf_s("%s", a,sizeof(a));//a.push_back(t);getchar();scanf_s("%s", b, sizeof(b));getchar();for (int i = 0; i < n; i++){if (a[i] != b[i])k++;}int a1=solve(n, k);printf("%d\n", a1);}
}