A 第一题

考虑建出子序列自动机。现在有了一个 DAG。

有两种做法。

我们可以按照子树内 dp 值最大（含的子序列个数最多的）儿子作为重儿子。类似地做轻重链剖分。考虑如果走了一条轻边，往轻儿子走明显答案至少会减半。

否则，我们会往重儿子走很多次。可以倍增来走重儿子。

麻烦点在于输出。有一种很优秀的实现方式，考虑先按照这样的方式跳总长度 - p 次，然后暴力跳 p 次即可。

要对 $10^{18}$ 取 $\min$ ，否则路径总数是指数级别的，直接做会爆炸。

还有一种 zjk 的神仙做法。考虑连续段的个数，会发现必然不超过 $\log + 26$。

因为考虑有很多连续段，如果出现了这个连续段大于后面一个连续段，那么之后的连续段的个数肯定是 $\log$ 级别的。因为如果删去了这个连续段，那么得到的串任意一个包含第一个字母的子序列必然小于这个串。而询问的 $k$ 只是 $10^{18}$ 级别的。后面的串的子序列个数是指数级别的，而后面的串的子序列个数不应该超过 $10^{18}$ ，所以后面的连续段的个数不会超过 $\log$ 。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 300006
//#define int long long
#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 pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , q;
int A[MAXN];
char ch[MAXN];

struct que {
	int p , idx; ll k;
} Q[MAXN] ; int cc = 1;

ll c[MAXN] , mx;
int nxt[MAXN][26] , G[MAXN][20];
ll valG[MAXN][20];

vector<pii> ans;
int lsj , dep = 0;
#include "assert.h"
void sol( int u , ll rk ) {
//	cout << ++ dep << ' ' << u << endl;
	if( rk == 0 ) return;
	ll fk = 1;
	rep( i , 0 , 25 ) if( nxt[u][i] ) {
		if( fk + c[nxt[u][i]] - 1 >= rk ) {
			int pr = nxt[u][i];
			if( i == ch[u] - 'a' ) {
				pr = u; int lg = 0;
				per( k , 19 , 0 ) if( G[pr][k] && valG[pr][k] <= rk && valG[pr][k] + c[G[pr][k]] - 1 >= rk ) 
					rk -= valG[pr][k] , pr = G[pr][k] , lg |= ( 1 << k );
//				cout << lg << endl;
				ans.eb( mp( i , lg ) );
			} else 
				ans.eb( mp( i , 1 ) ) , rk -= fk;
			sol( pr , rk );
			return;
		}
		fk += c[nxt[u][i]];
	}
	lsj = 1;
}

int lst[27];

void solve() {
	scanf("%s",ch + 1);
	n = strlen( ch + 1 );
	cin >> q;
	rep( i , 1 , q ) 
		scanf("%lld%d",&Q[i].k,&Q[i].p) , Q[i].idx = i , mx = max( mx , Q[i].k );
	for( int i = n ; i >= 0 ; -- i ) {
		c[i] ++;
		rep( j , 0 , 25 ) if(lst[j]) {
				nxt[i][j] = lst[j];
				if( c[i] <= mx ) 
					c[i] += c[nxt[i][j]];
			}
		if( i ) lst[ch[i]-'a'] = i;
		if( i && nxt[i][ch[i] - 'a'] ) {
			valG[i][0] = 1;
			rep( j , 0 , ch[i] - 'a' - 1 ) valG[i][0] += c[nxt[i][j]];
			G[i][0] = nxt[i][ch[i] - 'a'];
			for( int k = 1 ; k <= 19 ; ++ k ) {
				if( G[G[i][k - 1]][k - 1] ) G[i][k] = G[G[i][k - 1]][k - 1] , valG[i][k] = valG[i][k-1] + valG[G[i][k-1]][k-1];
				else break;
			}
		}
	}
	rep( i , 1 , q ) {
		ll k = Q[i].k; int p = Q[i].p;
		ans.clear() , lsj = 0;
		sol( 0 , k );
//		for( auto x : ans ) printf("%d %d\n",x.fi,x.se);
		int lg = 0;
		vector<char> re;
		if( lsj ) puts("-1");
		else { 
			per( i , ans.size() - 1 , 0 ) {
				rep( j , lg + 1 , min( lg + ans[i].se , p ) ) re.pb( ans[i].fi + 'a' );
				if( lg + ans[i].se >= p ) break;
				lg += ans[i].se;
			}
			per( i , re.size() - 1 , 0 ) putchar( re[i] );
			puts("");
		}
	}
}

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

