AGC046D Secret Passage

好像我做法比题解做法麻烦。。

我们考虑最终得到的串肯定会有一个子序列和原串结尾的一段子段相同，这些位置是保持不动的，而需要从 $S$ 前面的位置往这些位置插入字符。

现在就有了一个想法：能不能枚举一段原串的后缀和操作次数（通过操作次数可以确定串长），统计可以得到多少种不同的字符串？但是事实上可能会出现重复统计的情况，即一个串可能有多个后缀与之对应。

于是我们可以考虑在最短的、可以得到这个串的后缀处计算它。具体而言，当确定了操作次数和选择不动的后缀时，前面可以往后插入的 $0$ 的个数会形成一段区间，且后面能形成怎么样的串只取决于插入的 $0$ 的数量。。而随着后缀逐渐前移，这个区间也在不断扩大，因为当后缀增大时，意味着除开后缀的部分可以额外进行操作，这时候就可以通过 $00110 \to 1010 \to 1+1$ 的方法来让前面可以往后移动的 $0/1$ 的个数增加。

每当后缀增加一个 $0/1$ 时，将可以往后插入的 $0$ 的个数的区间对应更新一下，然后尝试一下这个区间是否可以扩大，如果可以就统计新增的方案数。这样对于任何一个终串，它一定在最短的可以被插入得到的后缀统计到正好一次。正确性可以使劲品一下

实现可以考虑设 $f[i][a][b]$ 表示前 $i$ 个数不断进行操作且被删空时，是否可以往后插入 $a$ 个 $0$ 和 $b$ 个 $1$ ，以及 $F[i][a][b]$ 表示从 $i$ 往后的后缀如果插入 $a$ 个 $0$ 和 $b$ 个 $1$ 能形成的不同串的数量。这两个都可以 $O(1)$ 转移。

实现有点细节，建议仔细想清楚再开写，不然就像我一样写的很丑。。复杂度 $O(n^3)$ 。

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define mp make_pair
#define rep( i , a , b ) for( int i = (a) , i##end = b ; i <= i##end ; ++ i )
#define per( i , a , b ) for( int i = (a) , i##end = b ; i >= i##end ; -- i )
#define mem( a ) memset( a , 0 , sizeof (a) )
#define all( x ) x.begin() , x.end()
//#define int long long
// #pragma GCC optimize(2)
typedef long long ll;
const int MAXN = 1e6 + 10;
const int P = 1e9 + 7;

struct op {
    int o , a , b , c;
};
vector<op> ops;

ll reg[MAXN];
void sum( int i , int j , int k ) {
    ops.pb( (op) { 0 , i , j , k } );
    ll re = reg[i] + reg[j];
    reg[k] = re;
}

void jud( int i , int j , int k ) {
    ops.pb( (op) { 1 , i , j , k } );
    int re = reg[i] < reg[j];
    reg[k] = re;
}

void solve() {
    reg[0] = 13224 , reg[1] = 535342;
    jud( 2 , 0 , 3 );
    int td = 3;
    rep( i , 1 , 29 ) {
        sum( td + i - 1 , td + i - 1 , td + i );
    }
    sum( 0 , td , 0 ) , sum( 1 , td , 1 );
    int tr = td + 30 + 2 , tp = tr + 30 + 2;
    int ga = tp + 5;
    per( k , 29 , 0 ) {
        sum( tp , td + k , tp + 1 );
        jud( tp + 1 , 1 , tr + k );
        rep( t , 1 , k ) sum( tr + k , tr + k , tr + k );
        sum( tr + k , tp , tp );
        sum( tr + k , 10000 , ga + 1 );
        jud( ga + 1 , td , ga + 1 );
        rep( p , 1 , 30 ) sum( ga + 1 , ga + 1 , ga + 1 );
        jud( ga + 3 , ga + 3 , ga + 3 );
        per( t , 29 , 0 ) {
            sum( ga + 3 , td + t , ga + 2 );
            sum( ga + 2 , ga + 1 , ga + 2 );
            jud( ga + 2 , 0 , ga + 4 );
            rep( k , 1 , t ) sum( ga + 4 , ga + 4 , ga + 4 );
            sum( ga + 4 , ga + 3 , ga + 3 );
        }
        rep( t , 1 , k ) sum( ga + 3 , ga + 3 , ga + 3 );
        sum( ga , ga + 3 , ga );
        // if( k == 0 ) {
        //     cout << reg[ga] << ' ' << reg[tr + k] << endl;
        // }
    }
    sum( ga , 10000 , 2 );
    cout << ops.size() << endl;
    // cout << reg[2] << endl;
    for( auto t : ops ) {
        if( t.o ) printf("< %d %d %d\n",t.a,t.b,t.c);
        else printf("+ %d %d %d\n",t.a,t.b,t.c);
    }
}

signed main() {
//	 freopen("in","r",stdin);
	// freopen("fout","w",stdout);
	// int T;cin >> T;while( T-- ) solve();
	solve();
}