问题描述

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

问题分析

Problem analyse

经典的母函数题目

algorithm analyse

如果有一组序列:a₀, a₁, a₂, a₃, ...，存在一个多项式G(X) = a₀ + a₁X + a₂X² + a₃X³ + ...，则称G(X)是序列 a₀, a₁, a₂, a₃, ... 的母函数。譬如：

(1 + x)n = C⁰_n + C¹_nX¹ + ... + Cⁿ_nXⁿ

则 (1 + x)n是序列C⁰_n， C¹_n, ..., Cⁿ_n的母函数。

用母函数解题，就是用多项式的指数来代表某一属性(质量、分数、体积...)，前面的系数为它的种数。譬如：有1克、2克、3克、4克的砝码各一枚，能称出哪几种重量？各有几种可能方案？

按上面讲的，我们把X的指数设为质量。所以：

1. 1克能表示0克和1克两种，所有是:X⁰ + X¹ = 1 + X¹
2. 2克能表示0克和2克两种，所有是:X⁰ + X² = 1 + X²
3. 3克能表示0克和3克两种，所有是:X⁰ + X³ = 1 + X³
4. 4克能表示0克和4克两种，所有是:X⁰ + X⁴ = 1 + X⁴

几种砝码的组合可以称重的情况，可以用以上几个函数的乘积表示：

(1 + X¹)(1 + X²)(1 + X³)(1 + X⁴) = 1 + X¹ + X² + 2X³ + 2X⁴ + 2X⁵ + 2X⁶ + 2X⁷ + X⁸ + X⁹ + X¹⁰

所以，能称出0->10克的重量。3->7都有两种表示方法，其他的都只有1种。因此，本题就是求1->50的母函数的系数和。

算法实现

多项式的表示方法很多，本题不是稀疏的多项式，所有直接用一个一维数组就可以了。

参考源码