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;
}

【题目】找单词母函数 HDU – 2082

于2018年4月22日2018年4月22日由XZYQvQ发布

1. 题目

2. 题解

XZYQvQ

0 条评论

发表回复取消回复

【题目】找单词 母函数 HDU – 2082

于2018年4月22日2018年4月22日由XZYQvQ发布

1. 题目

2. 题解

XZYQvQ

0 条评论

发表回复 取消回复

【题目】找单词母函数 HDU – 2082

发表回复取消回复