这题题意非常之裸。定义一种变换是模糊两个字符，求s的每个与t长度相等的子串变成与t相等的的最小变换次数。

一眼就看出这是FFT，但是不会构造。

于是就看了一眼数据范围，125000，bitset可以水。（虽然好想好写，但是罚时爆炸，不过小号rating无关紧要）

思路就是和bitset字符串匹配的思路差不多。

复杂度O（m*(n-m)/计算机位数）

简写O(能过)

codeforces评测机是64位无疑。

然后大力卡常即可。

代码：

#pragma GCC target("avx")#pragma GCC optimize(3)#pragma GCC optimize("Ofast")#pragma GCC optimize("inline")#pragma GCC optimize("-fgcse")#pragma GCC optimize("-fgcse-lm")#pragma GCC optimize("-fipa-sra")#pragma GCC optimize("-ftree-pre")#pragma GCC optimize("-ftree-vrp")#pragma GCC optimize("-fpeephole2")#pragma GCC optimize("-ffast-math")#pragma GCC optimize("-fsched-spec")#pragma GCC optimize("unroll-loops")#pragma GCC optimize("-falign-jumps")#pragma GCC optimize("-falign-loops")#pragma GCC optimize("-falign-labels")#pragma GCC optimize("-fdevirtualize")#pragma GCC optimize("-fcaller-saves")#pragma GCC optimize("-fcrossjumping")#pragma GCC optimize("-fthread-jumps")#pragma GCC optimize("-funroll-loops")#pragma GCC optimize("-fwhole-program")#pragma GCC optimize("-freorder-blocks")#pragma GCC optimize("-fschedule-insns")#pragma GCC optimize("inline-functions")#pragma GCC optimize("-ftree-tail-merge")#pragma GCC optimize("-fschedule-insns2")#pragma GCC optimize("-fstrict-aliasing")#pragma GCC optimize("-fstrict-overflow")#pragma GCC optimize("-falign-functions")#pragma GCC optimize("-fcse-skip-blocks")#pragma GCC optimize("-fcse-follow-jumps")#pragma GCC optimize("-fsched-interblock")#pragma GCC optimize("-fpartial-inlining")#pragma GCC optimize("no-stack-protector")#pragma GCC optimize("-freorder-functions")#pragma GCC optimize("-findirect-inlining")#pragma GCC optimize("-fhoist-adjacent-loads")#pragma GCC optimize("-frerun-cse-after-loop")#pragma GCC optimize("inline-small-functions")#pragma GCC optimize("-finline-small-functions")#pragma GCC optimize("-ftree-switch-conversion")#pragma GCC optimize("-foptimize-sibling-calls")#pragma GCC optimize("-fexpensive-optimizations")#pragma GCC optimize("-funsafe-loop-optimizations")#pragma GCC optimize("inline-functions-called-once")#pragma GCC optimize("-fdelete-null-pointer-checks")#include
      
       using namespace std;const int N1=20010,N2=40010,N3=80010,N4=125010,N5=60010;bitset
       
         ss[6],tt[6];bitset
        
          sss[6],ttt[6];bitset
         
           ssss[6],tttt[6];bitset
          
            sssss[6],ttttt[6];bitset
           
             ssssss[6],tttttt[6];char s[N4],t[N4];bool re[6][6],b[6];int dfs(int x){ if (b[x]) return 0; b[x]=1; int ret=1; for (int i=0; i<6; ++i) if (re[x][i]||re[i][x]) ret+=dfs(i); return ret;}int main(){ scanf("%s%s",s,t);// freopen("re.out","w",stdout); int n=strlen(s),m=strlen(t);// n=120000,m=60000;// for (int i=0; i
            
             >=1; if (u
             
              >=1; if (u
              
               >=1; if (u
               
                >=1; if (u
                
                 >=1; if (u
                
               
              
             
            
           
          
         
        
       
      

bitset不支持可变长度，于是就分类讨论，反正bitset空间很小。实测比写的xiang的FFT快。

话说不是很懂Execution time Rank 1 的大佬的写法是什么？