首页 > 代码库 > PT母函数

PT母函数

2024-07-14 06:20:07   227人阅读

B - 母函数入门1
Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u
Submit Status

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
 

这个题用母函数的思想，其实用一般的思想也可以，因为PT母函数就是建立在利用乘法遍历全部元素的基础上的。

用母函数推导的时候，设x的指数为价值，1+x为选或者不选价值为1的，1+x+x^2为不选，选一个，选两个，以此类推出这26个字母的情况，然后用母函数定理

N（Ex^m),N为连乘的意思，将连乘后的结果进行统计，把指数小于50的结果加起来即可。

用代码实现时，可以忽略母函数的概念，因为计算机的暴力解决了组合数据量大的问题，模拟即可，当然用母函数的思想角度更好理解，不断进行乘法运算（实际是加法，因为组合的加法体现在相乘，这里忽略底数，自然是对幂的加法），用两个循环来整合幂的结果，用两个数组来存更新和原来的结果。注意一开始数组中原来数组的值为1，这个用母函数解释很简单x^0 = 1;什么也不选，价值为0，方法为1；

#include<stdio.h>
#include<string.h>
int main()
{
	int n,v,a[51],b[51];
	scanf("%d",&n);
	while(n--){
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		a[0]=1;
        for(int i=1;i<=26;i++){
    	scanf("%d",&v);
    	for(int j=0;j<=50;j++)
    	for(int k=0;k<=v&&k*i+j<=50;k++){
	   	b[i*k+j]+=a[j];
	    }
    	for(int k=0;k<=50;k++){
	    	a[k]=b[k];
	    	b[k] = 0;
	    }
    }
    int s=0;
    for(int i=1;i<=50;i++){
    	s+=a[i];
    }
    printf("%d\n",s);
	}
}



PT母函数


联系
我们