B 第二题

首先，我们会矩乘。可以直接获得 80 分。

标程是直接用精度换时间整过去的最后两个点，也可以在 $m$ 很大的时候直接看成对角矩阵（但是明显可以被卡）。

考虑一种与精度没有关系的做法。我们考虑一个数被操作 $m$ 次后会被 加 / 减 多少次。

$$(\frac 1 k x + \frac 1 k x^{-1} + \frac{k-2}{k})^m$$

我们写成展开的式子

$$\begin{aligned} \sum_{i=-m}^m a_ix^i\\ \end{aligned}$$

然后考虑，我们相当于需要对所有 $\pmod d$ 为 $i$ 的位置的系数求和。就是在 $x=1$ 的时候下面多项式的值

$$\begin{aligned} &= \sum_{i=-m}^m [d|(i-t)] a_ix^i\\ &= \sum_{i=-m}^m a_ix^i \frac 1 d \sum_{j=0}^{d-1} \omega_d^{j(i-t)}\\ &= \frac 1 d \sum_{j=0}^{d-1} \omega_d^{-jt} \sum_{i=-m}^m a_i(x\omega_d^j)^i \end{aligned}$$

后面那一坨明显可以写回开始的式子，只是把 $x$ 变成 $x\omega_d^j$

$$= \frac 1 d\sum_{j=0}^{d-1} \omega_d^{-jt} (\frac 1 k(\omega_d^j)+\frac 1 k (\omega_d^{-j}) + \frac{k-2}{k})^m$$

可以参考钟神的实现，我写的比较好写的数据分治。。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 3000006
//#define int long long
#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 pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , d , m;
char ch[MAXN];
struct mtrx {
	double A[11][11];
	mtrx( ) {
		mem( A );
	}
} tmp , mre , pre ;
mtrx mul( mtrx& a , mtrx& b ) {
	mtrx ret;
	rep( i , 0 , d - 1 ) rep( j , 0 , d - 1 ) rep( k , 0 , d - 1 ) ret.A[i][j] += a.A[i][k] * b.A[k][j];
	return ret;
}

void Pow( mtrx& a , ll x ) {
	rep( i , 0 , d - 1 ) rep( j , 0 , d - 1 ) pre.A[i][j] = 0;
	rep( i , 0 , d - 1 ) pre.A[i][i] = 1;
	while( x ) {
		if( x & 1 ) pre = mul( pre , a );
		a = mul( a , a ) , x >>= 1;
	}
}

double ans[11];

void solve() {
	ll m;
	cin >> n >> d >> m;
	scanf("%s",ch );
	double p = 1.0 / d;
	mtrx gg;
	for( int i = 0 , c = 1 ; i < n ; i += d , ++ c ) {
		mtrx re;
		if( n <= 300000 ) {
			rep( j , 0 , d - 1 ) {
				int fr = j , to = ( j + 1 ) % d;
				re.A[fr][to] += p / c , re.A[to][fr] += p / c , re.A[fr][fr] += ( p - re.A[fr][to] ) , re.A[to][to] += ( p - re.A[fr][to] );
				rep( t , 0 , d - 1 ) if( t != fr && t != to ) re.A[t][t] += p;
			}
			Pow( re , m );
//		rep( i , 0 , d - 1 ){ rep( j , 0 , d - 1 ) 
//			printf("%lf ",re.A[i][j] ); puts("");
//		}
		}
		rep( j , i , i + d - 1 ) 
			gg.A[j % d][ch[j] - '0'] += j + 1;
		double tt = 1.0 / d;
		rep( j , 0 , d - 1 ) {
			rep( t , 0 , d - 1 ) 
			ans[t] += gg.A[j][t] * ( n <= 300000 ? pre.A[j][t] : tt );// , printf("%lf ",gg.A[j][t]);
//			puts("");
		}
	}
	rep( i , 0 , d - 1 ) printf("%.8lf\n",ans[i]);
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}

