首页 > ACM题库 > HDU-杭电 > HDU 4093-Xavier is Learning to Count[解题报告]HOJ
2015
04-16

HDU 4093-Xavier is Learning to Count[解题报告]HOJ

Xavier is Learning to Count

问题描述 :

  Xavier, a 9-year-old student, loves playing many kinds of puzzles. One of his favourites is the following:
  Xerier, his classmate, has made many cards. She writes down a single positive number on each of them. No numbers written on different cards are the same. After that she writes down an equation, whose right side is a single positive number chosen by her, and the left side is the sum of p integers:

  Then she asks Xavier put p cards on the corresponding Xi’s position to make this equation correct, with an additional condition that Xi should be ordered from smaller to bigger, i.e.
  Every time Xavier immediately comes up with many solutions. Now he wants to know how many solutions in total are there for any n given by Xerier.

输入:

  There are multiple test cases. The number of them is given in the beginning of the input. Then a series of input block comes one by one.
  For each test case:
  The first line contains two space-separated integers m and p (1<=p<=5). The second line contains m distinct positive integers – the numbers written on each of the cards. None of these integers exceeds 13000.
  There are about 120 test cases in total, but 90% of them are relatively small. More precisely, all numbers are less than or equal to 100 in 90% of the test cases.

输出:

  There are multiple test cases. The number of them is given in the beginning of the input. Then a series of input block comes one by one.
  For each test case:
  The first line contains two space-separated integers m and p (1<=p<=5). The second line contains m distinct positive integers – the numbers written on each of the cards. None of these integers exceeds 13000.
  There are about 120 test cases in total, but 90% of them are relatively small. More precisely, all numbers are less than or equal to 100 in 90% of the test cases.

样例输入:

3
3 3
1 2 3
5 4
1 3 5 6 7
10 3
1 2 3 4 5 6 7 8 9 10

样例输出:

Case #1:
6: 1

Case #2:
15: 1
16: 1
17: 1
19: 1
21: 1

Case #3:
6: 1
7: 1
8: 2
9: 3
10: 4
11: 5
12: 7
13: 8
14: 9
15: 10
16: 10
17: 10
18: 10
19: 9
20: 8
21: 7
22: 5
23: 4
24: 3
25: 2
26: 1
27: 1

#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<complex>
#define pi acos(-1.0)
using namespace std;
int n,k;
typedef complex<double> cp;
#define maxn 13100
int arr[maxn];
int fftlen;//FFT鏁扮粍闀垮害
#define PI pi
struct cparr
{
    cp v[65536];
    void operator=(const cparr &a)
    {
        memcpy(v, a.v, sizeof(cp) * fftlen);
    }
};
const cp I(0,1);
cparr f[6];//FFT鏁扮粍
cparr g[7];//缁撴灉FFT鏁扮粍
void fft(cp a[],int n, double theta )
{
    for(int m=n; m>=2; m>>=1)
    {
        int mh = m >> 1;
        for(int i=0; i<mh; i++)
        {
            cp w = exp(i*theta*I);
            for(int j=i; j<n; j+=m)
            {
                int k = j + mh;
                cp x = a[j] - a[k];
                a[j] += a[k];
                a[k] = w * x;
            }
        }
        theta *= 2;
    }
    int i = 0;
    for(int j=1; j<n-1; j++)
    {
        for(int k=n>>1; k>(i^=k); k>>=1);
        if(j<i)
            swap(a[i],a[j]);
    }
}

void mul(cparr &a,cparr &b)
{
    for(int i=0; i<fftlen; i++)
        a.v[i]*=b.v[i];
}
#define ndiv p
int p;
void gao()
{
    switch(k)
    {
    case 1:
        g[0] = f[1];
        p = 1;
        break;
    case 2:
        g[0] = f[2];
        g[1] = f[1];
        mul(g[1], f[1]);
        p = 2;
        break;
    case 3:
        g[0] = f[3];
        g[1] = f[2];
        mul(g[1],f[1]);
        g[2] = f[1];
        mul(g[2],f[1]);
        mul(g[2],f[1]);
        p = 3;
        break;
    case 4:
        g[0] = f[4];
        g[1] = f[3];
        mul(g[1],f[1]);
        g[2] = f[2];
        mul(g[2],f[2]);
        g[3] = f[2];
        mul(g[3],f[1]);
        mul(g[3],f[1]);
        g[4] = f[1];
        mul(g[4],f[1]);
        mul(g[4],g[4]);
        p = 5;
        break;
    case 5:
        g[0] = f[5];
        g[1] = f[4];
        mul(g[1], f[1]);
        g[2] = f[3];
        mul(g[2],f[2]);
        g[3] = f[3];
        mul(g[3],f[1]);
        mul(g[3],f[1]);
        g[4] = f[2];
        mul(g[4],f[2]);
        mul(g[4],f[1]);
        g[5] = f[2];
        mul(g[5],f[1]);
        mul(g[5],f[1]);
        mul(g[5],f[1]);
        g[6] = f[1];
        mul(g[6],f[1]);
        mul(g[6],g[6]);
        mul(g[6],f[1]);
        p = 7;
        break;
    }
}

const int factor[6]= {1,1,2,6,24,120};
const double ce[6][10] =
{
    {0.000000},
    {1.000000},
    {-1.000000, 1.000000},
    {2.000000, -3.000000, 1.000000},
    {-6.000000, 8.000000, 3.000000, -6.000000, 1.000000},
    {24.000000, -30.000000, -20.000000, 20.000000, 15.000000, -10.000000, 1.000000}
};
int main()
{
    int tcase;
    scanf("%d",&tcase);
    for(int ti=1; ti<=tcase; ti++)
    {
        scanf("%d%d",&n,&k);
        fftlen=1;
        for(int i=0; i<n; i++)
        {
            scanf("%d",&arr[i]);
            while(fftlen<=arr[i]*k)fftlen<<=1;
        }
        for(int i=1; i<=k; i++)
            for(int j=0; j<fftlen; j++)
                f[i].v[j]=0;
        //鍒濆鍖朏FT鏁扮粍
        for(int i=1; i<=k; i++)
        {
            for(int j=0; j<n; j++)
                f[i].v[arr[j]*i]+=1;
            fft(f[i].v,fftlen,2 * PI / fftlen);
        }
        gao();
        for(int i=0; i<ndiv; i++)
            fft(g[i].v,fftlen,-2 * PI / fftlen);
        printf("Case #%d:\n",ti);
        for(int i=0; i<fftlen; i++)
        {
            double tmp=0;
            for(int j=0; j<ndiv; j++)
                tmp+=g[j].v[i].real()*ce[k][j];
            tmp/=factor[k]*fftlen;
            if(tmp>0.5)
                printf("%d: %.0f\n",i,tmp);
        }
        printf("\n");
    }
    return 0;
}

  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  2. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  3. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的