HDU 1028 整数拆分 HDU 2082 找单词 母函数

生成函数（母函数）

母函数又称生成函数。定义是给出序列:a0,a1,a2,...ak,...an,

那么函数G(x)=a0+a1*x+a2*x²+....+ak*x^k +...+an* xⁿ  称为序列a0,a1,a2,.......ak,......的母函数(即生成函数)。

1. 问题 n=x1+x2+x3+...+xk有多少个非负整数解？这道题是学排列与组合的经典例题了。

把每组解的每个数都加1，就变成n+k=x1+x2+x3+...+xk的正整数解的个数了。

教材上或许会出现这么一个难听的名字叫“隔板法”：把n+k个东西排成一排，在n+k-1个空格中插入k-1个“隔板”。

答案我们总是知道的，就是C(n+k-1,k-1)。它就等于C(n+k-1,n)。

它关于n的生成函数是g(x)=1/(1-x)^k。

2. 这个公式非常有用，是把一个生成函数还原为数列的武器。而且还是核武器。1/(1-x)^n=1+C(n,1)x^1+C(n+1,2)x^2+C(n+2,3)x^3+...+C(n+k-1,k)x^k+...。

详情参考 百度百科  博客

找单词

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 9784    Accepted Submission(s): 6805

Problem Description

假设有x1个字母A， x2个字母B,..... x26个字母Z，同时假设字母A的价值为1，字母B的价值为2,..... 字母Z的价值为26。那么，对于给定的字母，可以找到多少价值<=50的单词呢？单词的价值就是组成一个单词的所有字母的价值之和，比如，单词ACM的价值是1+3+14=18，单词HDU的价值是8+4+21=33。(组成的单词与排列顺序无关，比如ACM与CMA认为是同一个单词）。

Input

输入首先是一个整数N，代表测试实例的个数。
然后包括N行数据，每行包括26个<=20的整数x1,x2,.....x26.

Output

对于每个测试实例，请输出能找到的总价值<=50的单词数,每个实例的输出占一行。

Sample Input

2

1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

9 2 6 2 10 2 2 5 6 1 0 2 7 0 2 2 7 5 10 6 10 2 10 6 1 9

Sample Output

7

379297

解析  相当于G(x)=(1++…) (1+++…)…(1++…)  每一个多项式 i 有xi+1项  然后多项式乘法就好了

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define fillchar(a, x) memset(a, x, sizeof(a))
#define huan printf("\n");
#define debug(a,b) cout<<a<<" "<<b<<" "<<endl;
using namespace std;
const int maxn= 1e2+;
const int inf = 0x3f3f3f3f;
typedef long long ll;
ll a[maxn],b[maxn];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        fillchar(a,);
        fillchar(b,);
        a[]=;
        for(int i=;i<=;i++)
        {
            int x;
            cin>>x;
            for(int j=;j<=;j++)
            {
                for(int k=;k<=x&&(j+i*k<=);k++)
                {
                    b[j+k*i]+=a[j];
                }

            }
            for(int j=;j<=;j++)
            {
                a[j]=b[j];
                b[j]=;
            }
        }
        ll ans=;
        for(int i=;i<=;i++)
        {
            ans+=a[i];
        }
        cout<<ans<<endl;
    }
}

Ignatius and the Princess III

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 25750    Accepted Submission(s): 17803

Problem Description

"Well, it seems the first problem is too easy. I will let you know how foolish you are later." feng5166 says.

"The second problem is, given an positive integer N, we define an equation like this:
  N=a[1]+a[2]+a[3]+...+a[m];
  a[i]>0,1<=m<=N;
My question is how many different equations you can find for a given N.
For example, assume N is 4, we can find:
  4 = 4;
  4 = 3 + 1;
  4 = 2 + 2;
  4 = 2 + 1 + 1;
  4 = 1 + 1 + 1 + 1;
so the result is 5 when N is 4. Note that "4 = 3 + 1" and "4 = 1 + 3" is the same in this problem. Now, you do it!"

Input

The input contains several test cases. Each test case contains a positive integer N(1<=N<=120) which is mentioned above. The input is terminated by the end of file.

Output

For each test case, you have to output a line contains an integer P which indicate the different equations you have found.

Sample Input

4

10

20

Sample Output

5

42

627

解析  这道题用母函数更裸一点 直接多项式乘法就好了  不过有一个递推的解法  记忆化一下就可以 减少很大计算量 或者dp

整数划分  还有一些其他的定理

递推法

根据n和m的关系，考虑下面几种情况：

（1）当n=1时，不论m的值为多少（m>0），只有一种划分，即{1}；

（2）当m=1时，不论 的值为多少（n>0），只有一种划分，即{1,1,....1,1,1}；

（3）当n=m时，根据划分中是否包含n，可以分为两种情况：

（a）划分中包含n的情况，只有一个，即{n}；

（b）划分中不包含n的情况，这时划分中最大的数字也一定比n小，即n的所有（n-1）划分；因此，f(n,n) = 1 + f(n, n - 1)。

（4）当n<=m时，由于划分中不可能出现负数，因此就相当于f(n,n)；

（5）当n>m时，根据划分中是否包含m，可以分为两种情况：

（a）划分中包含 的情况，即{m,{x1,x2,x3,...,xi}}，其中{x1,x2,x3,...,xi}的和为n-m，可能再次出现m，因此是（n-m）的m划分，因此这种划分个数为f(n-m,m；

（b）划分中不包含m的情况，则划分中所有值都比m小，即n的（m-1）划分，个数为f(n,m-1；因此，f(n,m)=f(n-m,m)+f(n,m-1) 。

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define fillchar(a, x) memset(a, x, sizeof(a))
#define huan printf("\n");
#define debug(a,b) cout<<a<<" "<<b<<" "<<endl;
using namespace std;
const int maxn= 1e2+;
const int inf = 0x3f3f3f3f;
typedef long long ll;
ll a[maxn],b[maxn];
int main()
{
    int n;
    while(cin>>n)
    {
        fillchar(a,);
        fillchar(b,);
        a[]=;
        for(int i=;i<=n;i++)  //枚举第i个多项式 每一项的系数都为1
        {
            for(int j=;j<=n;j++)  //保留x0----xn项
            {
                for(int k=;j+i*k<=n;k++) //枚举第i个多项式的每一项
                {
                    b[j+k*i]+=a[j];   //b数组保存中间值
                }

            }
            for(int j=;j<=n;j++)
            {
                a[j]=b[j];          //b数组传值给a
                b[j]=;
            }
        }
        cout<<a[n]<<endl;
    }
}
/*----------------------------------------------------------------------------------------*/
#include<bits/stdc++.h>
#define  ll long long
using namespace std;
//记忆化递归法求解整数划分
ll ans[][];
ll GetPartitionCount(int n, int m)
{
    if(ans[n][m]>)
        return ans[n][m];
    if (n ==  || m == )return ans[n][m]=;
    if (n < m)return ans[n][m]=(GetPartitionCount(n, n));
    if (n == m)return ans[n][m]=( + GetPartitionCount(n, n - ));
    else return ans[n][m]=(GetPartitionCount(n - m, m) + GetPartitionCount(n, m - ));
}

int main()
{
    int n,m;
    ll sum;
    while (scanf("%d",&n)==)
    {
        memset(ans,,sizeof(ans));
        m=n;
        sum = GetPartitionCount(n, m);
        printf("%lld\n", sum);
    }
    return ;
}