hdu6397(生成函数/容斥原理)

|

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=6397

题意

给定一个数集 $[0,n-1]$ ，连续从数集中可重复选取 $m$ 个数和为 $k$ 的方案数

题解

解法一(生成函数)：

这个东西看上去就是 $\displaystyle (\sum_{k=0}^{n-1}x^k)^m$ ，然后做个多项式快速幂，不过感觉会T。。

然后像个比较好的化简，可以发现

然后又是 $\displaystyle (1-x)^{-n}=\sum\binom{n+k-1}{k}x^k$

有了系数可以直接 $FFT$ 了，然而只需要一项所以可以 $O(n)$ 暴力求。。

解法二(容斥原理)：

把 $\le m$ 的限制拆出来，分别考虑有几个数大于 $m$ 就可以了。。

然后大于 $1$ 的和为 $k$ 的方案数直接隔板法得到 $\binom{n+k-1}{k-1}$




代码

解法一(生成函数)：

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/**
 *　　　　　　  　　┏┓　　 　┏┓
 * 　　　　　  　　┏┛┗━━━━━━━┛┗━━━┓
 * 　　　　　  　　┃　　　　　　　┃ 　
 * 　　　　　  　　┃　　　━　　 　┃
 * 　　　　　  　　┃　＞　　　＜　┃
 * 　　　　　  　　┃　　　　　　　┃
 * 　　　　　  　　┃...　⌒　... 　┃
 * 　　　　　　  　┃              ┃
 * 　　　　　　  　┗━┓          ┏━┛
 * 　　　　　　　　　┃          ┃　Code is far away from bug with the animal protecting　　　　　　　　　　
 * 　　　　　　　　　┃          ┃   神兽保佑,代码无bug
 * 　　　　　　　　　┃          ┃　　　　　　　　　　　
 * 　　　　　　　　　┃          ┃  　　　　　　
 * 　　　　　　　　　┃          ┃
 * 　　　　　　　　　┃          ┃　　　　　　　　　　　
 * 　　　　　　　　　┃          ┗━━━┓
 * 　　　　　　　　　┃              ┣┓
 * 　　　　　　　　　┃              ┏┛
 * 　　　　　　　　　┗┓┓┏━━━━━━━━┳┓┏┛
 * 　　　　　　　　　　┃┫┫       ┃┫┫
 * 　　　　　　　　　　┗┻┛       ┗┻┛
 */ 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<set>
#include<bitset>
#include<complex>
#include<cstdlib>
#include<assert.h>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define eps 1e-8
#define succ(x) (1<<x)
#define lowbit(x) (x&(-x))
#define mid (x+y>>1)
#define sqr(x) ((x)*(x))
#define NM 200005
#define nm 400005
const double pi=acos(-1);
const ll inf=998244353;
using namespace std;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f*x;
}
 


int n,m,k;
ll ans,inv[NM],invp[NM],p[NM];
inline ll binom(int n,int m){return n>=m?p[n]*invp[m]%inf*invp[n-m]%inf:0;}
inline ll f(int k){return binom(m+k-1,k);}

int main(){
    n=2e5;inv[1]=invp[0]=invp[1]=p[0]=p[1]=1;
    inc(i,2,n)inv[i]=inv[inf%i]*(inf-inf/i)%inf,invp[i]=invp[i-1]*inv[i]%inf,p[i]=p[i-1]*i%inf;
    int _=read();while(_--){
	n=read();m=read();k=read();
	ans=0;
	for(int i=0,j=0;i<=k;i+=n,j++)
	    if(j%2==0)ans+=binom(m,j)*f(k-i)%inf,ans%=inf;
	    else ans+=inf-binom(m,j)*f(k-i)%inf,ans%=inf;
	printf("%lld\n",ans);
    }
    return 0;
}

解法二(容斥原理)：

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/**
 *　　　　　　  　　┏┓　　 　┏┓
 * 　　　　　  　　┏┛┗━━━━━━━┛┗━━━┓
 * 　　　　　  　　┃　　　　　　　┃ 　
 * 　　　　　  　　┃　　　━　　 　┃
 * 　　　　　  　　┃　＞　　　＜　┃
 * 　　　　　  　　┃　　　　　　　┃
 * 　　　　　  　　┃...　⌒　... 　┃
 * 　　　　　　  　┃              ┃
 * 　　　　　　  　┗━┓          ┏━┛
 * 　　　　　　　　　┃          ┃　Code is far away from bug with the animal protecting　　　　　　　　　　
 * 　　　　　　　　　┃          ┃   神兽保佑,代码无bug
 * 　　　　　　　　　┃          ┃　　　　　　　　　　　
 * 　　　　　　　　　┃          ┃  　　　　　　
 * 　　　　　　　　　┃          ┃
 * 　　　　　　　　　┃          ┃　　　　　　　　　　　
 * 　　　　　　　　　┃          ┗━━━┓
 * 　　　　　　　　　┃              ┣┓
 * 　　　　　　　　　┃              ┏┛
 * 　　　　　　　　　┗┓┓┏━━━━━━━━┳┓┏┛
 * 　　　　　　　　　　┃┫┫       ┃┫┫
 * 　　　　　　　　　　┗┻┛       ┗┻┛
 */ 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<set>
#include<bitset>
#include<complex>
#include<assert.h>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define eps 1e-8
#define succ(x) (1ll<<x)
#define mid (x+y>>1)
#define lowbit(x) (x&(-x))
#define sqr(x) ((x)*(x))
#define NM 200005
#define nm 10000005
using namespace std;
const double pi=acos(-1);
const ll inf=998244353;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f*x;
}



int n,m,k;
ll ans,p[NM],invp[NM],inv[NM];
inline void reduce(ll&x){x+=x>>63&inf;}

int main(){
    n=2e5;p[0]=invp[0]=invp[1]=inv[1]=p[1]=1;
    inc(i,2,n)p[i]=p[i-1]*i%inf,inv[i]=inv[inf%i]*(inf-inf/i)%inf,invp[i]=invp[i-1]*inv[i]%inf;
    int _=read();while(_--){
	m=read();n=read();k=read();
	ans=0;
	for(int i=0;i<=n&&k>=0;i++,k-=m)if(i&1)
	    reduce(ans-=p[n]*invp[i]%inf*invp[n-i]%inf*p[k+n-1]%inf*invp[n-1]%inf*invp[k]%inf);
	else 
	    reduce(ans+=p[n]*invp[i]%inf*invp[n-i]%inf*p[k+n-1]%inf*invp[n-1]%inf*invp[k]%inf-inf);
	printf("%lld\n",ans);
    }
    return 0;
}