Yijan's Blog HomeArchives
10.16 模拟赛

10.16 模拟赛

T1

首先，对于全0或者全1可以手推或者打表发现是卡特兰数。

假设从0切换到1或者1切换到0，一定有$a_i \leq b_i \leq b_{i + 1} \leq a_{i + 1}$

相当于一定把前$i$个位置填完了才会开始填$i + 1$个位置。

所以直接乘起来就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<set>
using namespace std;
#define int long long
typedef long long ll;
#define MAXN 200006 
#define MAXM 450
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define inf 0x3f3f3f3f
#define cmx( a , b ) a = max( a , b )
#define cmn( a , b ) a = min( a , b )
#define upd( a , b ) ( a = ( a + b ) % P )
#define P 998244353
void read( signed& x ) {
	scanf("%d",&x);
}
void read( ll& x ) {
	scanf("%lld",&x);
}

int power( int x , int a ) {
	int cur = x % P , ans = 1;
	while( a ) {
		if( a & 1 ) ans *= cur , ans %= P;
		cur *= cur , cur %= P , a >>= 1;
	}
	return ans;
}
int n , J[MAXN] , invJ[MAXN];
int cat( int x ) {
	return J[2 * x] * invJ[x] % P * invJ[x + 1] % P;
}

signed main() <%
	cin >> n;
	J[0] = 1 , invJ[0] = 1; for( int i = 1 ; i <= 2 * n ; ++ i ) J[i] = J[i - 1] * i % P , invJ[i] = power( J[i] , P - 2 );
	int last = -1 , lst = 0 , res = 1;
	for( int i = 1 , t ; i <= n ; ++ i ) {
		scanf("%1d",&t);
		if( t == last ) ++ lst;
		else res *= ( last == -1 ? 1 : cat( lst ) ) , res %= P , last = t , lst = 1;
	}
	if( lst ) res *= ( last == -1 ? 1 : cat( lst ) ) , res %= P;
	cout << res << endl;
%>

/*
 * Things you should pay attention to
 * inf is big enough?
 * out of bounds?
 * long long ?
 */

T2

题解写的很清楚了，有问题就看题解了（懒得写一遍了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<set>
using namespace std;
#define int long long
typedef long long ll;
#define MAXN 200006 
#define MAXM 450
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define inf 0x3f3f3f3f
#define cmx( a , b ) a = max( a , b )
#define cmn( a , b ) a = min( a , b )
#define upd( a , b ) ( a = ( a + b ) % P )
#define P 998244353
void read( signed& x ) {
	scanf("%d",&x);
}
void read( ll& x ) {
	scanf("%lld",&x);
}
int n , m;
int head[MAXN] , to[MAXN << 1] , nex[MAXN << 1] , ecn;
void ade( int u , int v ) {
	to[++ecn] = v , nex[ecn] = head[u] , head[u] = ecn;
}
int s[MAXN];
void dfs( int u , int fa , int kel ) {
	s[u] = 1;
	int flga(1);
	for( int i = head[u] ; i ; i = nex[i] ) {
		int v = to[i];
		if( v == fa ) continue;
		dfs( v , u , kel );
		s[u] = min( s[u] , s[v] );
		flga = 0;
	}
	s[u] ^= 1;
	if( flga ) s[u] = kel;
}
int J[MAXN] , invJ[MAXN];
int C( int x , int a ) {
	return J[x] * invJ[a] % P * invJ[x - a] % P;
}
int power( int x , int a ) {
	int cur = x % P , ans = 1;
	while( a ) {
		if( a & 1 ) ans *= cur , ans %= P;
		cur *= cur , cur %= P , a >>= 1;
	}
	return ans;
}
int num00 , num01 , num10;
signed main() {
	cin >> n;
	J[0] = 1 , invJ[0] = 1; for( int i = 1 ; i <= 2 * n ; ++ i ) J[i] = J[i - 1] * i % P , invJ[i] = power( J[i] , P - 2 );
	int num = 0 , res = 0;
	for( int i = 1 ; i <= n ; ++ i ) {
		memset( head , 0 , sizeof head ) , ecn = 0;
		read( m );
		for( int i = 2 , p ; i <= m ; ++ i ) 
			read( p ) , ade( p , i ) , ade( i , p );
		dfs( 1 , 1 , 0 );
		int a = s[1] , b;
		dfs( 1 , 1 , 1 );
		b = s[1];
		a ^= 1 , b ^= 1 , swap( a , b );
		if( !a && !b ) ++ num00;
		if( !a && b ) ++ num01;
		if( a && !b ) ++ num10;
	}
	cout << ( power( 2 , n ) - power( 2 , num00 + num01 + max( num10 - 1 , 0ll ) ) + P ) % P << endl;
}

