Yijan's Blog HomeArchives
PKUSC 部分题解

D1T1 D2T1 非常签到，就不写了。

不会真的有人写 D1T3 吧，不会吧不会吧

D1T2

首先考虑部分分，部分分就是直接求 $\max[l,l+c]$ 为初始值走 $[l+c,r+c]$ 的单调栈的长度。

我们考虑设数组 $b_i$ 表示在经历若干操作后， $A_i$ 的值变成了原序列中 $[i,b_i]$ 的最大值。

考虑 $b_i$ 的转移，不难发现就是一次区间平移然后往最后插入一个 $b_r$ 。

但是即使维护了 $b_i$ 仍然不好方便地做这个东西。然后就有一个非常神仙的转化：设 $c_i = \max[b_{i-1}+1,b_i]$ ，也就是把相邻两个 $b_i$ 之间的东西作为 $c_i$ ，特别的，如果 $b_{i-1}=b_i$ 我们认为 $c_i = 0$ 。这样转化后，会发现答案就类似于之前部分分的东西，是 $[l,b_l]$ 之内的最大值在走 $c[l,r]$ 的单调栈长度。画图一下就会发现这个转化非常有道理，就是把重复部分去掉了。

考虑怎么维护 $c$ ，不难发现对 $b$ 的操作对应到 $c$ 就是将 $c_l,c_{l+1}$ 中保留较大的值，然后在 $c_r$ 处插入一个 $0$ 。而插入 $0$ 其实是不存在的操作，所以实际上只需要支持删除即可！

但是还是需要维护 $c_i$ 实际上对应的是 $A$ 中的哪个数，这里还是得平衡树的（）后面直接楼房重建的线段树即可。

复杂度 $O(n\log^2 n)$ 。

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 1000006
//#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 RT , siz[MAXN] , val[MAXN] , fa[MAXN] , ch[MAXN][2] , idx;

void pu( int rt ) {
	siz[rt] = 1 + siz[ch[rt][0]] + siz[ch[rt][1]];
}
void rotate( int u ) {
	int f = fa[u] , g = fa[f] , w = ch[f][1] == u , k = ch[u][w ^ 1];
	if( g ) ch[g][ch[g][1] == f] = u;
	ch[u][w ^ 1] = f , ch[f][w] = k;
	fa[f] = u , fa[k] = f , fa[u] = g;
	pu( f ) , pu( u );
}
void splay( int u , int to = 0 ) {
	if (!to) RT = u;
	int f , g;
	while( fa[u] != to ) {
		f = fa[u] , g = fa[f];
		if( g != to ) rotate( ( ch[f][1] == u ^ ch[g][1] == f ) ? u : f );
		rotate( u );
	}
}
int poi;
int kth( int u , int x ) {
	if( !u ) return 0;
	if( x <= siz[ch[u][0]] ) return kth( ch[u][0] , x );
	if( x == siz[ch[u][0]] + 1 ) return u;
	return kth( ch[u][1] , x - siz[ch[u][0]] - 1 );
}

void ins( int u , int v ) {
	while( ch[u][0] ) u = ch[u][0];
	ch[u][0] = ++ idx;
	val[idx] = v , fa[idx] = u , siz[idx] = 1 , u = idx;
	while( fa[u] ) u = fa[u] , pu( u );
}

void era( int u , int k ) {
	int pr = kth( RT , k - 1 );
	splay( pr );
	int nx = kth( RT , k + 1 );
	splay( nx , pr );
	ch[ch[RT][1]][0] = 0;
	pu( ch[RT][1] ) , pu( RT );
}

int qwq[MAXN];
void bsplay( int& rt , int f , int l , int r ) {
	if( l > r ) return;
	int m = l + r >> 1;
	rt = ++ idx;
	val[rt] = qwq[m] , siz[rt] = 1 , fa[rt] = f;
	bsplay( ch[rt][0] , rt , l , m - 1 ) , bsplay( ch[rt][1] , rt , m + 1 , r );
	pu( rt );
}

int mx[MAXN << 2] , cn[MAXN << 2];
ll lt[MAXN << 2];
int A[MAXN] , LeaF[MAXN << 2];

