codeforces 451E Devu and Flowers (指数型母函数)

Note: This article is available in Chinese only. 本文暂无英文版本。 View original

http://codeforces.com/problemset/problem/451/E 题意;有n个花坛，要选s支花，每个花坛有f[i]支花，同一个花坛的花颜色相同，不同花坛的花颜色不同，问说可以有多少种组合。思路：典型的母函数…然而s有点大，根据泰勒展开什么的…先转一下官方题解。

The number of ways to choose N items out of R groups where each item in a group is identical is equal to the number of integral solutions to _x_1 + _x_2 + _x_3…x__R = N, where 0 ≤ x__i ≤ L__i, where L__i is the number of items in i__th group. Number of integral solutions are coefficient of x__N in [Product of (1 + x + x * x + …x__L__i) over all $i$].
You need to find coefficient of x__s in (1 + x + _x_2 + _x_3 + + .._x__f_1) * * * (1 + x + _x_2 + _x_3 + + ..x__f__n).
Using sum of Geometric progression we can say that(1 + x + _x_2 + _x_3 + + .._x__f_1) = (1 - x(_f_1 + 1)) / (1 - x).
Substituting in the expression, we get (1 - x(_f_1 + 1)) / (1 - x) * * * (1 - x(f__n + 1)) / (1 - x).
= (1 - x(_f_1 + 1)) * .. * (1 - x(f__n + 1)) * (1 - x)( - n).
Now we can find x__s in (1 - x) - n easily. It is
.
You can have a look at following link. to understand it better.
So now as s is large, we can not afford to iterate over s.
But n is small, we notice that (1 - x(f_1 + 1)) * .. * (1 - x(f__n + 1)) can have at most 2_n terms.
So we will simply find all those terms, they can be very easily computed by maintaining a vector<pair<int, int> > containing pairs of coefficients and their corresponding powers. You can write a recursive function for doing this.
How to find
% p. As n + s - 1 is large and s is very small. You can use lucas’s theorem. If you understand lucas’s theorem, you can note that we simply have to compute
.
Complexity: O(n * 2_n_).

嗯。。。

我推到了这步：(1 - x(_f_1 + 1)) * .. * (1 - x(f__n + 1)) * (1 - x)( - n).

然后不知所措了。

一个不会的点是，一般意义的二项式定理不会，也就是指数为负数的。

然后后面那一串，由于n才20.所以直接暴力展开多项式我是能想到的。。。但是依然不知道怎么写。还有递归的求解方法。。。没有特别明白。

此外需要lucas定理求大组合数，以及预处理一个逆元（代码中的ny数组存的不仅仅是逆元）

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2016年03月02日 星期三 20时54分07秒
 4File Name :code/cf/problem/451E.cpp
 5************************************************ */
 6
 7#include <cstdio>
 8#include <cstring>
 9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const LL mod = 1E9+7;
34int n;
35LL s;
36LL f[35];
37
38int ny[35];
39LL ksm(LL a,LL b)   //快速幂
40{
41    LL res = 1;
42    while (b)
43    {
44	if (b&1) res = (res*a)%mod;
45	b>>=1;
46	a = (a*a)%mod;
47    }
48    return res;
49}
50
51void gny()  //ny数组存的不仅仅是逆元...
52{
53    LL val=1  ;
54    for ( LL i = 1 ; i <= 20 ; i++) val = val*i%mod;
55    ny[20]=ksm(val,mod-2);
56    for ( LL i = 19 ; i+1 ; i--) ny[i]=(ny[i+1]*(i+1))%mod;
57}
58
59
60LL cal( LL x,LL y)   //lucas 定理求组合数
61{
62    LL res  = 1LL;
63    for (LL  i = x ; i > x-y ;  i--)  res = (res*(i%mod))%mod;
64    res = (res*ny[y])%mod;
65    return res;
66}
67LL  solve(LL x,LL s)
68{
69    if (s<0) return 0;
70    if (x==n+1) return cal(s+n-1,n-1);
71    return (solve(x+1,s)-solve(x+1,s-f[x]-1)+mod)%mod;
72}
73int main()
74{
75	#ifndef  ONLINE_JUDGE
76	freopen("code/in.txt","r",stdin);
77  #endif
78
79	ios::sync_with_stdio(false);
80	gny();
81	cin>>n>>s;
82	for ( int i = 1 ; i <= n ; i++)
83	{
84	    cin>>f[i];
85	}
86
87	LL ans = solve(1,s)%mod;
88
89
90	cout<<ans<<endl;
91
92
93  #ifndef ONLINE_JUDGE
94  fclose(stdin);
95  #endif
96    return 0;
97}

Related