T3

考虑同一种颜色并且包含的情况，显然是可以舍弃掉这些情况的。

剩下的就容斥 然后 dp 统计。

容斥的式子是$s^{t} \times (-1)^k$t 为未被覆盖的点的个数，k为选择的区间数。

假设$dp[i]$是只考虑$r \leq i$的区间的答案，并且只考虑$1 … i$的位置可以填数。

首先我们可以选择不拿任何右端点为$i$的区间，那么直接$dp[i] += dp[i-1] \times s$

如果我们拿了某个右端点为$i$的区间，前一个区间要么是与这个区间没有交，要么与这个区间有交且颜色相同。

在容斥的情况下，我们拿了一个区间，其实就是将前面的贡献乘容斥系数$-1$然后再减去这个区间的贡献。因为原式子里面是$(-1)^k$

枚举一个右端点是这个点的区间，假设是$j$那么$dp[i] = dp[i] - dp[j.l - 1]$这里计算了包含这个区间，上一个区间无交的情况。

同时还有一种情况，选择了这个区间，上一个区间与这里有交，但是颜色相同。这种情况之间线段树统计即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<set>
using namespace std;
#define int long long
typedef long long ll;
#define MAXN 500006 
#define MAXM 450
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define inf 0x3f3f3f3f
#define cmx( a , b ) a = max( a , b )
#define cmn( a , b ) a = min( a , b )
#define upd( a , b ) ( a = ( a + b ) % P )
#define P 998244353
void read( signed& x ) {
	scanf("%d",&x);
}
void read( ll& x ) {
	scanf("%lld",&x);
}
int n , m , s;
struct node {
	int l , r , b;
};
int ls[MAXN << 3] , rs[MAXN << 3] , T[MAXN << 3] , cn , rt[MAXN];
void mdfy( int &rt , int l , int r , int p , int c ) {
	if( !rt ) rt = ++ cn;
	T[rt] += c , T[rt] %= P;
	if( l == r ) return;
	int m = l + r >> 1;
	if( p <= m ) mdfy( ls[rt] , l , m , p , c );
	else mdfy( rs[rt] , m + 1 , r , p , c );
}
int query( int rt , int l , int r , int L , int R ) {
	if( !rt ) return 0;
	if( L <= l && R >= r ) return T[rt];
	int m = l + r >> 1 , res = 0;
	if( L <= m ) res += query( ls[rt] , l , m , L , R ) , res %= P;
	if( R > m ) res += query( rs[rt] , m + 1 , r , L , R ) , res %= P;;
	return res;
}
bool cmp( node a , node b ) {
	return a.l == b.l ? a.r < b.r : a.l > b.l;
}
vector<node> V[MAXN] , S[MAXN];
int dp[MAXN];
signed main() {
	read( n ) , read( m ) , read( s );
	for( int i = 1 , l , r , b ; i <= m ; ++ i ) 
		read( l ) , read( r ) , read( b ) , V[b].pb( (node) { l , r , b } );
	for( int i = 1 ; i <= s ; ++ i ) {
		sort( V[i].begin( ) , V[i].end( ) , cmp );
		int minr = n + 1;
		for( int j = 0 ; j < V[i].size() ; ++ j ) 
			if( V[i][j].r < minr ) 
				S[V[i][j].r].pb( V[i][j] ) , minr = V[i][j].r;
	}
	dp[0] = 1;
	for( int i = 1 ; i <= n ; ++ i ) {
		dp[i] = dp[i - 1] * s % P;
		for( int j = 0 ; j < S[i].size() ; ++ j ) {
			int v = 0;
			v -= dp[S[i][j].l - 1] , v += P , v %= P;
			v -= query( rt[S[i][j].b] , 1 , n , S[i][j].l , S[i][j].r ) , v += P , v %= P;
			mdfy( rt[S[i][j].b] , 1 , n , i , v );
			dp[i] += v , dp[i] %= P;
		}
	}
	cout << dp[n] << endl;
}
文章作者: yijan
文章链接: https://yijan.co/old9/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog！
比赛