ll wkr( int rt , int v ) {
	if( !lt[rt] || v >= mx[rt] ) return 0;
	if( LeaF[rt] ) return mx[rt];
	if( v >= mx[rt << 1] ) return wkr( rt << 1 | 1 , v );
	return lt[rt] - ( lt[rt << 1] - wkr( rt << 1 , v ) );
}

void pus( int rt ) {
	mx[rt] = max( mx[rt << 1] , mx[rt << 1 | 1] );
	lt[rt] = lt[rt << 1] + wkr( rt << 1 | 1 , mx[rt << 1] );
}

void build( int rt , int l , int r ) {
	if( l == r ) { mx[rt] = lt[rt] = A[l] , LeaF[rt] = cn[rt] = 1; return; }
	int m = l + r >> 1;
	build( rt << 1 , l , m ) , build( rt << 1 | 1 , m + 1 , r );
	pus( rt );
}

void ad( int rt , int l , int r , int p ) {
	if( l == r ) { cn[rt] ++; return; }
	int m = l + r >> 1;
	if( p <= m ) ad( rt << 1 , l , m , p );
	else ad( rt << 1 | 1 , m + 1 , r , p );
}

void fuck( int rt , int l , int r , int p ) {
	if( l == r ) { if( cn[rt] == 1 ) mx[rt] = lt[rt] = 0; else -- cn[rt]; return; }
	int m = l + r >> 1;
	if( p <= m ) fuck( rt << 1 , l , m , p );
	else fuck( rt << 1 | 1 , m + 1 , r , p );
	pus( rt );
}

int tv;
ll re;
void que( int rt , int l , int r , int L , int R ) {
	if( L <= l && r <= R ) { re += wkr( rt , tv ) , tv = max( tv , mx[rt] ); return; }
	int m = l + r >> 1;
	if( L <= m ) que( rt << 1 , l , m , L , R );
	if( R > m ) que( rt << 1 | 1 , m + 1 , r , L , R );
}

void ot( int rt ) {
	if( ch[rt][0] ) ot( ch[rt][0] );
	printf("%d ",val[rt]);
	if( ch[rt][1] ) ot( ch[rt][1] );
}

int g[MAXN][20];
int qmx( int l , int r ) {
	int t = 31 - __builtin_clz( r - l + 1 );
	return max( g[l][t] , g[r - ( 1 << t ) + 1][t] );
}

void solve() {
	cin >> n >> q;
	rep( i , 2 , n + 1 ) qwq[i] = i - 1;
	qwq[1] = -0x3f3f3f3f , qwq[n + 2] = 0x3f3f3f3f;
	bsplay( RT , 0 , 1 , n + 2 );
	rep( i , 1 , n ) scanf("%d",A + i) , g[i][0] = A[i];
	build( 1 , 1 , n );
	rep( k , 1 , 18 ) rep( i , 1 , n - ( 1 << k ) + 1 )
		g[i][k] = max( g[i][k - 1] , g[i + ( 1 << k - 1 )][k - 1] );
	rep( i , 1 , q ) {
		int o , l , r;
		scanf("%d%d%d",&o,&l,&r);
		if( o == 1 ) {
			if( l == r ) continue;
			
			int t = kth( RT , r + 1 );
			splay( t );
			ad( 1 , 1 , n , val[t] );
			ins( ch[RT][1] , val[t] );
			
			int v1 = val[kth( RT , l + 1 )] , v2 = val[kth( RT , l + 2 )];
			if( A[v1] < A[v2] ) fuck( 1 , 1 , n , v1 ) , era( RT , l + 1 );
			else fuck( 1 , 1 , n , v2 ) , era( RT , l + 2 );
		} else {
			int L = val[kth( RT , l + 1 )] , R = val[kth( RT , r + 1 )];
			tv = re = qmx( l , L );
			que( 1 , 1 , n , L , R );
			printf("%lld\n",re);
		}
//		ot( RT ); puts("");
	}
}

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

D2T2 代金券

场上一直没注意到分界点可以二分，能注意到估计就过了。。

考虑一个贪心，最终策略肯定是某个东西之前尽量花钱得代金券，然后到某个时刻把所有代金券用掉，然后前面的 $A_i \bmod c$ 部分也需要尽量用掉代金券。显然其他最优策略可以调整成这种。

然后就变成了一个这样的问题，每次代金券数量会增加 $A_i / c$ ，如果增加之前大于等于 $A_i \bmod c$ ，就会减去这么多。

