比赛链接

A qiqi20021026 的 T1

这题出的真离谱。。

考虑 $O(qn)$ 怎么做。显然建 trie 树后直接在上面求子树内第一个串的个数和第二个串的个数的最小值贡献在答案里面就行了。

正解，直接上四维莫队。由于 $n$ 比较大，串长期望很小，可以看成移动 $O(1)$ ，然后复杂度 $O(nq^{\frac 3 4})$ （莫队复杂度）。

为什么能跑过去 我也不知道啊。。玄学 。题解写了最后一个指针的移动次数实际上不多。。

$n\le 10^4 , q\le 5\times 10^5$ 能出这个复杂度是真的离谱。

#define P 998244353
int n , q;
const int BLO = 150;

int son[MAXN][26] , dep[MAXN] , idx = 1 , fa[MAXN] , pos[MAXN] , S[MAXN];
void ins( char* ch , int len , int p ) {
	int cur = 1;
	per( i , len , 1 ) {
		if( !son[cur][ch[i] - 'a'] ) son[cur][ch[i] - 'a'] = ++ idx , dep[idx] = dep[cur] + 1 , fa[idx] = cur;
		cur = son[cur][ch[i] - 'a'];
	}
	pos[p] = cur;
}

int s[MAXN][2] , cur;
void add( int u , int w , int v ) {
//	printf("%d %d %d\n",u,w,v);
	while( u != 1 ) {
		cur -= min( s[u][0] , s[u][1] );
		s[u][w] += v;
		cur += min( s[u][0] , s[u][1] );
		u = fa[u];
	}
}

struct que {
	int l1 , r1 , l2 , r2 , idx;
	void in( int i ) {
		scanf("%d%d%d%d",&l1,&r1,&l2,&r2) , idx = i;
	}
} Q[500006] ;

int bel[MAXN];

bool cmp( const que& a , const que& b ) {
	return bel[a.l1] == bel[b.l1] ? ( bel[a.l2] == bel[b.l2] ? ( bel[a.r1] == bel[b.r1] ? a.r2 < b.r2 : a.r1 < b.r1 ) : a.l2 < b.l2 ) : a.l1 < b.l1;
}

char ch[MAXN];
int ans[500006];
void solve() {
	cin >> n >> q;
	rep( i , 1 , n ) {
		scanf("%s",ch + 1);
		ins( ch , strlen( ch + 1 ) , i );
		S[i] = S[i - 1] + strlen( ch + 1 );
		bel[i] = ( S[i] - 1 ) / BLO + 1;
	}
	rep( i , 1 , q ) Q[i].in( i );
	sort( Q + 1 , Q + 1 + q , cmp );
	int l = 1 , r = 0 , L = 1 , R = 0 , l1 , l2 , r1 , r2;
	rep( i , 1 , q ) {
		l1 = Q[i].l1 , l2 = Q[i].l2 , r1 = Q[i].r1 , r2 = Q[i].r2;
		while( l > l1 ) -- l , add( pos[l] , 0 , 1 );
		while( r < r1 ) ++ r , add( pos[r] , 0 , 1 );
		while( l < l1 ) add( pos[l] , 0 , -1 ) , ++ l;
		while( r > r1 ) add( pos[r] , 0 , -1 ) , -- r;
		while( L > l2 ) -- L , add( pos[L] , 1 , 1 );
		while( R < r2 ) ++ R , add( pos[R] , 1 , 1 );
		while( L < l2 ) add( pos[L] , 1 , -1 ) , ++ L;
		while( R > r2 ) add( pos[R] , 1 , -1 ) , -- R;
		ans[Q[i].idx] = cur;
	}
	rep( i , 1 , q ) printf("%d\n",ans[i]);
}

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

B xuanyiming 的 T2

设 $F(n,i)$ 表示 $n$ 个点，恰有 $i$ 个联通块为树的方案数量。于是我们可以枚举最终的图中树的联通块数量，答案即为：

$$\sum_{i\ge 0} F(n,i) i^k$$

明显是不太能算 $F(n,i)$ 的，注意到 $k$ 很小，可以考虑斯特林数拆一下 $i^k$ ，尝试把枚举变成枚举到 $k$ （类似 Cards 的思路）。

$$\sum_{i\ge 0} F(n,i) \sum_{j=0}^k i^{\underline j} \begin{Bmatrix}k\\j\end{Bmatrix}$$

把下降幂写成组合数的形式，再交换求和符号有：

$$\sum_{j=0}^k \begin{Bmatrix}k\\j\end{Bmatrix} j! \sum_{i\ge 0} F(n,i)\binom i j$$

考虑后面那个东西

