题目大意

有 $N$ 个 不可区分的 $K$ 面骰子。
对于每个 $i = 2, 3, \cdots , 2K$,求有多少种方案使得:任意两个点数不同 的骰子朝上的面之和不为 $i$。
答案对 $998244353$ 取模。
$2 \leq N \leq 2000,1 \leq K \leq 2000$。

题解

我们考虑对于 $i=x$ 怎么去计算答案 $ans$,考虑容斥,设 $cnt$ 表示$i+j=x$ 的无序对个数,那么答案就是
$ans = \sum_{i=0}^{cnt} (-1)^i \binom {cnt} {i} \binom {n-2i+k-1}{k-1}$
后面那个组合数是因为骰子是无序的,我们可以转化为求每种点数出现了多少次,插板一下得到的这个式子。

/*
 * sto Qingyu orz
 * 感谢真神sqy无私的教诲。膜时队者处处阿克,只因大师sqy在他背后。不膜大师者违背了真神的旨意,真神必将降下天谴,
 * 使其天天爆零
 * 我不由自主地膜拜真神sqy。
 * Author: RainAir
 * Time: 2019-10-16 10:11:35
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5000+5;
const int ha = 998244353;
int cnt[MAXN];
int n,k,fac[MAXN],inv[MAXN];

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

inline void prework(){
    fac[0] = 1;
    FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha;
    inv[MAXN-1] = qpow(fac[MAXN-1]);
    ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
}

inline int C(int n,int m){
    if(n < m) return 0;
    return 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha;
}

int main(){
    scanf("%d%d",&k,&n);
    prework();
    FOR(i,1,k) cnt[i+1]++,cnt[i+k+1]--;
    FOR(i,1,2*k) cnt[i] += cnt[i-1],cnt[i-1] = (cnt[i-1]+1)/2;
//    FOR(i,1,2*k) DEBUG(cnt[i]);
    FOR(i,2,k*2){
        int ans = 0;
        FOR(j,0,std::min(cnt[i],n/2)){
            (ans += 1ll*((j&1)?ha-1:1)*C(cnt[i],j)%ha*C(n-2*j+k-1,k-1)%ha)%=ha;
        }
        printf("%d\n",ans);
    }
    return 0;
}


版权属于:RainAir

本文链接:https://blog.aor.sd.cn/archives/888/

转载时须注明出处及本声明

Last modification:April 7th, 2020 at 10:14 pm
如果觉得我的文章对你有用,请随意赞赏