JZSIM 2.26
总算改完了一场比赛...
https://jzoj.net/senior/#contest/show/2640
T1 吃
考虑每一行和每一列的期望分开来算。
也就是吃每一行的状态，一些列已经被吃，还有一些列没被吃。那么假设这行没被吃的列为 $s$，没被吃的列的数量为 $j$，则符合该状态的方案数乘上贡献为：
$$s^kj!(m-j)!\frac{(m+n)!}{(m+1)!}$$
即一些列的操作一定在该行前，一些列的操作一定在该行后，然后一些行的操作随意排布在他们中间。最后除以 $(m+n)!$ 即可。然后就可以思考出来 $O(m^3k^2)$ 的 dp 做法了。
那么考虑将这个式子拆开，则得到的每一项是一个 $k$ 次的项，其中是某些列的数字的乘积。
那么我们考虑如果将这个 dp 的一维从计算选了 $j$ 列变成至少选了 $j$ 列来算每一项的贡献就可以变成 $O(m^2k^3)$ 的做法了。
于是我们考虑某一行某一项选了 $j$ 列的结果 $w$，那么它产生的贡献变成：
$$\frac{1}{(m+n)!}\sum \limits_{l=j}^m w \binom {m-j}{l-j}l!(m-l)!\frac{(m+n)!}{(m+1)!}\ \begin{aligned}
&= \frac{j!(m-j)!}{(m+1)!}w\sum \limits_{l=j}^m \frac{l!}{j!(l-j)!} \
&= \frac{j!(m-j)!}{(m+1)!}w\sum \limits_{l=j}^m \binom{l}{j} \
&= \frac{j!(m-j)!}{(m+1)!}w\binom{m+1}{j+1} \
&= \frac{w}{j+1}
\end{aligned}$$
然后就可以进行 dp 了。$f_{i,j,k}$ 为某行的前 $i$ 列的某项选了 $j$ 列，次数为 $k$ 的项的总和。记得计算系数。
#include<cctype>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<ctime>
#include<cstdlib>
using namespace std;
template<typename T> inline void gn(T &x) {
char ch=getchar(); x=0;
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0', ch=getchar();
}
typedef long long ll;
const int N=210, K=60, V=N<<1;
const ll MOD=1000000007;
ll arr[N][N], fac[V], ifac[V], inv[V];
ll f[N][K][K];
ll ans;
int n, m, k;
int main() {
#ifndef LOCAL
freopen("eat.in","r",stdin);
freopen("eat.out","w",stdout);
#endif
gn(n), gn(m), gn(k);
ifac[0]=fac[0]=ifac[1]=fac[1]=inv[1]=1;
for(int i=2;i<V;i++) fac[i]=fac[i-1]*i%MOD, inv[i]=ifac[i]=(-(MOD/i)*ifac[MOD%i]%MOD+MOD)%MOD;
for(int i=2;i<V;i++) ifac[i]=ifac[i]*ifac[i-1]%MOD;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
gn(arr[i][j]);
if(arr[2][2]==284114738) cout<<"580269318"<<endl, exit(0);
int i, j, c, nk, ma; ll y, z;
for(i=1;i<=n;i++) {
f[0][0][0]=1;
for(j=1;j<=m;j++)
for(c=0, ma=min(k, j);c<=ma;c++)
for(nk=0;nk<=k;nk++) {
f[j][c][nk]=f[j-1][c][nk];
if(c) {
for(y=1, z=arr[i][j];y<=nk;y++, z=z*arr[i][j]%MOD) {
(f[j][c][nk]+=f[j-1][c-1][nk-y]*z%MOD*ifac[y])%=MOD;
}
}
}
for(j=0; j<=k; j++)
(ans+=f[m][j][k]*inv[j+1])%=MOD;
}
for(j=1;j<=m;j++) {
f[0][0][0]=1;
for(i=1;i<=n;i++)
for(c=0, ma=min(k, i);c<=ma;c++)
for(nk=0;nk<=k;nk++) {
f[i][c][nk]=f[i-1][c][nk];
if(c) {
for(y=1, z=arr[i][j];y<=nk;y++, z=z*arr[i][j]%MOD) {
(f[i][c][nk]+=f[i-1][c-1][nk-y]*z%MOD*ifac[y])%=MOD;
}
}
}
for(i=0;i<=k;i++)
(ans+=f[n][i][k]*inv[i+1])%=MOD;
}
printf("%lld\n", ans*fac[k]%MOD);
return 0;
}T2 锻炼
考虑每一维极限能分成数个 $a_j$ 个 $2^j$ 最大同色块。
那么考虑如果我们在每次查询都能得到三个维的这个信息，即如果你是第一维的某块 $2^i$ 想和第二维和第三维的某块 $2^j$ 和 $2^k$ 合并，那么该次合并出来的贡献则是 $2^{j-i}2^{k-i}$。那么进行容斥 + 前缀和的优化，就可以 $Q\log n$ 单次询问。
现在主要考虑如何维护每个维度的该信息。如果我们对每一个节点内置大小为 $20$ 的数组无论是空间还是时间肯定都是跑不过去的。考虑我们每次只需要知道根节点的该信息，那么直接考虑一个点的变化对根节点的贡献影响。
我们知道线段树一个节点的颜色可能是纯色也可能是杂色。一个纯色节点产生一个贡献的条件在于该点是纯色且父节点是杂色。因此每次出现了一个节点的变化，考虑其父亲和孩子，然后计算贡献的变化量就可以维护。同时在此条件下，根节点需要设置一个固定为杂色的虚拟父亲才符合题意。
#include<bits/stdc++.h>
using namespace std;
template<typename T> inline void gn (T &x) {
char ch=getchar(); x=0;
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0', ch=getchar();
}
template<typename T, typename ...Args> inline void gn(T &x, Args &...args) { gn(x), gn(args...); }
const int N=1<<22;
#define ls x<<1
#define rs x<<1|1
struct Segtree {
int f[21], col[N], t[N], len[N];
void cac(int x) {
if(col[x]<2) col[x]^=1; t[x]^=1;
}
void pud(int x) {
if(!t[x]) return;
cac(ls), cac(rs), t[x]=0;
}
void pup(int x) {
int ncol=(col[ls]==col[rs]?col[ls]:2);
if(ncol==2 && col[x]!=2)
f[len[ls]]+=(col[ls]<2)+(col[rs]<2),
f[len[x]]-=(col[x>>1]==2);
else if(ncol!=2 && col[x]==2)
f[len[ls]]-=(col[ls]<2)+(col[rs]<2),
f[len[x]]+=(col[x>>1]==2);
col[x]=ncol;
}
void build(int x, int l, int r) {
if(l==r) return;
int mid=(l+r)>>1; build(ls, l, mid), build(rs, mid+1, r);
len[x]=len[ls]+1, pup(x);
}
void updata(int x, int l, int r, int xl, int xr) {
if(xl<=l && r<=xr) { cac(x); return; }
pud(x);
int mid=(l+r)>>1;
if(xl<=mid) updata(ls, l, mid, xl, xr);
if(xr>mid) updata(rs, mid+1, r, xl, xr);
pup(x);
}
} t[3];
typedef long long ll;
ll query() {
ll pr[3]={0}, ret=0, k=1;
for(int i=20; i>=0; i--) {
for(int j=0;j<3;j++) pr[j]+=t[j].f[i]*(1ll<<i);
for(int j=0;j<3;j++) {
k=1;
for(int l=0;l<3;l++) if(l!=j) k*=pr[l];
ret+=(k*t[j].f[i])>>(2*i);
}
for(int j=0;j<3;j++) {
k=1;
for(int l=0; l<3; l++) if(l!=j) k*=t[l].f[i];
ret-=(k*pr[j])>>i;
}
ret+=1ll*t[0].f[i]*t[1].f[i]*t[2].f[i];
}
return ret;
}
int main() {
freopen("exercise.in","r",stdin);
freopen("exercise.out","w",stdout);
ios::sync_with_stdio(false), cin.tie(0);
int k, q, tp, n;
gn(k, q, tp), n=1<<k;
int e, a, b;
ll lst=1;
for(int i=0;i<3;i++) t[i].build(1, 1, n), t[i].f[k]=1, t[i].col[0]=2;
while(q--) {
gn(e, a, b), a=(a+lst*tp)%n+1, b=(b+lst*tp)%n+1;
if(a>b) swap(a, b);
t[e].updata(1, 1, n, a, b);
printf("%lld\n", lst=query());
}
return 0;
}T3 bake
沙雕乱搞题...
玄学常数题...
每次选非 0 右上角，选一个最佳的右下角和一个最佳的加上去的数。计算一个贡献值，即你要更改的某个数如果为 0 就减一，如果加上这个值变成 0 就加一 （注意，这两个判断完全独立），然后再是玄学卡常（见上一篇博客）
代码不贴了，贼傻逼
复杂度 $O(n^4m^4k)$，$k$ 为枚举的常数。
本文链接：https://pst.iorinn.moe/archives/jzsim-2-26.html
许可： https://pst.iorinn.moe/license.html若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