B Bulbasaur
给定 (n imes k) 的分层图，设 (f(i,j)) 表示第 (i) 层到第 (j) 层的点不交的路径组大小的最大值，求
[sum_{i=1}^{n-1}sum_{j=2}^nf(i,j)
]
(nle 4cdot 10^4,kle 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
", ans);
}
C Cloyster
这是一道交互题
给定正整数 (n)，交互器有 (n imes n) 的正整数矩阵 (A)，保证数两两不同且对于所有非最大值的格子，周围 (8) 个格子中至少有一个比它大。
你至多可以询问 (3n+210) 次某个位置的值，要求求出最大值的位置。
(nle 2000)。
又 tm 被教育了
询问一行，找到最大值 (X)，询问 (X) 的周围，找到目前已知最大值的那一边走过去，如果还在同一行说明已经求出最大值。列同理。
然后就是标准的 KDT 型分治，操作次数 (3n+12log_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
", 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
", 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
", 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
", 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_{1le i<jle k}f(i,j)
ight)mod(10^9+7)
]
(2le k,nle 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 ightarrow n)，动态维护转移系数，每次做一遍 dp。
设 (f_u) 表示 (S) 中最后出现的元素是 (u)，按照 (p_l) 中元素的出现顺序转移，枚举下一个出现的是 (v)。
当 (rge 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
", ans);
}
I Infernape
给定 (n) 个点的树，(q) 次询问 (k) 个圆 (C(v,r))，求被至少 (k-1) 个圆包含的点的个数。
(nle 10^5,sum kle 3cdot 10^5)。
计算圆的交集之前做过了，然后就成 sb 题了（
不同的是计算圆面积包含的点数需要用离线+点分治/点分树，时间复杂度 (O((n+sum k)log n))。
L Lati@s
Nimber 积和式。
(nle 150,M_{i,j}in[0,2^{64}))。
Nimber 积和式跟行列式完全一样，所以算行列式就完事了（
Nimber 在 ([0,2^{2^n})) 上构成有限域，(x) 的逆元即为 (x^{2^{2^n}-2})。
复习一下 Nim 积：设 (x=acdot 2^{2^{m-1}}+b,y=ccdot 2^{2^{m-1}}+d)，其中 (a,b,c,din[0,2^{2^{m-1}}))，则有
[egin{aligned}
xotimes y&=(aotimes 2^{2^{m-1}}oplus b)otimes(cotimes 2^{2^{m-1}}oplus d) \
&=aotimes cotimes 3cdot 2^{2^{m-1}-1}oplus (aotimes doplus botimes c)otimes 2^{2^{m-1}}oplus botimes d \
&=aotimes cotimes 2^{2^{m-1}-1}oplus(aotimes coplus aotimes doplus botimes c)cdot 2^{2^{m-1}}oplus botimes d \
&=aotimes cotimes 2^{2^{m-1}-1}oplus((aoplus b)otimes(coplus d)oplus botimes d)cdot 2^{2^{m-1}}oplus botimes d
end{aligned}
]
然后 ([0,2^{16})) 内的原根是 (258)，预处理离散对数之后可以直接算。(64) 位的 Nim 积计算大概是异或运算的 (10sim 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");
}