$$\sum_{i\ge 0} F(n,i) \binom i j$$

这个东西相当于是，钦定 $n$ 个点分成了 $j$ 个联通块作为树的方案数量。

我们设 $g(x)$ 为 树的个数 的生成函数，$f(x)$ 为 无向图（可以不联通）个数的生成函数，于是这个东西等于

$$\frac 1 {j!} g^j(x) f(x)$$

相当于任意选 $j$ 个树加进去，剩下的随意连图。

答案就是

$$n![x^n]\sum_{j=0}^k \begin{Bmatrix} k\\j \end{Bmatrix} g^j(x) f(x)$$

我们可以预处理

$$g^j(x)f(x)$$

就可以 $O(k)$ 回答询问了。

#define P 998244353
int n , k;
const int N = 50000;
int Pow( int x , int a ) {
	int ans = 1 , cur = x % P;
	while( a ) {
		if( a & 1 ) ans = 1ll * ans * cur % P;
		cur = 1ll * cur * cur % P , a >>= 1;
	}
	return ans;
}

int Wn[2][MAXN] , rev[MAXN];
void getwn( int len ) {
	for( int mid = 1 ; mid < len ; mid <<= 1 ) {
		int w0 = Pow( 3 , ( P - 1 ) / ( mid << 1 ) ) , w1 = Pow( 3 , P - 1 - ( P - 1 ) / ( mid << 1 ) );
		Wn[0][mid] = Wn[1][mid] = 1;
		for( int i = 1 ; i < mid ; ++ i )
			Wn[0][mid + i] = 1ll * Wn[0][mid + i - 1] * w0 % P,
					Wn[1][mid + i] = 1ll * Wn[1][mid + i - 1] * w1 % P;
	}
}
void getr( int len ) {
	int t = __builtin_ctz( len ) - 1;
	for( int i = 1 ; i < len ; ++ i ) rev[i] = ( rev[i >> 1] >> 1 ) | ( ( i & 1 ) << t );
}
void NTT( int* A , int len , int typ ) {
	rep( i , 0 , len - 1 ) if( i < rev[i] ) swap( A[i] , A[rev[i]] );
	for( int mid = 1 ; mid < len ; mid <<= 1 )
		for( int i = 0 ; i < len ; i += ( mid << 1 ) )
			for( int k = 0 ; k < mid ; ++ k ) {
				int t1 = A[i + k] , t2 = 1ll * A[i + k + mid] * Wn[typ][mid + k] % P;
				A[i + k] = (t1 + t2 > P ? t1 + t2 - P : t1 + t2) , A[i + k + mid] = (t1 - t2 < 0 ? t1 - t2 + P : t1 - t2);
			}
	if( typ == 1 ) for( int inv = Pow( len , P - 2 ) , i = 0 ; i < len ; ++ i ) A[i] = 1ll * A[i] * inv % P;
}

int g[MAXN] , F[23][MAXN] , f[23][MAXN] , J[MAXN] , iJ[MAXN];
int S[23][23];

void solve() {
	J[0] = iJ[0] = 1;
	rep( i , 1 , MAXN - 1 ) J[i] = J[i - 1] * 1ll * i % P , iJ[i] = Pow( J[i] , P - 2 );
	F[0][0] = 1;
	rep( i , 1 , N ) {
		g[i] = ( i > 1 ? Pow( i , i - 2 ) : 1 ) * 1ll * iJ[i] % P;
		F[0][i] = Pow( 2 , i * 1ll * (i - 1) / 2 % ( P - 1 ) ) * 1ll * iJ[i] % P;
	}
	getwn( ( 1 << 17 ) );
	int len = 1;
	while( len <= N + N ) len <<= 1;
	getr( len );
	NTT( g , len , 0 );
	rep( i , 1 , 20 ) {
		NTT( F[i - 1] , len , 0 );
		rep( j , 0 , len - 1 ) F[i][j] = F[i - 1][j] * 1ll * g[j] % P;
		NTT( F[i] , len , 1 );
		rep( j , N + 1 , len - 1 ) F[i][j] = 0;
		rep( j , 0 , N ) f[i][j] = F[i][j];
	}
	S[0][0] = 1;
	rep( i , 1 , 20 )
		rep( j , 1 , i )
			S[i][j] = ( S[i - 1][j - 1] + S[i - 1][j] * 1ll * j % P ) % P;
	int T; cin >> T;
	while( T-- ) {
		scanf("%d%d",&n,&k);
		int ans = 0;
		rep( j , 0 , k )
			( ans += S[k][j] * 1ll * f[j][n] % P ) %= P;
		ans = ans * 1ll * J[n] % P;
		printf("%d\n",ans);
	}
}

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