Gym102341【杂题】

B Bulbasaur

给定 \(n\times k\) 的分层图,设 \(f(i,j)\) 表示第 \(i\) 层到第 \(j\) 层的点不交的路径组大小的最大值,求

\[\sum_{i=1}^{n-1}\sum_{j=2}^nf(i,j) \]

\(n\le 4\cdot 10^4,k\le 9\)。


将一个点拆成两个点之间连一条边。

考虑朴素的 FF 算法,假设当前要计算 \(\sum f(1,j)\),从第 \(1\) 层的每个点开始暴力增广,走到尽可能靠后的点。

\(i\) 增加的时候,把前一层的贡献减掉,然后从第 \(i\) 层开始增广,限制不能走到比第 \(i\) 层还前的点。容易发现我们只会从增广路的终点开始增广。总增广长度为 \(nk\),使用压位方法的增广一次是 \(O(k)\) 的。总时间复杂度 \(O(nk^2)\)甚至是关于输入规模线性的?

#include<bits/stdc++.h>
#define fi first
#define se second
#define MP make_pair
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int N = 80003, M = 9;
int n, m, k, sum, val[N], e[N][M], E[N][M], vis[N];
pii q[N*M], pre[N][M]; char str[M+2]; LL ans;
void work(int sx, int sy){
	vis[sx] = 1<<sy; int fr = 0, re = 0, mx = sx;
	q[re++] = MP(sx, sy); pii res(sx, sy);
	while(fr < re){
		int x = q[fr].fi, y = q[fr].se;
		if((x & 1) && x > res.fi) res = q[fr]; ++ fr;
		if(x < m){
			if(mx == x) vis[++mx] = 0;
			while(true){
				int tmp = e[x][y] & ~vis[x+1]; if(!tmp) break;
				int p = __builtin_ctz(tmp); vis[x+1] |= 1<<p;
				pre[x+1][p] = MP(x, y); q[re++] = MP(x+1, p);
			}
		} if(x > sx){
			while(true){
				int tmp = E[x-1][y] & ~vis[x-1]; if(!tmp) break;
				int p = __builtin_ctz(tmp); vis[x-1] |= 1<<p;
				pre[x-1][p] = MP(x, y); q[re++] = MP(x-1, p);
			}
		}
	} for(int i = sx>>1;i <= (res.fi>>1);++ sum, ++val[++i]);
	while(res != MP(sx, sy)){
		int x = pre[res.fi][res.se].fi, y = pre[res.fi][res.se].se;
		if(res.fi == x+1){e[x][y] ^= 1<<res.se; E[x][res.se] ^= 1<<y;}
		else {e[res.fi][res.se] ^= 1<<y; E[res.fi][y] ^= 1<<res.se;}
		res = MP(x, y);
	}
}
int main(){
	scanf("%d%d", &n, &k); m = (n<<1)-1;
	for(int i = 1;i < m;++ i)
		if(i & 1) for(int j = 0;j < k;++ j){
			scanf("%s", str);
			for(int l = 0;l < k;++ l)
				if(str[l] == '1') e[i][j] |= 1<<l;
		} else for(int j = 0;j < k;++ j) e[i][j] = 1<<j;
	for(int i = 1;i < n;++ i){
		for(int j = 0;j < k;++ j)
			work(max(1, i-1<<1), j);
		sum -= val[i]; ans += sum;
	} printf("%lld\n", ans);
}

C Cloyster

这是一道交互题

给定正整数 \(n\),交互器有 \(n\times n\) 的正整数矩阵 \(A\),保证数两两不同且对于所有非最大值的格子,周围 \(8\) 个格子中至少有一个比它大。

你至多可以询问 \(3n+210\) 次某个位置的值,要求求出最大值的位置。

\(n\le 2000\)。


又 tm 被教育了

询问一行,找到最大值 \(X\),询问 \(X\) 的周围,找到目前已知最大值的那一边走过去,如果还在同一行说明已经求出最大值。列同理。

然后就是标准的 KDT 型分治,操作次数 \(3n+12\log_2 n\)。