这个其实就是一个括号匹配问题，每个位置相当于会先加入 $A_i \bmod c$ 个左括号，$A_i / c$ 个右括号，需要找到第一个位置使得积累的右括号数量大于等于后面所有数的和。

这个东西是可以二分的，于是线段树维护括号匹配即可。

复杂度 $O(n \log^2 n)$ ，或许可以优化到单 $\log$ 。

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 1000006
//#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 RT , siz[MAXN] , val[MAXN] , fa[MAXN] , ch[MAXN][2] , idx;

void pu( int rt ) {
	siz[rt] = 1 + siz[ch[rt][0]] + siz[ch[rt][1]];
}
void rotate( int u ) {
	int f = fa[u] , g = fa[f] , w = ch[f][1] == u , k = ch[u][w ^ 1];
	if( g ) ch[g][ch[g][1] == f] = u;
	ch[u][w ^ 1] = f , ch[f][w] = k;
	fa[f] = u , fa[k] = f , fa[u] = g;
	pu( f ) , pu( u );
}
void splay( int u , int to = 0 ) {
	if (!to) RT = u;
	int f , g;
	while( fa[u] != to ) {
		f = fa[u] , g = fa[f];
		if( g != to ) rotate( ( ch[f][1] == u ^ ch[g][1] == f ) ? u : f );
		rotate( u );
	}
}
int poi;
int kth( int u , int x ) {
	if( !u ) return 0;
	if( x <= siz[ch[u][0]] ) return kth( ch[u][0] , x );
	if( x == siz[ch[u][0]] + 1 ) return u;
	return kth( ch[u][1] , x - siz[ch[u][0]] - 1 );
}

void ins( int u , int v ) {
	while( ch[u][0] ) u = ch[u][0];
	ch[u][0] = ++ idx;
	val[idx] = v , fa[idx] = u , siz[idx] = 1 , u = idx;
	while( fa[u] ) u = fa[u] , pu( u );
}

void era( int u , int k ) {
	int pr = kth( RT , k - 1 );
	splay( pr );
	int nx = kth( RT , k + 1 );
	splay( nx , pr );
	ch[ch[RT][1]][0] = 0;
	pu( ch[RT][1] ) , pu( RT );
}

int qwq[MAXN];
void bsplay( int& rt , int f , int l , int r ) {
	if( l > r ) return;
	int m = l + r >> 1;
	rt = ++ idx;
	val[rt] = qwq[m] , siz[rt] = 1 , fa[rt] = f;
	bsplay( ch[rt][0] , rt , l , m - 1 ) , bsplay( ch[rt][1] , rt , m + 1 , r );
	pu( rt );
}

int mx[MAXN << 2] , cn[MAXN << 2];
ll lt[MAXN << 2];
int A[MAXN] , LeaF[MAXN << 2];

ll wkr( int rt , int v ) {
	if( !lt[rt] || v >= mx[rt] ) return 0;
	if( LeaF[rt] ) return mx[rt];
	if( v >= mx[rt << 1] ) return wkr( rt << 1 | 1 , v );
	return lt[rt] - ( lt[rt << 1] - wkr( rt << 1 , v ) );
}

void pus( int rt ) {
	mx[rt] = max( mx[rt << 1] , mx[rt << 1 | 1] );
	lt[rt] = lt[rt << 1] + wkr( rt << 1 | 1 , mx[rt << 1] );
}

void build( int rt , int l , int r ) {
	if( l == r ) { mx[rt] = lt[rt] = A[l] , LeaF[rt] = cn[rt] = 1; return; }
	int m = l + r >> 1;
	build( rt << 1 , l , m ) , build( rt << 1 | 1 , m + 1 , r );
	pus( rt );
}

void ad( int rt , int l , int r , int p ) {
	if( l == r ) { cn[rt] ++; return; }
	int m = l + r >> 1;
	if( p <= m ) ad( rt << 1 , l , m , p );
	else ad( rt << 1 | 1 , m + 1 , r , p );
}

void fuck( int rt , int l , int r , int p ) {
	if( l == r ) { if( cn[rt] == 1 ) mx[rt] = lt[rt] = 0; else -- cn[rt]; return; }
	int m = l + r >> 1;
	if( p <= m ) fuck( rt << 1 , l , m , p );
	else fuck( rt << 1 | 1 , m + 1 , r , p );
	pus( rt );
}

