官方题解

题目大意

对于一个字符串序列，可以修改任意一个位置的字符串，问最终有多少种可能，使得所有长度至少为 $2$ 的字符串序列中的所有字符集合与原来的相同。

解题思路

首先由于每一个字符串中的字符不会重复且长度最大不会超过 $26$ ，那么我们不妨将每个小写字母用二进制表示，这样每个字符串都可以用一个整数来表示。那么对于第三点要求，就转化成：对于所有 $1\leq l<r\leq n$，均有 $a_l | a_{l+1}|...|a_r = b_l|b_{l+1}|...|b_r$ 。

接下来考虑如何满足题目要求的第两、三个条件。不难发现，当我们要修改位置 $i$ 的元素是，对于一个包含 $i$ 区间 $[l,r]$ ，满足 $a_l | a_{l+1}|...|a_r = b_l|b_{l+1}|...|b_r$ ，那么一定需要满足长度至少为 $2$ 的区间按位或值不变。因此，我们只需要让 $a_i$ 与其相邻的数按位或后的值不变即可。

假设当前的数为 $a_i$ ，变化后的数为 $b_i$ 且 $b_i \ne a_i$ ，与其相邻的数为 $x$ ，那么对于每一位老说有以下几种情况：

• $a_i | x$ 的这一位为 $0$ ，那么 $b_i$ 的这一位一定为 $0$ ；
• $a_i | x$ 的这一位为 $1$ ，并且 $x$ 的这一位为 $0$ ，那么 $b_i$ 的这一位一定为 $0$ ；
• $a_i | x$ 的这一位为 $1$ ，并且 $x$ 的这一位为 $1$ ，那么 $b_i$ 的这一位可以为 $0$ ，也可以为 $1$ .

综上，不难发现，只有第三种情况 $b_i$ 会有两种情况，我们统计有 $cnt$ 位会出现这种情况，那么位置 $i$ 的方案数就有 $2^{cnt}$ 个，由于需要满足 $a_i\ne b_i$ 这个条件，还要把方案数 $-1$ 。

最后将所有位置的方案数相加，即为答案。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 200010;

void solve(){
    int n,m;cin>>n>>m;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++){
        string s;cin>>s;
        for(auto x:s){
            a[i]+=(1ll<<(x-'a'));
        }
    }
    
    ll res=0;
    for(int i=1;i<=n;i++){
        int x=(1<<m)-1;
        if(i>1) x&=a[i-1];
        if(i<n) x&=a[i+1];

        int cnt=0;
        for(int j=0;j<m;j++){
            if(x>>j&1) cnt++;
        }
        res+=(1ll<<cnt)-1;
    }
    cout<<res<<endl;
}

int main(){
    int T=1;cin>>T;
    while(T--){
        solve();
    }
    return 0;
}