#include<bits/stdc++.h>
using namespace std;
const int N = 2003;
template<typename T>
void read(T &x){
	int ch = getchar(); x = 0;
	for(;ch < '0' || ch > '9';ch = getchar());
	for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
} template<typename T>
bool chmax(T &a, const T &b){if(a < b) return a = b, 1; return 0;}
int n, a[N][N], x0, y0, mx;
int qry(int x, int y){
	if(a[x][y]) return a[x][y];
	printf("? %d %d\n", x, y); fflush(stdout);
	read(a[x][y]); return a[x][y];
} void work(int u, int d, int l, int r){
	if(u == d && l == r){printf("! %d %d\n", u, l); exit(0);}
	if(d - u < r - l){
		int m = l+r>>1, p = u, v = qry(u, m);
		for(int i = u+1;i <= d;++ i)
			if(chmax(v, qry(i, m))) p = i;
		if(chmax(mx, v)){x0 = p; y0 = m;}
		for(int x = max(p-1, 1);x <= p+1 && x <= n;++ x){
			if(m > 1 && chmax(mx, qry(x, m-1))){x0 = x; y0 = m-1;}
			if(m < n && chmax(mx, qry(x, m+1))){x0 = x; y0 = m+1;}
		} if(y0 == m){printf("! %d %d\n", p, m); exit(0);}
		if(y0 < m) work(u, d, l, m-1); else work(u, d, m+1, r);
	} else {
		int m = u+d>>1, p = l, v = qry(m, l);
		for(int i = l+1;i <= r;++ i)
			if(chmax(v, qry(m, i))) p = i;
		if(chmax(mx, v)){x0 = m; y0 = p;}
		for(int y = max(p-1, 1);y <= p+1 && y <= n;++ y){
			if(m > 1 && chmax(mx, qry(m-1, y))){x0 = m-1; y0 = y;}
			if(m < n && chmax(mx, qry(m+1, y))){x0 = m+1; y0 = y;}
		} if(x0 == m){printf("! %d %d\n", m, p); exit(0);}
		if(x0 < m) work(u, m-1, l, r); else work(m+1, d, l, r);
	}
} int main(){read(n); work(1, n, 1, n);}

E Eevee

给定 \(k\) 个长为 \(n\) 的排列 \(p_i\),设 \(f(i,j)\) 表示满足所有长为 \(\ell=j-i+1\) 的子段都不全相等的、将 \(p_i,p_{i+1},\cdots,p_j\) 归并的方案数。求

\[\left(\sum_{1\le i<j\le k}f(i,j)\right)\bmod(10^9+7) \]

\(2\le k,n\le 300,p_i\) 在所有长为 \(n\) 的排列中独立均匀随机生成。


直接容斥,枚举 \([n]\) 的子集 \(S\),要求 \(S\) 在 \([l,r]\) 这一段的出现位置顺序相同,贡献系数是 \((-1)^{|S|}\),方案数是一堆可重集排列的乘法原理。

于是你获得了垃圾的指数级做法

考虑 dp,首先枚举区间左端点 \(l\),对于每个二元组 \((u,v)\) 记录 \(R(u,v)\) 表示使得 \([l,R(u,v))\) 的排列满足 \(u\) 比 \(v\) 先出现的最大值。

然后枚举 \(r:l+1\rightarrow n\),动态维护转移系数,每次做一遍 dp。

设 \(f_u\) 表示 \(S\) 中最后出现的元素是 \(u\),按照 \(p_l\) 中元素的出现顺序转移,枚举下一个出现的是 \(v\)。

当 \(r\ge R(u,v)\) 时没有贡献,所以对于每个 \(u\),将所有 \(v\) 按照 \(R(u,v)\) 降序排序,按照这个顺序转移就可以剪枝。

要先预处理一下 \(nk\) 以内的阶乘、阶乘逆元,最后注意把总方案数算上。

关于时间复杂度,第一部分是 \(O(n^2k)\),第二部分是 \(\sum_{l<r}\sum_{u,v}(R(u,v)-l)=O(nk^2)\)。

