IFrog 1032 - A-B(容斥)
题意:
$n\le 500个球,需要把他们放到m\le 500个盒子里,盒子不同,可以为空$
$要求拥有最多球的盒子唯一,问方案数,答案模998244353$
分析:
$容斥原理套路题,枚举最多球的个数x,令事件A_i:=i号盒子\ge x的解的方法数$
$显然E_x=$
$所以容斥一波就好了,注意这里是有序的,所以容斥的时候要乘C(m-1, i)$
$因为选出1个盒子放最大的,最后插到m-1个盒子里有m种可能$
$对于n个球放进m个不同的盒子可以为空用隔板法来求,即calc(n, m)=C(n+m-1, m-1)$
$ans=m\sum_{x} E_x =m\sum_{x}\sum_{i=0}^{m-1} (-1)^i \cdot C(m-1, i) \cdot calc(m-1-x-i\times x, m-1)$
$阶乘预处理一下组合数,时间复杂度O(nm)$
$代码:$
//
// Created by TaoSama on 2016-09-22
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 500 + 10, INF = 0x3f3f3f3f, MOD = 998244353;
int n, m;
typedef long long LL;
LL quick(LL x, LL n) {
LL ret = 1;
for(; n; n >>= 1) {
if(n & 1) ret = ret * x % MOD;
x = x * x % MOD;
}
return ret;
}
LL fact[N], invf[N];
LL C(int n, int m) {
if(n < m) return 0;
return fact[n] * invf[m] % MOD * invf[n - m] % MOD;
}
LL calc(int n, int m) {
return C(n + m - 1, m - 1);
}
LL solve(int lft, int x, int m) {
LL ret = 0;
for(int i = 0; i <= m; ++i) {
if(lft - i * x < 0) continue;
if(i & 1) ret -= C(m, i) * calc(lft - i * x, m) % MOD;
else ret += C(m, i) * calc(lft - i * x, m) % MOD;
ret %= MOD;
}
return (ret + MOD) % MOD;
}
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
fact[0] = invf[0] = 1;
for(int i = 1; i < N; ++i) {
fact[i] = fact[i - 1] * i % MOD;
invf[i] = quick(fact[i], MOD - 2);
}
while(cin >> n >> m) {
if(m == 1) {cout << "1\n"; continue;}
LL ans = 0;
for(int i = n / m + 1; i <= n; ++i) {
ans += solve(n - i, i, m - 1);
}
ans = ans * m % MOD;
cout << ans << endl;
}
return 0;
}