@atcoder - AGC035F@ Two Histograms

@description@

给定一个 N*M 的方格，我们通过以下步骤往里面填数：

（1）将所有方格填上 0。
（2）对于 i=1...N，选择一个 ki (0 <= ki <= M) ，给第 i 行的前 ki 个数加一。
（3）对于 j=1...M，选择一个 lj (0 <= lj <= N) ，给第 i 列的前 lj 个数加一。

最终每个方格填着 0, 1 或 2。求最后可以得到的不同填数方案总数 mod 998244353。

Constraints
1≤N,M≤5×10^5
N 与 M 都是整数。

Input
输入形式如下：
N M
Output
输出不同的填数方案 mod 998244353。

Sample Input 1
1 2
Sample Output 1
8

@solution@

见过的最水的AGC的F题，没有之一。

大胆考虑一个 dp：设 dp[i][j] 表示前 i 行，有 j 列的 l >= i。
转移时枚举有 p 列的 l = i，则为了不重复计数，第 i+1 行的 k 除了这 p 列都可以取。
为什么呢？如果不是这 p 列，要么在第 i+1 行之前就出现了断层，此时如果这个位置上为 1 则一定是行的贡献；否则要么延伸到 i+1 以下，此时这个位置就是 2，肯定也是惟一的。
如果是这 p 列，则不难验证一定会重复计数。

发现这个 dp 既过不了，也无法优化。
遇事不决，容斥解决。

我们发现假如重复计数，则第 i+1 行的 k 与第 j 列的 l 是一定的。
于是我们可以固定这一行一列会导致重复计数，同时去掉这一行一列。
当然还要加回两行两列，减去三行三列。。。
就可以得到我们的容斥式子啦：
\[ans = \sum_{i=0}^{min\{N, M\}}(-1)^i\C_{N}^{i}*C_{M}^{i}*i!*(N+1)^{M-i}*(M+1)^{N-i}\]

所以上面那个 dp 的作用？
便于感性理解这个容斥的正确性。

@accepted code@

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 20000000;
const int MOD = 998244353;
int pow_mod(int b, int p) {
    int ret = 1;
    while( p ) {
        if( p & 1 ) ret = 1LL*ret*b%MOD;
        b = 1LL*b*b%MOD;
        p >>= 1;
    }
    return ret;
}
int fct[MAXN + 5], ifct[MAXN + 5];
void init() {
    fct[0] = 1;
    for(int i=1;i<=MAXN;i++)
        fct[i] = 1LL*fct[i-1]*i%MOD;
    ifct[MAXN] = pow_mod(fct[MAXN], MOD-2);
    for(int i=MAXN-1;i>=0;i--)
        ifct[i] = 1LL*ifct[i+1]*(i+1)%MOD;
}
int pw1[MAXN + 5], pw2[MAXN + 5];
int main() {
    init(); int N, M;
    scanf("%d%d", &N, &M);
    int ans = 0;
    pw1[0] = pw2[0] = 1;
    for(int i=1;i<=max(N, M);i++)
        pw1[i] = 1LL*pw1[i-1]*(N+1)%MOD, pw2[i] = 1LL*pw2[i-1]*(M+1)%MOD;
    for(int i=0,f=1;i<=min(N,M);i++,f=1LL*f*(MOD-1)%MOD) {
        int del = 1LL*ifct[N-i]*ifct[M-i]%MOD*ifct[i]%MOD;
        del = 1LL*del*pw1[M-i]%MOD*pw2[N-i]%MOD;
        ans = (ans + 1LL*f*del)%MOD;
    }
    printf("%lld\n", 1LL*ans*fct[N]%MOD*fct[M]%MOD);
}

@details@

我现在很后悔当时没有打这一场的 AGC。

独立切出来一道 AGC 的 F 题真的很爽www。

@atcoder - AGC035F@ Two Histograms

原文：https://www.cnblogs.com/Tiw-Air-OAO/p/11716759.html