int tv;
ll re;
void que( int rt , int l , int r , int L , int R ) {
	if( L <= l && r <= R ) { re += wkr( rt , tv ) , tv = max( tv , mx[rt] ); return; }
	int m = l + r >> 1;
	if( L <= m ) que( rt << 1 , l , m , L , R );
	if( R > m ) que( rt << 1 | 1 , m + 1 , r , L , R );
}

void ot( int rt ) {
	if( ch[rt][0] ) ot( ch[rt][0] );
	printf("%d ",val[rt]);
	if( ch[rt][1] ) ot( ch[rt][1] );
}

int g[MAXN][20];
int qmx( int l , int r ) {
	int t = 31 - __builtin_clz( r - l + 1 );
	return max( g[l][t] , g[r - ( 1 << t ) + 1][t] );
}

void solve() {
	cin >> n >> q;
	rep( i , 2 , n + 1 ) qwq[i] = i - 1;
	qwq[1] = -0x3f3f3f3f , qwq[n + 2] = 0x3f3f3f3f;
	bsplay( RT , 0 , 1 , n + 2 );
	rep( i , 1 , n ) scanf("%d",A + i) , g[i][0] = A[i];
	build( 1 , 1 , n );
	rep( k , 1 , 18 ) rep( i , 1 , n - ( 1 << k ) + 1 )
		g[i][k] = max( g[i][k - 1] , g[i + ( 1 << k - 1 )][k - 1] );
	rep( i , 1 , q ) {
		int o , l , r;
		scanf("%d%d%d",&o,&l,&r);
		if( o == 1 ) {
			if( l == r ) continue;
			
			int t = kth( RT , r + 1 );
			splay( t );
			ad( 1 , 1 , n , val[t] );
			ins( ch[RT][1] , val[t] );
			
			int v1 = val[kth( RT , l + 1 )] , v2 = val[kth( RT , l + 2 )];
			if( A[v1] < A[v2] ) fuck( 1 , 1 , n , v1 ) , era( RT , l + 1 );
			else fuck( 1 , 1 , n , v2 ) , era( RT , l + 2 );
		} else {
			int L = val[kth( RT , l + 1 )] , R = val[kth( RT , r + 1 )];
			tv = re = qmx( l , L );
			que( 1 , 1 , n , L , R );
			printf("%lld\n",re);
		}
//		ot( RT ); puts("");
	}
}

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

D2T3

这算是一个套路，由于询问的长度 $k$ 都是整数，我们可以考虑枚举小数部分的顺序。如果确定了小数部分的顺序，就可以通过一个简单的 $dp$ 来解决整数部分问题（这大概就是 Arcs On Circle）的做法。具体来说，我们假设 $x_1 < x_2 < \dots < x_n$ ，最后再除以在整数部分在 $[1,m]$ 时这种顺序关系出现的概率，我们设 $dp[i][j][k]$ 表示当前考虑到第 $i$ 个位置，$x_i,x_{i-1}$ 的整数部分分别是 $j,k$ 的概率，这个东西可以非常方便地转移。

然后会发现，其实我们需要考虑的只有 $i,i-1$ 的小数部分的相对排名，所以不需要枚举全排列，直接把相对排名记录进状态，也就是设 $dp[i][j][k][l][m]$ 表示前 $i$ 个数整数部分已经确定，$i,i-1$ 的整数部分分别是 $j,k$ 小数部分的相对排名是 $l,m$ 。转移就是枚举下个位置的整数部分和小数部分相对排名。直接转移复杂度 $O(n^4m^3)$ 。

如果加一个前缀和优化，可以做到 $O(n^3m^2)$ ，但是仍然无法通过此题。

我们观察一下加入了前缀和优化后的代码，转移部分大概长这样：

1
dp[c][j][o][v + ( o <= v )] = ( c - k - 1 >= j ? S[j][v][j] : S[j][v][c - k - 1] + s[j][v][c - k][o - 1] ) % P;

