The solution of「[ARC102E] Stop. Otherwise...」

· · 题解

\textup{[ARC102E] Stop. Otherwise...}

\textup{Luogu} | \textup{Atcoder}

组合数学。

\textup{\textup{Solution}}

> 我们考虑逐个 $i = t$ 数出答案，并且注意到合法的要求为同一组内不包括 $a$ 和 $i - a$。 > > 则考虑将点分成三类：有产生非法的点对、$\frac{i}{2}$（不一定会产生）、和这两类的补集（可以随便使用）。 > > 不妨令前两种数量分别为 $A,B \in \{0, 1\}$。 $\textup{\textup{Step2}}$：这三类点的数量如何计算？ > 对于任意 $A$ 中点对 $\{x, y\}$，有 $1 \le x < y \le K$。 > > 此处表达式略去边界条件，通过计算 $A$ 的最大（标蓝部分）最小值（标红部分）可以得到 $A = \textcolor{#66CCFF}{\frac{i - 1}{2}} - \textcolor{#EE0000}{i + K + 1}$。 > > 得出 $B$ 的值直接判断当前 $i$ 奇偶性即可。 $\textup{\textup{Step3}}$：如何计算答案？ > 定义 $S = A + B$，表示受到约束的组数，$T = K - A - B$，表示当前自由点个数（注意与前文中补集不同，为包含关系）。 > > 此时我们要枚举使用哪些受限组，于是有 $C_{S}^{j}$ 的产生。 > > 那么 $N - j$ 的物品分配到剩下 $T$ 个类别，可以不放，利用插板法计算出 $C_{T + N − j − 1} ^ {N - j}$ 的贡献。 > > 合并得出式子为： > > $$ > \sum_{j = 0}^{\min(N, S)} C_{T + N − j − 1} ^ {N - j} \cdot C_{S}^{j} > $$ --- # $\textup{Code}

\textup{Submission Record}.

const int MAXN = 4005;
const int MOD = 998244353;
int N, K;
int fac[MAXN], inv[MAXN];
void pre(){//预处理阶乘逆元
    fac[0] = fac[1] = inv[0] = inv[1] = 1;
    for( int i = 2; i < MAXN; i ++ ){
        fac[i] = ( fac[i - 1] * i ) % MOD;
        inv[i] = ( MOD - MOD / i ) * inv[MOD % i] % MOD;
    }
    for( int i = 1; i < MAXN; i ++ ) inv[i] = inv[i - 1] * inv[i] % MOD;
}

int C( int n, int m ){//组合数计算
    if( m < 0 || m > n ) return 0;
    return fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}
signed main(){
    cin >> K >> N;
    pre();
    for( int i = 2; i <= 2 * K; i ++ ){
        int l = max( 1LL, i - K ), r = ( i - 1 ) / 2;//找到a的上界下界
        int a = ( l <= r ) ? ( r - l + 1 ) : 0, b = 0;
        if( i % 2 == 0 && i / 2 >= 1 && i / 2 <= K ) b = 1;

        int s = a + b, t = K - a - b;
        int ans = 0;
        for( int j = 0; j <= min( N, s ); j ++ ){
            ans += C( s, j ) % MOD * C( t + N - j - 1, N - j ) % MOD;
            ans %= MOD;
        }
        cout << ans << endl;
    }
    return 0;
}

\textup{Last}

审核管理员辛苦了，如果您有什么看不懂、我太弱了所以讲错了的地方，请您在评论区指出或找我，我会一定解答并且修改本题解。

如果您觉得本文写的还不错，那可以留个赞吗?

QWQ。

谢谢你看到这里~