[HDOJ6425] Rikka with Badminton (组合数学)

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：

链接：http://acm.hdu.edu.cn/showproblem.php?pid=6425

$n$个人去打羽毛球，其中$a$个人没球没拍，$b$个人只有拍，$c$个人只有球，$d$个人什么都有。现在规定只要有两个人有拍，一个人有球就能去打。问有多少种组合不能去打。

JLS给的解居然是个dp，惊了。

直接考虑有几种情况不能去打：球和拍都不够、球够拍不够、拍够球不够。

($a$个白嫖哥去不去都无所谓，因此他们对答案的整体贡献是$2^a$。)

球和拍都不够：分两种情况，完全没有拍和只有一个拍。第一种的贡献只有$a$出，第二种贡献从$a$和$b$里出。因此总体答案是$2^a+2^a×C_{b}^{1}$。

球够拍不够：这个贡献可以拆分成$a$和$c$、$a$和$b$、$a$和$b$和$d$里出。第一种（没有拍子）$c$类人随意去就可以（不能不去），贡献是$2^{a}×(2^{c}-1)$。第二种（只有一个拍子，$b$类人出拍子，$c$类人出球），贡献是$2^{a}×C_{b}^{1}×(2^c-1)$。第三种（只有一个拍子，$d$类人出拍子），贡献是$2^{a}×C_{d}^{1}×2^c$。

拍够球不够：只有$b$类人，且至少去$2$个，贡献是$2^a×C_{b}^{2}$。

全加起来就完事了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;

using LL = long long;
const LL mod = 998244353;
LL a, b, c, d;

LL mul(LL x, LL n) {
  LL ret = 1;
  while(n) {
    if(n & 1) ret = x * ret % mod;
    n >>= 1;
    x = x * x % mod;
  }
  return ret;
}

signed main() {
  // freopen("in", "r", stdin);
  int T;
  scanf("%d", &T);
  while(T--) {
    scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
    LL p1 = mul(2LL, a) * (b + 1) % mod;
    LL p2 = mul(2LL, a) * (mul(2LL, c) - 1) % mod;
       p2 += ((mul(2LL, a) * b % mod) * (mul(2LL, c) - 1)) % mod; p2 %= mod;
       p2 +=(( mul(2LL, a) * d % mod) * mul(2LL, c)) % mod; p2 %= mod;
    LL p3 = (mul(2LL, a) * (mul(2LL, b) - b - 1 + mod) % mod) % mod;
    printf("%lld\n", (((p1+p2)%mod)+p3)%mod);
  }
  return 0;
}