AGC 024 F

我们考虑对于所有串 $S$ 计数它是多少个串的子序列。

我们假设 $(S,T)$ 为当前有一个字符串 $S$ ，我们要往后面加一些字符 $T’$ 并且是 $T$ 的一个子序列，转移类似子序列自动机来走，对于每个 $i$ 处理出 $nxt[i][c]$ 表示 $i$ 后面第一个 $c$ 的位置。

• $T’ = \varnothing$ ，相当于走到了 $(S,\varnothing)$ 就是不再加字符了
• $T’ = 0$ ，找到 $T$ 中第一个 0 ，跳过去，转移到 $(S+0,T+t_0)$
• $T’ = 1$ ，找到第一个 1 ，跳过去，转移到 $(S+1,T+t_1)$

根据前面的分析，显然 $(\varnothing,T)$ 可以走到 $(S,\varnothing)$ 就等价于 $S$ 是 $T$ 的子序列，并且这样的路径是唯一的。

每个状态满足 $|S|+|T| \leq N$ 所以总的状态数量是 $O(n2^n)$ 的。

然后就是对于一个 $(S,\varnothing)$ 算出有多少个起点可以到达它，可以直接设 $F(sta)$ 表示有多少条路径，并且由于路径唯一，路径的个数本质上就等价于有多少个起点可以到达它。

但是，这个东西实现起来有点麻烦啊。。一种比较简单的考虑方式是 $dp[len][sta][k]$ 表示长度为 $len$ 状态为 $sta$ 分割位置是 $k$ ，但是这个东西算算空间暴毙了啊。。可能用指针动态分配内存是可以的，但是貌似很麻烦还容易爆炸。

参考了一下钟神的实现，设 dp 状态时这样设：$dp[sta][k]$ ，其中 $sta$ 为一个长度为 $i+1$ 的二进制，它的最高位必然是一个 1 ，这个 1 是用来占位的，实际上这个状态下的 $S + T$ 是第 $0$ 到 $i$ 位，然后 $k$ 代表 $S,T$ 的分割位置，这个状态的值是到达这种状态的路径条数。

初始状态是所有串的本身和 $k = i$ 的情况，这种状态的值应当为 1 。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
using namespace std;
#define MAXN 21
int n , k , dp[1 << 21][21];
char ch[1 << 21];
int main() {
    cin >> n >> k;
    for( int i = 0 ; i <= n ; ++ i ) {
        scanf("%s",ch);
        for( int j = 0 ; j < ( 1 << i ) ; ++ j )
            dp[( 1 << i ) | j][i] = ( ch[j] == '1' );
    }
    int re1 = 0 , re2 = 0;
    for( int i = n ; i >= 0 ; -- i ) {
        for( int j = 0 ; j < ( 1 << i ) ; ++ j ) // sta : ( 1 << i ) | j
            for( int k = i ; k > 0 ; -- k ) if( dp[( 1 << i ) | j][k] ) {
                int S = ( j >> k ) , T = ( j & ( 1 << k ) - 1 ) , f = dp[( 1 << i ) | j][k];
                dp[( 1 << i - k ) | S][0] += f;
                int ls = T & ( 1 << k ) - 1 , re = (~T) & ( 1 << k ) - 1;
                if( T ) {
                    int u = 31 - __builtin_clz( ls );
//                    cout << ls << ' ' << u << endl;
                    dp[( 1 << i - k + u + 1 ) | ( S << u + 1 ) | ( 1 << u ) | ( T & ( 1 << u ) - 1 )][u] += f;
                }
                if( re ) {
                    int u = 31 - __builtin_clz( re );
//                    cout << T << ' ' << u << ' ' << k << endl;
                    dp[( 1 << i - k + u + 1 ) | ( S << u + 1 ) | ( T & ( 1 << u ) - 1)][u] += f;
                }
            }
    }
    for( int i = n ; i >= 0 ; -- i )
        for( int j = 0 ; j < ( 1 << i ) ; ++ j ) if( dp[( 1 << i ) | j][0] >= k ) {
            for( int k = i - 1 ; k >= 0 ; -- k ) printf("%d",( j >> k ) & 1);
            return 0;
        }
}