Yijan's Blog HomeArchives
5.25 训练

三道 Petrozavodsk 和 Open Cup

Different Summands Counng

链接

反套路题。介绍一下 $O(m^3\log n)$ 的卡常做法和 $O(m^3)$ 的标算。

我们考虑对于一个数，算出它恰好没有出现过的方案数，然后用总方案减去这个就是出现过的方案数量。前面这个可以方便地容斥成钦定，而如果是钦定且这题是有序拆分就可以用插板来安排剩下的数。

这个东西看起来比较难算。我们考虑第一层直接枚举，怎么计算后面这个东西。

我们倍增计算出所有的 $\binom{n-ak-1}{j}$ 。具体来说，我们先计算出

然后考虑怎么去计算前半部分。

由于一个组合恒等式，有

所以可以 $O(m^2)$ 转移出所有的 $F(j)$ 。复杂度 $O(m^3 \log n)$ ，转移时可以 NTT 做到 $O(m^2\log m\log n)$，写着很难受而且很不优秀。

标算做法非常反套路。具体来说，我们把 $a$ 看作 $x$ ，于是会发现 $\binom{n-kx-1}{m-k-1}$ 这个玩意是个 $O(m)$ 次项的多项式。所以说我们直接把多项式暴力算出来（这部分可以暴力或者 NTT），然后去求一个自然数幂和来算这个多项式的 $\sum F(a)$ 。这样复杂度仅仅是 $O(m^3)$ 或者 $O(m^2\log m)$ ，非常优秀。

第一种做法是当 $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
#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;
const int P = 998244353;
ll n;
int m;

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 J[MAXN] , iJ[MAXN] , iv[MAXN];
int C( int a , int b ) {
	if( b > a || b < 0 || a < 0 ) return 0;
	return J[a] * 1ll * iJ[b] % P * iJ[a - b] % P;
}
int CC( ll a , int b ) {
	if( a < b || b < 0 || a < 0 ) return 0;
	int re = 1;
	per( i , a % P , a % P - b + 1 )
		re = re * 1ll * ( i + P ) % P;
	re = re * 1ll * iJ[b] % P;
	return re;
}

void Inc( int& x , int y ) {
	x = ( x + y < P ? x + y : x + y - P );
}

int S[506] , i , gc[506];
int gs[506];
ll tot;
int solve( ll x ) {
	gs[0] = x % P;
	rep( k , 1 , m - i - 1 ) {
		gs[k] = Pow( ( x + 1 ) % P , k + 1 );
		rep( j , 0 , k - 1 )
			gs[k] = ( gs[k] + P - C( k + 1 , j ) * 1ll * gs[j] % P ) % P;
		gs[k] = ( gs[k] + P - 1 ) * 1ll * iv[k + 1] % P;
	}
	S[0] = 1;
	int sz = 0;
	rep( j , 0 , m - i - 2 ) {
		per( t , sz + 1 , 1 )
			S[t] = ( S[t] * 1ll * ( n % P + P - 1 - j ) + S[t - 1] * 1ll * ( P - i ) ) % P;
		S[0] = S[0] * 1ll * ( n % P + P - 1 - j ) % P;
		++ sz;
	}
	int re = 0;
	rep( t , 0 , m - i - 1 )
		re = ( re + S[t] * 1ll * gs[t] ) % P;
	re = re * 1ll * iJ[m - i - 1] % P;
	rep( j , 0 , m - i - 1 ) S[j] = 0;
	return re;
}

void solve() {
	cin >> n >> m;
	J[0] = iJ[0] = 1;
	rep( i , 1 , 506 ) J[i] = J[i - 1] * 1ll * i % P , iv[i] = Pow( i , P - 2 ) , iJ[i] = iJ[i - 1] * 1ll * iv[i] % P;
	int as = 0;
//	tot = n - 1;
//	solve( n - 1 );
//	rep( i , 0 , m ) cout << S[i] << ' '; puts("");
	for( i = 1 ; i < m ; ++ i ) {
		rep( c , 0 , m ) S[c] = 0;
		tot = ( n - m + i ) / i;
		int re = solve( tot );
		int w = C( m , i ) * 1ll * re % P;
		if( i & 1 ) as = ( as + w ) % P;
		else as = ( as + P - w ) % P;
	}
	if( n % m == 0 ) {
		if( m & 1 ) Inc( as , 1 );
		else Inc( as , P - 1 );
	}
	cout << as << endl;
}

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

