hdu1171&&P2000——母函数

hdu1171

题意：有 $n$ 种设施，每种有价值 $v_i$ 和数量 $m_i$，求一种方案使得分成价值尽可能相近的两组。（$n \leq 50, v_i \leq 50, m_i \leq 100$）

分析：

可以用背包做，这里讲母函数的做法。

直接用样例说明一下：

3
10 1
20 2
30 1

其母函数为 

$$(1+x^{10})(1+x^{20}+x^{40})(1+x^{30})$$

多项式展开后，倒着枚举 $i$ 从 $sum/2$ 到0，如果 $x^i$ 前的系数不为0说明能够组成 $i$，则答案为 $sum-i, i$.

#include<bits/stdc++.h>
using namespace std;

const int maxn =  50+5;
int c1[250000+10], c2[250000+10];    //c1存放前面项计算出来的结果，c2存放中间结果
int n;
int value[maxn], amount[maxn];

int main()
{
    while(scanf("%d", &n) == 1 && n >= 0)  //负数结束，不一定是-1。。。
    {
        int sum = 0;
        for(int i = 1;i <= n;i++)
        {
            scanf("%d%d", &value[i], &amount[i]);
            sum += value[i]*amount[i];
        }

        for(int i=0; i<=sum/2; ++i)  c1[i] = c2[i] = 0;
        for(int i = 0;i <= value[1]*amount[1]; i+= value[1])  c1[i] = 1;
        for(int i=2; i<=n; ++i)   // n个大括号
        {

            for(int j=0; j<=sum/2; ++j)   // 枚举c1中的项
                for(int k=0; k<=value[i]*amount[i] && j+k<=sum/2; k+=value[i])  // 枚举第i个大括号中的项
                {
                    c2[j+k] += c1[j];
                }
            for(int j=0; j<=sum/2; ++j)     //转移到c1
            {
                c1[j] = c2[j];
                c2[j] = 0;
            }
        }


        for(int i = sum/2;i >= 0;i--)
            if(c1[i] != 0)
            {
                printf("%d %d\n", sum-i, i);
                break;
            }
    }
    return 0;
}

View Code

p2000拯救世界

题目：给出10个限制，求组成n的方案数

分析：每个限制都可以写成一个母函数，由于每个限制是独立的，直接乘起来，结果为 $\displaystyle \frac{1}{(1-x)^5}$

有结论：$\displaystyle \frac{1}{(1-x)^k} = \sum_{i=0}^{\infty}C_{k+i-1}^i\cdot x^i$（用广义二项式定理证）

所以有 $\frac{1}{(1-x)^5}$ 的 $n$ 项的系数为 $C_n^4$.

//因为这题卡常，所以python过不了，然后用pypy就过了

n=int(input())
print((n+1)*(n+2)*(n+3)*(n+4)//24)

View Code

参考链接：

1. http://www.acmsearch.com/article/show/5079

2. http://www.wutianqi.com/blog/594.html

3. https://www.luogu.org/problemnew/solution/P2000