洛谷4104 [HEOI2014]平衡

Luogu

$\mathsf{\color{black}{l}\color{red}{ongge}}$ 怎么这么强啊 QAQ

分析

设 $dp_{i,j}$ 表示选了 $j$ 个数和为 $i$ 的方案数。通过一些思考可以得到转移

$$ dp_{i,j}\leftarrow dp_{i-j,j}+dp_{i-j,j-1} $$

注意当 $i>n$ 时需要多一个转移来去掉出现 $n+1$ 的情况

$$ dp_{i,j}\leftarrow dp_{i,j}-dp_{i-n-1,j-1} $$

考虑统计答案。枚举左边的和 $i$ 以及选的个数 $j$,则右边应选 $k-j$ 个,则将 $ans$ 加上 $dp_{i,j}\times dp_{i,k-j}$;注意中间的是可以选的,所以当 $j\neq k$ 时还要将 $ans$ 加上 $dp_{i,j}\times dp_{i,k-j-1}$。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=10000+10,K=10+10;

int n,k,mod;
int dp[N*K][K];

int main() {
    int T=read();
    while (T--) {
        n=read(),k=read(),mod=read();
        memset(dp,0,sizeof(dp)),dp[0][0]=1;
        for (re int i=1;i<=n*k;++i)
            for (re int j=1;j<=min(i,k);++j) {
                dp[i][j]=(dp[i-j][j]+dp[i-j][j-1])%mod;
                if (i>n) dp[i][j]=(dp[i][j]-dp[i-n-1][j-1]+mod)%mod;
            }
        int ans=0;
        for (re int i=0;i<=n*k;++i)
            for (re int j=0;j<=min(i,k);++j) {
                if (j!=k) ans=(ans+1ll*dp[i][j]*dp[i][k-j-1])%mod;
                ans=(ans+1ll*dp[i][j]*dp[i][k-j])%mod;
            }
        printf("%d\n",ans);
    }
    return 0;
}
最后修改:2019 年 11 月 08 日 10 : 24 PM

发表评论