C 第三题

显然有删掉的边的数量就是一棵树的叶子数量。

考虑把两个树的根连起来，在不考虑中间叶子连边的时候会得到一个树。所以在 cut 掉边后会得到一个有 $m+1$ 连通块的森林。

同时，cut 边之后不能有没有叶子的连通块。否则这个连通块就无法与其他连通块联通。

然后有个结论，总是可以把这 $2m$ 个叶子（存在于不同连通块中）加入 $m-1$ 条边，使得最后得到的是一个树，且在叶子间原题中的两棵树上是个完美匹配。考虑归纳证明。对于 $m=1$ 的时候显然是对的，否则，由于抽屉原理，一定有一个连通块中只有一个叶子，我们把它和存在于另一个树中的任意一个有不止一个叶子的连通块的一个叶子连边，然后不再考虑这两个叶子。这样会得到一个 $m$ 连通块的森林（有一个连通块不再有需要考虑的叶子了），有 $2(m-2)$ 个点，仅加入 $m-2$ 条边。可以一直这么加下去，一定会得到一个树。

现在我们可以把删边问题转化为加边问题了。我们只需要在加边的时候保证含有叶子的联通块的个数不超过 $m+1$ 即可。

事实上在边集上这是个拟阵。下面引用钟神的证明：

对于两个合法的边集 $A,B$，$|A| < |B|$，有以下两种情况：

1. $A$ 中含有叶子的连通块数 $> m+1$：从 $B$ 中选出一条边加入 $A$ 后无环的边即可。
2. $A$ 中含有叶子的连通块数 $= m+1$：我们把 $A$ 中的连通块分成两个集合 $X,Y$，$X$ 中的连通块都含有叶子，$Y$ 中的连通块都不含叶子。如果 $B$ 中存在连接 $X,Y$ 中的点的边，或者存在连接 $Y$ 中属于不同连通块的点的边，选择这条边加入即可；否则 $B$ 在 $Y$ 中的点之间的边数小于等于 $A$ 的，又因为 $|B| > |A|$，所以 $B$ 在 $X$ 中的点之间的边数大于 $A$ 的，所以 $X$ 中的点在 $B$ 中形成的连通块数小于 $A$，即小于 $m+1$，又因为所有的叶子都在 $X$ 中，所以 $B$ 中含有叶子的连通块数小于 $m+1$，所以 $B$ 不合法，所以这种情况不存在。

也就是说只要从小到大加边即可。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 300006
//#define int long long
#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 pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m;
int A[MAXN];

tuple<int,int,int> E[MAXN];
int cn = 0 , deg[MAXN] , LeaF[MAXN] , cc;

int fa[MAXN];
int find( int x ) {
	return x == fa[x] ? x : fa[x] = find( fa[x] );
}

void solve() {
	cin >> n;
	int u , v , w;
	ll S = 0;
	rep( i , 2 , n ) 
		scanf("%d%d%d",&u,&v,&w) , E[++ cn] = make_tuple( -w , u , v ) , ++ deg[u] , ++ deg[v] , S += w;
	rep( i , 2 , n )
		scanf("%d%d%d",&u,&v,&w) , u += n , v += n , E[++ cn] = make_tuple( -w , u , v ) , ++ deg[u] , ++ deg[v] , S += w;
	n = n + n;
	sort( E + 1 , E + 1 + cn );
	rep( i , 2 , n ) LeaF[i] = ( i != n / 2 + 1 && deg[i] == 1 ) , cc += LeaF[i] , fa[i] = i;
	fa[1] = n / 2 + 1;
	int c = cc / 2 + 1;
	ll re = 0;
	rep( i , 1 , cn ) {
		int u = find( get<1>( E[i] ) ) , v = find( get<2>( E[i] ) );
		if( u == v ) continue;
		if( !LeaF[u] || !LeaF[v] || cc > c ) cc -= ( LeaF[u] & LeaF[v] ) , LeaF[u] |= LeaF[v] , fa[v] = u , re += -get<0>( E[i] );
	}
	cout << S - re << endl;
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}