A.建设城市
考场暴搜+特判(20pts)
正解是子集反演但是我不能理解
还是容斥比较好理解
利用隔板法得到随意选择的方案数量为(C_{m-1}^{n-1})
答案是随便选-至少一个不满足的+至少两个不满足的-至少三个不满足的……
至少(i)个不满足的方案数为(C_n^i * C_{m-i*k-1} ^ {n-1})
(n>m)显然无解是(0),所以说数据相当于就是(1e7)的
然后直接出代码
City
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
inline int read(){
int x = 0, w = 1;
char ch = getchar();
for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') w = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
return x * w;
}
inline void write(register int x){
if(x < 0) x = ~x + 1, putchar('-');
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
const int mod = 998244353;
int n, m, k, minn;
int ans;
inline void dfs(register int cnt, register int tmp){//放好了cnt个城市,tmp队伍剩余数量
if(cnt == n){
if(tmp == 0) ans++;
return;
}
for(register int i = 1; i <= k; i++)
dfs(cnt + 1, tmp - i);
}
signed main(){
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
n = read(), m = read(), k = read();
if(n > m) return puts("0"), 0;
minn = min(m, k);
dfs(0, m);
printf("%d
", ans);
return 0;
}