4.27 高斯消元 杂题

A (False) faces

题解在 这里

B Pachinko

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

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

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

复杂度 O(nm3)O(nm^3)

#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 的。

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

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

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

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

复杂度都是 O(nlog2n)O(n\log^2 n)

#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();
}
\