Yijan's Blog HomeArchives
4.27 高斯消元 杂题

A (False) faces

题解在 这里 。

B Pachinko

我们考虑设出 $s_{i,j}$ 表示经过 $s_{i,j}$ 的期望次数。那么可以对每个格子列出一个方程。由于每个 T 位置不会往外走，也就是说走到这个点就结束了，所以期望次数可以直接看成一个概率，最后除以会结束的总概率即可。但是直接进行高斯消元是 $O(n^3m^3)$ 的，无法接受。

然后会发现这个矩阵非常有性质。由于这个矩阵是 $n \times m,10^4 \times 20$ 的，而一个位置的方程仅在 $[i-m,i+m]$ 有值。因此高斯消元的时候，每一行只会影响到后面 $m$ 行。

但是还有一个问题，在进行交换的时候，显然只需要尝试把后 $m$ 行交换过来，交换过来后就可能影响 $[i+1,i+2m]$ 的系数了。因此需要对每个位置存储 $[i-m,i+2m]$ 的系数。记得在交换后需要改变这个方程可能有值的区间，由于 $i$ 前面都是 $0$ ，这个改变只可能是前面砍掉一些 $0$ 后面加上一些 $0$ 。

复杂度 $O(nm^3)$ 。

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
#include "cassert"
#include "numeric"
using namespace std;
#define MAXN 10036
//#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 X[] = { -1,1,0,0 };
const int Y[] = { 0,0,-1,1 };
int n , m;

char M[MAXN][22];
double p[5];
int gid( int x , int y ) {
	return ( x - 1 ) * m + y;
}

struct vec {
	int l , r;
	double A[62];
	double val;
	
	vec( ) : val(0) { mem( A ); }
	
	void ini( int L , int R ) { l = max( L , 1 ) , r = min( R , n * m ); }
	double& operator [] ( int x ) {
		assert( x >= l && x <= r );
		return A[x - l];
	}
	void gt( int L , int R ) {
		L = max( L , 1 ) , R = min( R , n * m );
		double a[62]; mem( a );
		rep( i , L , R ) if( i <= r ) a[i - L] = A[i - l];
		memcpy( A , a , sizeof a );
		l = L , r = R;
	}
	vec operator * ( double t ) {
		vec as; as.ini( l , r );
		rep( i , l , r ) as[i] = A[i - l] * t;
		as.val = val * t;
		return as;
	}
	void operator -= ( vec t ) {
		rep( i , max( t.l , l ) , min( t.r , r ) ) A[i - l] -= t[i];
		val -= t.val;
	}
} A[MAXN * 60] ;

bool iT[MAXN * 60];

void solve() {
	cin >> m >> n;
	rep( i , 0 , 3 ) {
		int qwq;
		scanf("%d",&qwq);
		p[i] = qwq * 1. / 100;
	}
	rep( i , 1 , n ) {
		scanf("%s",M[i] + 1);
	}
	int tt = 0;
	rep( j , 1 , m ) if( M[1][j] == '.' ) ++ tt;
	rep( i , 1 , n ) rep( j , 1 , m ) {
		int dx = gid( i , j );
		iT[dx] = M[i][j] == 'T';
		A[dx].ini( dx - m , dx + 2 * m );
		if( M[i][j] == 'X' ) {
			A[dx][dx] = 1 , A[dx].val = 0;
		} else {
			double c = 1;
			rep( d , 0 , 3 ) {
				int x = i + X[d] , y = j + Y[d];
				if( M[x][y] == 'X' || x < 1 || y < 1 || x > n || y > m ) 
					c -= p[d];
				else if( M[x][y] == '.' ) 
					A[dx][gid( x , y )] = -p[d ^ 1];
			}
			if( M[i][j] == 'T' ) c = 1;
			A[dx][dx] = c;
			A[dx].val = 0;
			if( i == 1 && M[i][j] == '.' ) A[dx].val += 1. / tt;
		} 
	}
	rep( i , 1 , n * m ) {
		if( !A[i][i] ) {
			rep( j , i + 1 , min( i + m , n * m ) ) if( A[j][i] != 0 ) {
				swap( A[j] , A[i] );
				A[j].gt( A[i].l , A[i].r );
			}
		}
		if( !A[i][i] ) continue;
		rep( j , i + 1 , min( i + m , n * m ) ) if( A[j][i] != 0 ) {
			double k = A[j][i] / A[i][i];
			A[j] -= A[i] * k;
		}
	}
	vector<double> as;
	per( i , n * m , 1 ) {
		rep( j , i + 1 , A[i].r ) if( A[i][j] ) {
			A[i].val -= A[j].val * A[i][j];
			A[i][j] = 0;
		}
		A[i].val /= A[i][i];
		if( iT[i] ) as.pb( A[i].val );
	}
	reverse( all( as ) );
	double s = accumulate( all( as ) , 0. );
	for( auto t : as ) {
		printf("%.7lf\n",t / s);
	}
}

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

