找单词

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 9061 Accepted Submission(s): 6323

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

题目链接：HDU 2082

没错我就是这么无聊，强行用FFT去（负）优化这个母函数的相乘过程，实际上我调试了非长久，连nan都出现了233，关键在于控制次数界不要超过51即可，不然数组长度不够存。

代码：

#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define pb(x) push_back(x)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define caseT int _T;scanf("%d",&_T);for (int q=1; q<=_T; ++q)
typedef pair<int, int> pii;
typedef complex<double> cpx;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 26 * 20 + 5;
const double eps = 1e-6;
cpx x[N], y[N], pwm[30];
int R[N];

int rpos(int x, int n)//以n位二进制表示的x的反转之后的值
{
    int w = 0;
    for (int i = 0; (1 << i) < n; ++i)
        w = (w << 1) | ((x >> i) & 1);
    return w;
}
void init(cpx a[], int b, int e)
{
    for (int i = b; i < e; ++i)
        a[i] = cpx(0, 0);
}
cpx* FFT(cpx a[], int n, int f)
{
    cpx *A = new cpx[n];
    for (int i = 0; i < n; ++i)
        A[i] = a[R[i]];
    for (int i = 1; (1 << i) <= n; ++i)
    {
        int m  = (1 << i);
        cpx wm = pwm[i];
        if (f == -1)
            wm.imag(-wm.imag());
        for (int k = 0; k < n; k += m)
        {
            cpx w(1, 0);
            for (int j = 0; j < (m >> 1); ++j)
            {
                cpx t = w * A[k + j + (m >> 1)], u = A[k + j];
                A[k + j] = u + t;
                A[k + j + (m >> 1)] = u - t;
                w *= wm;
            }
        }
    }
    if (!~f)
        for (int i = 0; i < n; ++i)
            A[i].real(A[i].real() / n);
    return A;
}
int main(void)
{
    int i, j;
    for (i = 0; (1 << i) < N; ++i)
        pwm[i] = cpx(cos(2 * PI / (1 << i)), sin(2 * PI / (1 << i)));
    caseT
    {
        int la = 1, lb = 0, lc = 0, n, first = 1;
        init(x, 0, N);
        cpx * dx, *dy;
        for (i = 1; i <= 26; ++i)
        {
            int c;
            scanf("%d", &c);
            if (!c)
                continue;
            if (first)
            {
                x[0].real(1.0);
                for (j = 0; j <= c; ++j)
                {
                    if (j * i > 50)
                        break;
                    x[j * i].real(1);
                }
                la = min(51, c * i + 1);
                first = 0;
            }
            else
            {
                lb = min(51, i * c + 1), lc = lb + la - 1;
                n = 1;
                while (n < lc)
                    n <<= 1;
                for (j = 0; j < n; ++j)
                    R[j] = rpos(j, n);
                init(y, 0, N);
                init(x, la, N);
                for (j = 0; j <= c; ++j)
                {
                    if (j * i > 50)
                        break;
                    y[j * i].real(1);
                }
                dx = FFT(x, n, 1);
                dy = FFT(y, n, 1);
                for (j = 0; j < n; ++j)
                    dx[j] *= dy[j];
                dy = FFT(dx, n, -1);
                for (j = 0; j < lc; ++j)
                    x[j] = cpx(int(dy[j].real() + 0.5), 0);
                la = min(51, lc);
                init(x, la, N);
            }
        }
        int ans = 0;
        for (i = 1; i <= 50; ++i)
            ans += int(x[i].real() + 0.5);
        printf("%d\n", ans);
    }
    return 0;
}

Blackops

HDU 2082 找单词（FFT优化母函数乘法）

找单词