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;
}
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *