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$ 为枚举的常数。

网站*

加入讨论吧...