#include<bits/stdc++.h>
#define PB emplace_back 
using namespace std;
typedef long long LL;
const int N = 303, M = N*N, mod = 1e9 + 7;
template<typename T>
void read(T &x){
	int ch = getchar(); x = 0;
	for(;ch < '0' || ch > '9';ch = getchar());
	for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
} template<typename T>
bool chmax(T &a, const T &b){if(a < b) return a = b, 1; return 0;}
int ksm(int a, int b){
	int res = 1;
	for(;b;b >>= 1, a = (LL)a * a % mod)
		if(b & 1) res = (LL)res * a % mod;
	return res;
} void qmo(int &x){x += x >> 31 & mod;}
int k, n, a[N][N], pos[N][N], fac[M], inv[M], R[N][N], dp[N], coe[N][N], sc[N][N], f[N], g[N], sf[N], sg[N], ans;
vector<int> E[N];
void init(int m){
	fac[0] = 1;
	for(int i = 1;i <= m;++ i) fac[i] = (LL)fac[i-1] * i % mod;
	inv[m] = ksm(fac[m], mod-2);
	for(int i = m;i;-- i) inv[i-1] = (LL)inv[i] * i % mod;
} int C(int n, int m){
	if(m < 0 || n < m) return 0;
	return (LL)fac[n] * inv[m] % mod * inv[n-m] % mod;
}
int main(){
	read(k); read(n); init(n*k);
	for(int i = 0;i < k;++ i)
		for(int j = 0;j < n;++ j){
			read(a[i][j]);
			pos[i][--a[i][j]] = j;
		}
	for(int l = 0;l < k-1;++ l){
		for(int u = 0;u < n;++ u){
			E[u].resize(0); f[u] = g[u] = 1;
			sf[u] = pos[l][u]; sg[u] = n-pos[l][u]-1;
			for(int v = 0;v < n;++ v)
				if(pos[l][u] < pos[l][v] && pos[l+1][u] < pos[l+1][v]){
					chmax(R[u][v], l+2);
					while(R[u][v] < k && pos[R[u][v]][u] < pos[R[u][v]][v]) ++ R[u][v];
					E[u].PB(v); coe[u][v] = 1; sc[u][v] = pos[l][v]-pos[l][u]-1;
				}
			sort(E[u].begin(), E[u].end(), [&](int x, int y){return R[u][x] > R[u][y];});
		} for(int r = l+1;r < k;++ r){
			memset(dp, 0, sizeof dp);
			for(int _ = 0;_ < n;++ _){
				int u = a[l][_]; sf[u] += pos[r][u]; sg[u] += n-pos[r][u]-1;
				f[u] = (r-l+1ll) * C(sf[u], pos[r][u]) % mod * f[u] % mod;
				g[u] = (LL)C(sg[u], n-pos[r][u]-1) * g[u] % mod;
				qmo(dp[u] -= f[u]); ans = (ans + (LL)dp[u] * g[u]) % mod;
				for(int v : E[u]){
					if(r >= R[u][v]) break;
					sc[u][v] += pos[r][v]-pos[r][u]-1;
					coe[u][v] = (r-l+1ll) * C(sc[u][v], pos[r][v]-pos[r][u]-1) % mod * coe[u][v] % mod;
					qmo(dp[v] -= (LL)dp[u] * coe[u][v] % mod);
				}
			}
		}
	} for(int i = 2, pw = inv[n];i <= k;++ i){
		pw = (LL)pw * inv[n] % mod;
		ans = (ans + (k-i+1ll)*pw%mod*fac[i*n])%mod;
	} printf("%d\n", ans);
}

I Infernape

给定 \(n\) 个点的树,\(q\) 次询问 \(k\) 个圆 \(C(v,r)\),求被至少 \(k-1\) 个圆包含的点的个数。

\(n\le 10^5,\sum k\le 3\cdot 10^5\)。


计算圆的交集之前做过了,然后就成 sb 题了(

不同的是计算圆面积包含的点数需要用离线+点分治/点分树,时间复杂度 \(O((n+\sum k)\log n)\)。

L Lati@s

Nimber 积和式。

\(n\le 150,M_{i,j}\in[0,2^{64})\)。


Nimber 积和式跟行列式完全一样,所以算行列式就完事了(

Nimber 在 \([0,2^{2^n})\) 上构成有限域,\(x\) 的逆元即为 \(x^{2^{2^n}-2}\)。

复习一下 Nim 积:设 \(x=a\cdot 2^{2^{m-1}}+b,y=c\cdot 2^{2^{m-1}}+d\),其中 \(a,b,c,d\in[0,2^{2^{m-1}})\),则有

\[\begin{aligned} x\otimes y&=(a\otimes 2^{2^{m-1}}\oplus b)\otimes(c\otimes 2^{2^{m-1}}\oplus d) \\ &=a\otimes c\otimes 3\cdot 2^{2^{m-1}-1}\oplus (a\otimes d\oplus b\otimes c)\otimes 2^{2^{m-1}}\oplus b\otimes d \\ &=a\otimes c\otimes 2^{2^{m-1}-1}\oplus(a\otimes c\oplus a\otimes d\oplus b\otimes c)\cdot 2^{2^{m-1}}\oplus b\otimes d \\ &=a\otimes c\otimes 2^{2^{m-1}-1}\oplus((a\oplus b)\otimes(c\oplus d)\oplus b\otimes d)\cdot 2^{2^{m-1}}\oplus b\otimes d \end{aligned} \]

然后 \([0,2^{16})\) 内的原根是 \(258\),预处理离散对数之后可以直接算。\(64\) 位的 Nim 积计算大概是异或运算的 \(10\sim 20\) 倍常数,可以近似地看成 \(O(1)\)。

行列式直接高斯消元就完事了。时间复杂度 \(O(n^3)\)。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned u32;
typedef unsigned short u16;
typedef unsigned long long u64;
const u32 r = 258;
const int N = 1<<16;
template<typename T>
void read(T &x){
	int ch = getchar(); x = 0;
	for(;ch < '0' || ch > '9';ch = getchar());
	for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
} u16 pw[N], pos[N];
u16 mulp(u16 x, u16 y, u16 n = 16){
	if(x <= 1 || y <= 1) return x * y;
	u16 a = x>>n, b = x&(1<<n)-1, c = y>>n, d = y&(1<<n)-1, bd = mulp(b, d, n>>1);
	return ((mulp(a^b, c^d, n>>1)^bd)<<n)^bd^mulp(mulp(a, c, n>>1), 1<<n-1, n>>1);
} u16 mul16(u16 x, u16 y){
	if(x <= 1 || y <= 1) return x * y;
	int tmp = pos[x]+pos[y];
	return pw[tmp >= 65535 ? tmp - 65535 : tmp];
} u32 mul32(u32 x, u32 y){
	u16 a = x>>16, b = x&65535, c = y>>16, d = y&65535, bd = mul16(b, d);
	return ((mul16(a^b, c^d)^bd)<<16)^bd^mul16(mul16(a, c), 32768);
} u64 mul64(u64 x, u64 y){
	u32 a = x>>32, b = x&u32(-1), c = y>>32, d = y&u32(-1), bd = mul32(b, d);
	return (u64(mul32(a^b, c^d)^bd)<<32)^bd^mul32(mul32(a, c), 1u<<31);
} int n; u64 A[150][150], res = 1;
u64 ksm(u64 a, u64 b){
	u64 res = 1;
	while(b){
		if(b & 1) res = mul64(res, a);
		a = mul64(a, a); b >>= 1;
	} return res;
} u64 inv(u64 a){return ksm(a, u64(-2));}
int main(){
	for(u16 i = 0, x = 1;i < 65535;++ i, x = mulp(x, r)){
		pw[i] = x; pos[x] = i;
	} read(n);
	for(int i = 0;i < n;++ i)
		for(int j = 0;j < n;++ j)
			read(A[i][j]);
	for(int i = 0;i < n;++ i){
		int p = i; while(p < n && !A[p][i]) ++ p;
		if(p == n) return puts("Second"), 0;
		swap(A[i], A[p]);
		u64 tmp = inv(A[i][i]);
		res = mul64(res, A[i][i]);
		for(int j = i;j < n;++ j)
			A[i][j] = mul64(A[i][j], tmp);
		for(int j = i+1;j < n;++ j)
			for(int k = i+1;k < n;++ k)
				A[j][k] ^= mul64(A[j][i], A[i][k]); 
	} puts(res ? "First" : "Second");
}
上一篇:快速沃尔什变换(FWT)


下一篇:aspNet各种模块介绍