C AUOJ1599 递归

原题是 ZR 的。

我们考虑对每个区间算出使得这个区间全为 $0$ 和全为 $1$ 的方案数。首先它能形成全为 $0$ 的方案数量显然是 $2^{n-f}$ 其中 $f$ 是自由元的数量。因为任意选取一些自由元，都可以通过基里面的东西得到。

然后如果通过给定的区间可以得到全为 $1$ ，那么形成全为 $1$ 的方案数量显然也是这个。还是因为选出一些自由元一定可以被基得到补集。

现在考虑怎么求出这个区间的线性基。直接求肯定是不行的。然后就有一个套路，如果每次加入的是一个区间为 $1$ 的数，那么就等价于从 $l$ 向 $r+1$ 连一条无向边。然后最后可以异或出 $a,b$ 全为 $1$ 当且仅当 $a,b+1$ 连通。于是往里面加入数就是一个并查集合并的过程，如果加入的时候已经连通了就说明这是一个自由元。

这题非常卡常，在线段树分治的时候不要提前挂好所有区间，这样预处理时间会非常长，一种优秀的处理方式是把区间的 vector 作为参数传进线段树分治的 dfs 中，然后每次分成两个部分丢到两个子节点。

复杂度都是 $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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
#include "ctime"
using namespace std;
#define MAXN 600006
//#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 , q;
int clo = 0;
int A[MAXN];

//vector<pii> T[MAXN << 2];
//void pus( int rt , int l , int r , int L , int R ) {
//	if( L <= l && R >= r ) return;
//	int m = l + r >> 1;
//	T[rt].eb( max( L , l ) , min( R , r ) );
//	if( L <= m ) pus( rt << 1 , l , m , L , R );
//	if( R > m ) pus( rt << 1 | 1 , m + 1 , r , L , R );
//}

int fa[MAXN];
int find( int x ) {
	return fa[x] == x ? x : fa[x] = find( fa[x] );
}

int res , p2[MAXN];

void que( int rt , int l , int r , vector<pii>& V ) {
	if( l == r ) return;
	rep( i , l , r + 1 ) fa[i] = i;
	int fre = q - V.size();
	vector<pii> sl , sr; 
	int m = l + r >> 1;
	for( auto t : V ) {
		if( t.fi <= m && !( t.fi <= l && t.se >= m ) ) sl.eb( t.fi , min( m , t.se ) );
		if( t.se > m && !( t.fi <= m + 1 && t.se >= r ) ) sr.eb( max( t.fi , m + 1 ) , t.se );
		int L = find( t.fi ) , R = find( t.se + 1 );
		if( L == R ) ++ fre;
		else fa[L] = R;
	}
	int tm = p2[fre];
	if( find( l ) == find( r + 1 ) ) tm = tm * 2 % P;
	res = ( res + p2[q] * 1ll + P - tm ) % P;
	que( rt << 1 , l , m , sl );
	que( rt << 1 | 1 , m + 1 , r , sr );
}

namespace IO {
const int MAXSIZE = 1 << 20;
char buf[MAXSIZE], *p1, *p2;
#define gc()                                                               \
  (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) \
       ? EOF                                                               \
       : *p1++)
inline int rd() {
  int x = 0, f = 1;
  char c = gc();
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = gc();
  }
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = gc();
  return x * f;
}
char pbuf[1 << 20], *pp = pbuf;
inline void push(const char &c) {
  if (pp - pbuf == 1 << 20) fwrite(pbuf, 1, 1 << 20, stdout), pp = pbuf;
  *pp++ = c;
}
inline void write(int x) {
  static int sta[35];
  int top = 0;
  do {
    sta[top++] = x % 10, x /= 10;
  } while (x);
  while (top) push(sta[--top] + '0');
  push( 10 );
}
}

void solve() {
	n = IO::rd() , q = IO::rd();
//	cin >> n >> q;
	vector<pii> T;
	rep( i , 1 , q ) {
		int l , r;
		l = IO::rd( ) , r = IO::rd();
//		cin >> l >> r;
		T.eb( l , r );
	}
	p2[0] = 1;
	rep( i , 1 , max( n , q ) ) p2[i] = p2[i - 1] * 2 % P;
	res = 0;
	que( 1 , 0 , n - 1 , T );
	cout << res << endl;
}

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