1. 题目

传送门=￣ω￣=

题目是少见的良心中文题面，就不写大意了。

2. 题解

母函数模板题耶 QvQ

设 $a_i$表示价值为 $i$的单词的个数。

构造母函数：

$$G(x)=a_1x+a_2x^2+a_3x^3+…$$

对于价值为 $i$个字符，设它有 $p$个，则对于它来说母函数为：

$$G_i(x)=1+x^i+x^{2i}+…+x^{pi}$$

对于用字符 $i$和字符 $j$能组合出来的情况的母函数我们可以想一下：

$G_i(x)$中的 $a[i]_px^p$和 $G_j(x)$中的 $a[j]_qx^q$可以合并得到新的母函数的 $(a[i]_pa[j]_q)x^{p+q}$（其中 $a[i]_j$表示 $G_i(x)$的 $j$次项的系数）

说的比较拗口。。。

打个比方吧，比如你有 $2$种方法得到价值 $5$，有 $3$种方法得到价值 $7$，那么你得到价值 $(5+7=12)$的方法数应当加上 $(2\times 3=6)$

不难发现就是：

$$G(x)=G_i(x)G_j(x)$$

即 $i,j$两种价值的字符组合出来的母函数 $G(x)$是 $G_i(x)$和 $G_j(x)$的卷积。

那么最终情况的母函数：

$$G(x)=G_1(x)G_2(x)G_3(x)…G_{26}(x)$$

求卷积可以用 FFT 把 $N^2$优化到 $Nlog_2N$，但是这题多项式长度只有 $51$，你 FFT 快不到哪里去，说不定常数大还慢些。。。

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

struct poly
{
    LL v[55];
    LL& operator [] (const int a) {return v[a];}
    void operator *= (poly& oth)
    {
        LL tmp[55]; memset(tmp, 0, sizeof(tmp));
        for (int i = 0; i <= 50; i += 1)
            for (int j = 0; i + j <= 50; j += 1)
                tmp[i + j] += v[i] * oth[j];
        memmove(v, tmp, sizeof(v));
    }
} sum, cur;

int T, x;

LL ans;

int main(int argc, char const* argv[])
{
    IN(T);
    while (T--)
    {
        memset(sum.v, 0, sizeof(sum.v)), sum[0] = 1;
        for (int i = 1; i <= 26; i += 1)
        {
            IN(x), memset(cur.v, 0, sizeof(cur.v));
            for (int p = 0, j = 0; p <= x && j <= 50; p += 1, j += i) cur[j] = 1;
            sum *= cur;
        }
        ans = 0; for (int i = 1; i <= 50; i += 1) ans += sum[i];
        printf("%lld\n", ans);
    }
    return 0;
}