也就是说，如果有 $c-j \ge k+1$ ，这个 $dp$ 值就和 $c$ 无关了！因此 $j$ 只需要存到 $[c-k-1,c]$ 即可，也可以理解成当整数部分的差距超过了 $k$ ，显然转移就和当前之前位置无关了。因此复杂度可以优化到 $O(n^3km)$ ，不难发现 $kn > 2m$ 时，答案必然为 $0$ ，因此实际复杂度是 $O(n^2m^2)$ 。

写着挺恼火的

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 1006
//#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 , k , m , P;

int dp[151][151][51][51] , S[151][51][151] , s[151][51][151][51];

int Pow( int x , int a ) {
	int ret = 1;
	while( a ) {
		if( a & 1 ) ret = ret * 1ll * x % P;
		x = x * 1ll * x % P , a >>= 1;
	}
	return ret;
}
int iv[114515];

bool cmp( int a , int aa , int b , int bb ) {
	return a == b ? aa < bb : a < b;
}

void Inc( double& x , double c ) {
	x = x + c;
}
void Inc( int& x , int y ) {
	x = ( x + y > P ? x + y - P : x + y );
}
int Ad( int x , int y ) {
	return x + y < P ? x + y : x + y - P;
}

int pd[1006][1006] , iJ[114515] , J[114515];
int tmp[151][51];

void solve() {
	cin >> n >> k >> m >> P;
	if( n == 2 ) { puts("1"); return; }
	int tim = 0;
	int cur = 0 , las = 1;
	J[0] = iJ[0] = 1;
	rep( i , 1 , 114514 ) iv[i] = Pow( i , P - 2 ) , J[i] = J[i - 1] * 1ll * i % P , iJ[i] = iJ[i - 1] * 1ll * iv[i] % P;
	pd[0][0] = 1;
	rep( t , 1 , m ) {
		rep( i , 0 , n ) rep( j , 0 , i ) {
				Inc( pd[t][i] , pd[t - 1][j] * 1ll * iJ[i - j] % P );
			}
	}
	int tot = pd[m][n];
	tot = tot * 1ll * J[n] % P;
	rep( i , 1 , m ) rep( j , 1 , i ) {
			dp[i][j][2][1] = 1;
			if( i != j ) dp[i][j][1][2] = 1;
		}
	rep( i , 3 , n ) {
		rep( j , 1 , m ) rep( v , 1 , i - 1 ) {
			S[j][v][j - k - 2] = 0;
			if( j > k + 1 ) S[j][v][j - k - 2] = S[j - 1][v][j - k - 2];
			rep( t , max( j - k - 1 , 1 ) , j ) {
				S[j][v][t] = 0;
				rep( w , 1 , i - 1 ) {
					Inc( S[j][v][t] , dp[j][t][v][w] );
					s[j][v][t][w] = Ad( s[j][v][t][w - 1] , dp[j][t][v][w] );
				}
				Inc( S[j][v][t] , S[j][v][t - 1] );
			}
		}
		if( i == 3 ) mem( dp );
		rep( j , 1 , m ) rep( v , 1 , i ) rep( c , max( j , k + 1 ) , min( m , j + k + 1 ) ) rep( o , 1 , i )
			dp[c][j][o][v] = 0;
		rep( j , 1 , m ) rep( v , 1 , i - 1 ) rep( c , max( j , k + 1 ) , min( m , j + k + 1 ) ) rep( o , 1 , i ) if( c != j || o > v ) {
			dp[c][j][o][v + ( o <= v )] = ( Ad( c <= j ? S[c][v][c - k - 1] : S[j][v][c - k - 1] , c <= j - 1 ? s[c + 1][v][c - k][o - 1] : s[j][v][c - k][o - 1] ) ) % P;
		}
	}
//	cerr << S[6][1][2] << ' ' << S[6][1][1] << endl;
	int res = 0;
	rep( j , 1 , m ) rep( t , 1 , j ) rep( v , 1 , n ) rep( w , 1 , n ) {
					Inc( res , j - t > k ? dp[t + k + 1][t][v][w] : dp[j][t][v][w] );
				}
//	cout << res << endl;
	res = res * 1ll * Pow( tot , P - 2 ) % P;
	cout << res << endl;
}

signed main() {
//	freopen("a1_4.in","r",stdin);
//	freopen("ot","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
	solve();
}
文章作者: yijan
文章链接: https://yijan.co/pkusc-bu-fen-ti-jie/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog！