陈老师的题QwQ

题目大意

有两个字符串\(S\)和\(T\)（都只能由'A','C','G','T'这四个字符组成），\(S\)已知\(T\)未知，还知道\(S\)的长度为\(m\)。求满足\(Len(LCS(S,T))=L,1\leqslant L\leqslant |T|\)的\(S\)的个数

先想想若\(S\)已知怎么做。一个简单的\(DP\)就能解决，设\(dp[i][j]\)表示\(S\)到\(i\)位置，\(T\)到\(j\)位置时\(LCS\)的长度：

1.若\(S[i]==T[j]\)，则\(dp[i][j]=max(dp[i-1][j-1]+1,max(dp[i-1][j],dp[i][j-1]))\)

2.否则\(dp[i][j]=max(dp[i-1][j],dp[i][j-1])\)

然后考虑倒过来怎么做，看一下数据范围，可能状压？设\(f[i][state]\)表示\(T\)填到第\(i\)位，\(dp[?][i]\)在\(Len(S)+1\)进制下的表示时的方案数，再令\(g[state][c]\)表示状态是\(state\)时再加一个字符\(c\)后的\(state\)是多少。\(g\)数组可以预处理一下，然后\(f\)就好转移了：

\(f[i][g[state][c]]=f[i][g[state][c]]+f[i-1][state]\)

这样的话空间显然会炸，一个显然的性质，\(dp[i][j]\)只有可能是\(dp[i-1][j]\)或\(dp[i-1][j]+1\)，我们把差分数组在二进制下压一下就行了

预处理时间复杂度\(O(4*n*2^{Len(S)})\)，转移的时间复杂度为\(O(4*m*2^{Len(S)})\)，空间复杂度\(\theta (m*2^{Len(S)}+4*2^{Len(S)})\)

代码（预处理参考了）：

#include 
    
     #define MOD 1000000007using namespace std;int kase;string S;char ch[4] = {'A', 'C', 'G', 'T'};int n, m, tmp[2][20], lim, f[1001][32800], g[32800][4], ans[20];int lowbit(int x) {    return x&-x;}int popcount(int x) {    int cnt = 0;    while(x) cnt++, x -= lowbit(x);    return cnt;}int calc(int state, char c) {    for(int i = 1; i <= n; ++i) tmp[0][i] = tmp[0][i-1]+((state>>i-1)&1);    int ret = 0;    for(int i = 1; i <= n; ++i)    {        int t = 0;        if(c == S[i-1]) t = tmp[0][i-1]+1;        t = max(t, max(tmp[1][i-1], tmp[0][i]));        tmp[1][i] = t;    }    for(int i = 1; i <= n; ++i) ret += (1<
     
      > kase;    for(int i = 1; i <= kase; ++i) {        cin >> S >> m;        n = S.length();        lim = (1<