B Process with Constant Sum

链接

我可能比较擅长这种题。

我们来手玩一下样例以及手捏的数据，会发现最后一段区间操作完后一定会成为一段 $0$ 再拼一段 $1$ 再拼一个 $x$ 。具体来说，我们可以这样操作：首先对每个数 $\bmod 2$ ，把所有 $\ge 2$ 的数用操作把 $x - x\bmod 2$ 送到结尾。然后找到倒数第二段 $1$ ，如果它和最后一段之间隔了奇数个 $0$ ，会发现你可以使用操作把最后两段互相削除掉。如果它和最后一段之间隔了偶数个$0$ ，会发现可以使用操作把这两段拼起来（这两部分需要仔细想想，有点细节）。而且会发现先拼 / 削任意两段是不会有区别的，也就是操作顺序其实不影响。

然后就是一些套路操作了，因为顺序不影响，我们把一个区间会得到的最终状态放到线段树上，在一个区间维护前面 $0$ 的长度，中间 $1$ 的长度，最后 $x$ 是多少。合并就是上面说的，需要想一想，细节可以参考代码。修改就是正常的线段树单点修改。

复杂度 $O(n\log 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
#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 , k;
int A[MAXN];

struct tcurts {
	int r , t , le;
	tcurts( ) : r( 0 ) , t( 0 ) , le( 0 ) {}
	tcurts( int r , int t , int le ) : r(r) , t(t) , le(le) {}
} T[MAXN << 2] ;

tcurts merge( tcurts ls , tcurts rs ) {
	if( !ls.le ) return rs;
	int tl = ls.t , tr = rs.t , sl = ls.r , sr = rs.r , cr = rs.le - rs.t - 1;
	tcurts as;
	as.le = ls.le + rs.le;
	as.r = sr + sl / 2 * 2;
	if( sl & 1 ) ++ tl; else ++ cr;
	if( cr & 1 ) {
		if( tl <= tr ) as.r += tl * 2 , as.t = tr - tl;
		else as.r += tr * 2 + 1 , as.t = tl - tr - 1;
	} else {
		as.t = tr + tl;
	}
	return as;
}

void pu( int rt ) {
	T[rt] = merge( T[rt << 1] , T[rt << 1 | 1] );
}
void build( int rt , int l , int r ) {
	if( l == r ) { T[rt] = tcurts( A[l] , 0 , 1 ); return; }
	int m = l + r >> 1;
	build( rt << 1 , l , m ) , build( rt << 1 | 1 , m + 1 , r );
	pu( rt );
}

void mdfy( int rt , int l , int r , int p , int c ) {
	if( l == r ) { T[rt] = tcurts( c , 0 , 1 ); return; }
	int m = l + r >> 1;
	if( p <= m ) mdfy( rt << 1 , l , m , p , c );
	else mdfy( rt << 1 | 1 , m + 1 , r , p , c );
	pu( rt );
}

tcurts que( int rt , int l , int r , int L , int R ) {
	if( L <= l && R >= r ) return T[rt];
	int m = l + r >> 1;
	tcurts as;
	if( L <= m ) as = que( rt << 1 , l , m , L , R );
	if( R > m ) as = merge( as , que( rt << 1 | 1 , m + 1 , r , L , R ) );
	return as;
}

void solve() {
	cin >> n;
	rep( i , 1 , n ) scanf("%d",A + i);
	build( 1 , 1 , n );
	cin >> q;
	rep( i , 1 , q ) {
		int op , l , r;
		scanf("%d%d%d",&op,&l,&r);
		if( op == 1 ) {
			mdfy( 1 , 1 , n , l , r );
		} else {
			tcurts pr = que( 1 , 1 , n , l , r );
			printf("%d\n",pr.le - pr.t - ( !!pr.r ));
		}
	}
}

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

C Interest

神仙题

链接

会发现这是以前 DLS round 的第三题，AUOJ 459。

我们考虑 $O(n^2)$ 暴力怎么做。可以看出选出两条边不相交路径可以直接看成一个网络流问题，也就是求出 $1$ 到点 $u$ 的大小为 $2$ 的最小费用流，且每条边容量为 $1$ ，然后就可以类似环游那个题真正的跑 $2$ 次单路增广。

首先第一次流其实可以非常简单的得出，也就是当我们建出最短路树后，第一次流一定是从 $1$ 在最短路树上流到 $u$ ，可以一次 dijkstra 实现。我们考虑能否通过一次 dijkstra 做完第二次流。但是在流了一次并反向后会得到负权边，所以我们可以对最开始的图做一次 primal dual ，也就是设到每个点最短路为 $d_u$ ，那么把 $u \to v$ 边权为 $w$ 的边的边权设置为 $w’ = w - d_v + d_u$ 。不难发现这样操作后最短路树上的边一定全部变成了 $0$ ，并且对于一条 $1 \to k$ 的路径，实际长度一定正好是 $d_k + dis$ 。并且此时，如果我们对 $1\to u$ 的路径全部反向，所有边的长度仍然是 $\ge 0$ 的！

于是我们考虑做一个 dijkstra 的过程，也就是我们设 $d_u’$ 为在 $1 \to u$ 的边被反向时，$1 \to u$ 的最短路。然后我们仍然考虑类 dijkstra 的转移，也就是每次拿出堆顶来更新其他点。考虑当前堆顶为 $u$ ，那么转移有两种。首先，这个点自己连出去的边肯定可以转移，对于一条非树边 $(u,v,w)$ ，一定可以用 $d_u + w$ 来更新 $d_v$ 。

然后考虑还可以用 $d_u$ 更新什么，会发现，其实 $1 \to u$ 的边被反向后等价于当前的根换成了 $u$ ，我们考虑对于一对其他的边 $(a,b,w)$ ，我们可以用 $d_u + w$ 来更新 $b$ 当且仅当 $a,b$ 不在 $u$ 的同一棵子树。因为如果把 $1 \to b$ 的路径反向其实等价于在这个图上把 $u \to b$ 的路径反向，然后如果 $a,b$ 不在同一个子树，那么把 $1 \to b$ 反向后仍然可以从 $u$ 以 $0$ 的代价走到 $a$ ，否则一定走不到。所以可以这样更新。

但是直接这样更新需要枚举 $u$ 的所有子树，这是不优秀的。但是考虑 $u$ 的某个子树中如果存在某个点 $v$ ，而 $d_v < d_u$ ，即 $v$ 已经作为堆顶过了，那么 $v$ 的子树一定是不用更新的。因为 $v$ 子树内部一定不能更新， $v$ 子树向外已经被 $v$ 更新过了。所以我们更新完一个点 $u$ 后其实可以直接把 $u$ 删去，也就是做一个类似点分的过程。

但是这种启发式点分也很容易被卡到 $O(n^2)$ 。我们考虑在更新一个点 $u$ 时，其实可以不用枚举这个点的最大的子树。我们可以对每个点存下这个点的所有出边即入边，然后枚举所有非最大的子树以及它们的出入边即可。我们可以证明这样每个点被枚举的次数是不超过 $O(\log n)$ 的，因为每次它作为轻子树出现，就说明这次点分之前它所在子树大小会翻倍。

然后还需要考虑最后一个问题，怎么判断哪个子树是最大的。考虑维护一个当前最大的子树 $mx$ 。考虑用 $O(\min (sz_u,sz_v))$ 的复杂度比大小。具体来说，可以倍增一个上界 $lim$ ，然后在两个子树分别 dfs $lim$ 次，如果其中某一个没 dfs 到这么多次即可直接比较，否则倍增 $lim$ 。可以发现这样实际上只会用 $O(\min(sz))$ 次。所以，每次枚举一个子树后如果它比当前子树大，那么我们去把当前最大子树给 dfs 一次枚举所有出入边，然后把最大的子树修改成当前子树，否则对当前子树做即可。

前面说明了，这样的复杂度是 $O(m\log 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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
//#pragma GCC optimize(3)
#define MAXN 200006
//#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;
const int P = 998244353;
int n , m;
vector<pair<int,ll> > G[MAXN] , F[MAXN];

ll dis[MAXN];
int vis[MAXN] , pre[MAXN];
priority_queue<pair<ll,int> > Q;
void dijk( ) {
	rep( i , 1 , n ) dis[i] = 1e18 , vis[i] = 0;
	Q.emplace( 0 , 1 );
	dis[1] = 0;
	while( !Q.empty() ) {
		int u = Q.top().se; Q.pop();
		if( vis[u] ) continue;
		vis[u] = 1;
		for( auto t : G[u] ) if( dis[t.fi] > dis[u] + t.se ) {
				int v = t.fi;
				dis[v] = dis[u] + t.se , Q.emplace( -dis[v] , v );
				pre[v] = u;
			}
	}
}

vi T[MAXN];
ll pr[MAXN];

int cnt = 0 , lim;
void dfs( int u , int f ) {
	++ cnt;
	for( int v : T[u] ) if( v != f && !vis[v] ) {
			if( cnt >= lim ) break;
			dfs( v , u );
		}
}

bool chk( int u , int v ) { // return siz[u] > siz[v]
	lim = 1;
	while( 233 ) {
		int a , b;
		dfs( u , 0 ) , a = cnt , cnt = 0;
		dfs( v , 0 ) , b = cnt , cnt = 0;
		if( a != lim || b != lim ) return a > b;
		lim <<= 1;
	}
}

int col[MAXN] , co;
void assign( int u , int f ) {
	col[u] = co;
	for( int v : T[u] ) if( v != f && !vis[v] )
			assign( v , u );
}

void wkr( int u , int f , ll D ) {
	for( auto t : G[u] ) {
		int v = t.fi;
		if( col[v] != col[u] && dis[v] > D + t.se )
			dis[v] = D + t.se , Q.emplace( -dis[v] , v );
	}
	for( auto t : F[u] ) {
		int v = t.fi;
		if( !vis[v] && col[v] != col[u] && dis[u] > D + t.se )
			dis[u] = D + t.se , Q.emplace( -dis[u] , u );
	}
	for( int v : T[u] ) if( v != f && !vis[v] ) wkr( v , u , D );
}

void solve() {
	cin >> n >> m;
	rep( i , 1 , m ) {
		int u , v , w;
		scanf("%d%d%d",&u,&v,&w);
		G[u].eb( v , w );
	}
	dijk( );
	rep( u , 1 , n ) {
		for( auto& t : G[u] ) {
			t.se -= dis[t.fi] - dis[u];
			F[t.fi].eb( u , t.se );
		}
		if( pre[u] ) T[pre[u]].pb( u ) , T[u].pb( pre[u] );
	}
	rep( i , 1 , n ) pr[i] = dis[i] , vis[i] = 0 , dis[i] = 1e18;
	dis[1] = 0;
	Q.emplace( 0 , 1 );
	co = 0;
	while( !Q.empty() ) {
		int u = Q.top().se; Q.pop();
		if( vis[u] ) continue;
		vis[u] = 1;
		for( auto t : G[u] ) {
			int v = t.fi;
			if( pre[v] == u || dis[v] <= dis[u] + t.se ) continue;
			dis[v] = dis[u] + t.se;
			Q.emplace( -dis[v] , v );
		}
		int hea = 0;
		for( int v : T[u] ) {
			if( vis[v] ) continue;
			if( !hea ) { hea = v; continue; }
			if( chk( v , hea ) )
				swap( hea , v );
			++ co , assign( v , u ) , wkr( v , u , dis[u] );
		}
	}
	rep( i , 2 , n ) printf("%lld\n",( dis[i] + pr[i] * 2 > 1e17 ? -1 : dis[i] + pr[i] * 2 ) );
	rep( i , 1 , n ) G[i].clear() , F[i].clear() , col[i] = 0 , T[i].clear();
}

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