agc055F - Creative Splitting 题解

又是 atc 风格 DP/tuu/tuu/tuu/tuu/tuu/tuu/tuu/tuu/tuu/tuu/tuu/tuu/tuu/tuu/tuu/tuu/tuu/tuu

首先容易想到对一个序列 \(p_{1\sim nk}\) 搞一个贪心的判断方法。

我一开始想的是：维护 \(n\) 个序列，初始为空。从左往右考虑 \(p_i\)，加入其能加入的最短序列，如果不存在就寄了。按照这个方法推出了很奇怪的结论，并不可做。事实上它是假的。

事实上，考虑其证明（肯定是调整法）：设 \(p_i\) 可以加入一个长度为 \(x,y\) 的序列且 \(x。如果加入 \(y\) 能成立，那么试图构造基于此的加入 \(x\) 的方案。一个显然的想法是交换 \(x\) 序列的位置 \(x+1\) 和 \(y\) 序列的位置 \(y+1\)，但是交换完后 \(y\) 序列的下标不一定递增，这种方法就萎掉了。

正确的贪心是维护 \(n\) 个满的序列，从后往前考虑，删除其能作为末尾的最短序列的末尾，不存在就寄。这是可以证明的：考虑把 \(y\) 序列的位置 \(y\) 放到 \(x\) 序列的位置 \(x\)。归纳地假设删完这一步后按照该贪心策略有解，那么存在方案使 \(x\) 序列的位置 \(x\) 下标小于 \(y\) 序列的位置 \(x\)，那么就可以把整个 \(x\) 序列与 \(y\) 序列的前 \(x-1\) 个元素交换，\(y\) 序列后面的顺延。

从前往后的一个反例是 \(p=[1,1,3,1,1,1],n=2,k=3\)。感性地理解是，从前往后贪心虽然预先选择尽可能小（也就是限制尽可能紧）的机会，但可能让之后的元素没有及时达到大的机会；而从后往前就没有这个问题。

如果按这个贪心的过程 DP，需要记录当前所有序列长度的可重集的信息，这至少是指数级的，寄。

考虑分析这个贪心的过程。设 \(c_i\) 表示当前长度为 \(i\) 的序列个数（这显然能描述该可重集）。那么加入 \(x\)，会令可重集中的哪个数自减呢？是最小的 \(y\geq x\) 满足 \(c_y>0\)。这个 lower_bound 的事情就很影响我们处理。

设 \(c_x\) 非零的 \(x\) 的上一个 \(c_y\) 非零的 \(y\) 为 \(prv_x\)。那么 \((prv_x,x]\) 这一段的影响是一样的。还有什么东西使得 \((prv_x,x]\) 这一段一样？后缀和。我们对 \(c\) 的后缀和数组 \(C\) 进行考察：加入 \(x\)，令 \(C_y=C_x\) 的最后一个 \(y\) 的 \(c_y\) 自减、\(c_{y-1}\) 自加——这对应到 \(C\) 上，就相当于 \(C_y\) 自减。而 \(C\) 始终是单调减的，所以我们可以只记录其可重集，那么令 \(C_y\) 自减就和令 \(C_x\) 自减等效！

这下就好办了，可以把贪心策略转化成相对简单的过程：维护一个序列 \(p\)，表示后缀和数组 \(C\) 的可重集按照执行过程的排列。那么每次加入 \(x\) 就是 --p[x]，如果此时 \(p_x\) 显然就寄了。\(p\) 初始为 \(k\) 个 \(n\)，最后要变成 \(k\) 个 \(0\)。这样一来，总方案数就很好算：就是个可重集排列数，为 \(\dfrac{(nk)!}{(n!)^k}\)。

考虑 \(ans_{pos,val}\)。接下来的过程就较为 trivial 了。显然考虑枚举从右往左执行完位置 \(pos+1\) 时的 \(p\)——任意满足 \(\sum p_i=pos\) 的 \(p\)。对一个 \(p\)，\(pos\) 前后及其自身三部分显然是割裂开的。\([pos+1,nk]\) 这一段的方案数显然是 \(\dfrac{(nk-pos)!}{\prod (n-p_i)!}\)，\(pos\) 处的方案是确定的，就是令 \(P_{val}\) 自减（\(P\) 为 \(p\) 从大到小排序后的结果），那么 \([1,pos-1]\) 这一段就是 \(\dfrac{(pos-1)!}{\prod(P_i-[i=val])!}\)。

还是枚举 \(P\) 比较好。一个 \(P\) 的答案就是 \(\dfrac{k!(nk-pos)!(pos-1)!P_{val}}{\prod cnt_i!\times \prod(n-P_i)!P_i!}\)，其中 \(cnt_i\) 为 \(P_j=i\) 的 \(j\) 的个数。接下来就是喜闻乐见的背包 DP 时间。对一个总和固定为 \(s\) 的长度为 \(m\) 的递增序列（设其值域为 \(v\)）DP 的方法主要有两种（这题中 \(s=n^2,m=k,v=n\)）：

\(dp_{i,sum,las}\)，一个一个元素考虑。转移需要枚举 \([las,v]\)，复杂度 \(\mathrm O\!\left(msv^2\right)\)，在本题中为 \(\mathrm O\!\left(n^4k\right)\)。
\(dp_{i,sum,cnt}\)，一个一个值考虑。转移需要枚举当前 \(i\) 的数量，复杂度为 \(\mathrm O\!\left(sm\prod\limits_{i=1}^v\min\!\left(m,\dfrac si\right)\right)\)。当 \(s=v\) 时可以被分析成 \(\mathrm O\!\left(s^2m\log s\right)\)，然而这题不行，就是 \(\mathrm O\!\left(vsm^2\right)\)，即 \(\mathrm O\!\left(n^3k^2\right)\)。当然，这题转移时需要知道 \(cnt\)，所以只能采用方法 2，笑死（

在本题中显然可以枚举 \(val\) 做一遍 DP，就能求出所有 \(pos\) 的答案，毕竟 \(pos\) 既 \(sum\)。复杂度就是 \(\mathrm O\!\left(n^3k^3\right)\)，可以通过 \(n,k\leq 30\) 的数据（用上快模）。

code

constexpr int N = 35, NN = 1010;

typedef unsigned long long ULL;
typedef __uint128_t LLL;
struct FastMod {
ULL b, m;
void init(ULL b){
this->b = b; m = ULL((LLL(1) << 64) / b);
}
ULL operator()(ULL a){
ULL q = (ULL)((LLL(m) *
a) >> 64);
ULL r = a - q *
b;
return r >= b ? r - b : r;
}
} M;
int mul(int x, int y){return M((ULL)x *
y);}

int iv[NN], fc[NN], ifc[NN];

int n, k;
int ans[NN][N];

void mian() {
    n = read(), k = read(), P = read();
    M.init(P);
    iv[1] = 1; REP(i, 2, NN - 1) iv[i] = (ll)iv[P % i] * (P - P / i) % P;
    fc[0] = ifc[0] = 1; REP(i, 1, NN - 1) fc[i] = (ll)fc[i - 1] * i % P, ifc[i] = (ll)ifc[i - 1] * iv[i] % P;
    REP(val, 1, k) {
        static int dp[N][NN][N];
        memset(dp, 0, sizeof(dp));
        dp[0][0][0] = 1;
        REP(i, 0, n) {
            auto f = dp[i], g = dp[i + 1];
            REP(sum, 0, n * k) REP(cnt, 0, k) if(f[sum][cnt]) {
                int base = mul(ifc[n - i], ifc[i]), prod = 1;
                REP(c, 0, k - cnt) {
                    if(sum + i * c > n * k) break;
                    int p = mul(prod, ifc[c]);
                    if(cnt < k - val + 1 && k - val + 1 <= cnt + c) p = mul(p, i);
                    addto(g[sum + i * c][cnt + c], mul(p, f[sum][cnt]));
                    prod = mul(prod, base);
                }
            }
        }
        REP(pos, 1, n * k) {
            int sum = dp[n + 1][pos][k];
            ans[pos][val] = (ll)fc[k] * fc[n * k - pos] % P * fc[pos - 1] % P * sum % P;
        }
    }
    REP(pos, 1, n * k) REP(val, 1, k) prt(ans[pos][val]), pc(" \n"[val == k]);
}

agc055F - Creative Splitting 题解

相关

标签