Yijan's Blog HomeArchives
4.26 模拟赛

A 钩子

我们按照 $d$ 来分层。如果当前区间长度为 $x$ ，如果它是偶数，挂一个后会变成 $\frac{x}{2}-1$ 和 $\frac{x}{2}$ ，否则会变成两个 $\frac{x-1}{2}$。就这样分层下去，最终得到的必然是 $\log$ 层。

明显每层会有一定数量的人来选，所以我们考虑对每层分别 $dp$ 。每一层明显只会有两种权值，并且我们可以知道每种权值的个数。我们考虑当前如果已经有 $i+j$ 个人选择了位置，其中有 $j$ 个人选的是奇数的块（也就是固定挂中间），$i$ 个人选了偶数的块（也就是可以选中间两个位置之一），这种情况出现的概率。通过这个 $dp$ 可以算出每个人选择奇数或者偶数的概率。注意这里选择偶数的权值应当是 $2$ ，奇数的权值是 $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
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
#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 P;
int n , m;
int A[MAXN] , inv[MAXN];

int dp[MAXN][MAXN] , t[2][MAXN];
int L[50][MAXN] , R[50][MAXN] , dis[50][MAXN] , us[MAXN];
int ans[MAXN][MAXN];
void solve( int dep , int S ) {
	int d = 0; // d on current floor
	rep( i , 1 , n ) if( !us[i] ) 
		L[dep][i] = L[dep][i - 1] + 1;
	per( i , n , 1 ) if( !us[i] )
		R[dep][i] = R[dep][i + 1] + 1;
	rep( i , 1 , n ) 
		dis[dep][i] = min( L[dep][i] , R[dep][i] ) , d = max( d , dis[dep][i] );
	if( d == 1 ) {
		int t = 0;
		rep( i , 1 , n ) if( !us[i] ) ++ t;
		rep( i , S + 1 , n ) rep( j , 1 , n ) if( !us[j] ) ans[i][j] = inv[t];
		return;
	}
	int e = 0 , o = 0;
	rep( i , 1 , n ) if( d == dis[dep][i] ) {
		us[i] = 1;
		if( dis[dep][i + 1] == d ) ++ e , ++ i;
		else ++ o;
	}
	rep( i , 0 , n ) rep( j , 0 , n ) dp[i][j] = 0;
	dp[0][0] = 1;
	rep( i , 0 , e ) rep( j , 0 , o ) {
		if( i < e ) { // ins an even seg.
			dp[i + 1][j] = ( dp[i + 1][j] + dp[i][j] * 1ll * inv[o - j + ( e - i ) * 2] % P * ( e - i << 1 ) % P ) % P;
			t[0][S + i + j + 1] = ( t[0][S + i + j + 1] + dp[i][j] * 1ll * inv[o - j + ( e - i ) * 2] % P * ( e - i << 1 ) % P ) % P;
		}
		if( j < o ) { // ins an odd seg.
			dp[i][j + 1] = ( dp[i][j + 1] + dp[i][j] * 1ll * inv[o - j + ( e - i ) * 2] % P * ( o - j ) % P ) % P;
			t[1][S + i + j + 1] = ( t[1][S + i + j + 1] + dp[i][j] * 1ll * inv[o - j + ( e - i ) * 2] % P * ( o - j ) % P ) % P;
		}
	}
	rep( i , S + 1 , S + e + o ) 
		rep( j , 1 , n ) if( dis[dep][j] == d ) {
			if( dis[dep][j + 1] == d ) 
				ans[i][j] = t[0][i] * 1ll * inv[e << 1] % P , ans[i][j + 1] = t[0][i] * 1ll * inv[e << 1] , ++ j;
			else 
				ans[i][j] = t[1][i] * 1ll * inv[o] % P;
		}
	solve( dep + 1 , S + e + o );
	int t = 0;
	rep( i , 1 , n - 1 ) if( dis[dep][i] == d && dis[dep][i + 1] == d ) {
		rep( j , S + 1 + e + o , n ) {
			rep( l , 0 , d - 1 ) {
				t = ( ans[j][i - l] + ans[j][i + l + 1] ) % P * 1ll * inv[2] % P;
				ans[j][i - l] = ans[j][i + l + 1] = t;
			}
		} 
	}
} 

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

void solve() {
//	freopen("ex_data1.in","r",stdin);
//	freopen("out.txt","w",stdout);
	cin >> n >> P;
	rep( i , 1 , n ) inv[i] = Pow( i , P - 2 );
	solve( 1 , 0 );
	rep( i , 1 , n ) { rep( j , 1 , n ) printf("%d ",ans[i][j]); puts(""); }
}

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

B 加减

先打表或者观察样例，发现奇数和偶数位置分别凸。于是考虑分治做，考虑枚举左边开头的是放奇数还是偶数，左右放了奇数还是偶数个，然后就可以用类似 “闵可夫斯基和” 的方法进行合并了。

可惜出题人不知道怎么想的八倍常数 $O(n\log n)$ 开 $5\times 10^5$ 还给 1s。。于是光荣 TLE 80 分不想调了。。

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
#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 , m;
int A[MAXN];

inline void gi(int &dx)
{
    dx = 0;
    int cc = getchar();
    bool nega = false;
    while (cc < '0' || cc > '9') { nega = (cc == '-' ? true : nega); cc = getchar(); }
    while (cc >= '0' && cc <= '9') { dx = (dx * 10 + cc - '0'); cc = getchar(); }
    if (nega) { dx = -dx; }
}

vector<ll> dp[2][MAXN << 2];

#define max( a , b ) ( (a) > (b) ? (a) : (b) )

const ll inf = 0x3f3f3f3f3f3f3f3f;

void solve( int rt , int L , int R ) {
	if( L == R ) {
		dp[0][rt] = { 0 , A[L] } , dp[1][rt] = { 0 , -A[L] };
		return;
	}
	int m = L + R >> 1;
	int ls = rt << 1 , rs = rt << 1 | 1 , len = R - L + 1;
	solve( ls , L , m ) , solve( rs , m + 1 , R );
	int s , a , b , ll = ( len - ( len >> 1 ) ) , rr = ( len >> 1 );
	rep( i , 0 , 1 ) {
		dp[i][rt].resize( R - L + 2 );
		dp[i][rt][0] = 0; 
		rep( j , 1 , R - L + 1 ) dp[i][rt][j] = -inf;
		rep( l , 0 , 1 ) rep( r , 0 , 1 ) {
			s = l ^ i;
			dp[i][rt][l + r] = max( dp[i][rt][l + r] , dp[i][ls][l] + dp[s][rs][r] );
			a = l , b = r;
			while( a + 2 <= ll || b + 2 <= rr ) {
				if( b + 2 > rr || ( a + 2 <= ll && dp[i][ls][a + 2] - dp[i][ls][a] >= dp[s][rs][b + 2] - dp[s][rs][b] ) )
					dp[i][rt][a + b + 2] = max( dp[i][rt][a + b + 2] , dp[i][ls][a + 2] + dp[s][rs][b] ) , a += 2;
				else
					dp[i][rt][a + b + 2] = max( dp[i][rt][a + b + 2] , dp[i][ls][a] + dp[s][rs][b + 2] ) , b += 2;
			}
		}
	}
}

void solve() {
	cin >> n;
	rep( i , 1 , n ) gi( A[i] );
	solve( 1 , 1 , n );
	rep( i , 1 , n ) printf("%lld ",dp[0][1][i]);
}

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

C 树高

见 luogu 梦断SCOI2017，我不会 TAT

文章作者: yijan
文章链接: https://yijan.co/426-mo-ni-sai/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog！