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");
}