CF525E Anya and Cubes 题解【双向搜索】【哈希表】

作者: wjyyy 分类: 双向搜索,哈希表,搜索,离散化,解题报告 发布时间: 2018-08-02 08:30

点击量:177

 

    状态不是很难想的一个双向搜索。

 

Description

Anya loves to fold and stick. Today she decided to do just that.

 

Anya has n cubes lying in a line and numbered from 1 to n from left to right, with natural numbers written on them. She also has k stickers with exclamation marks. We know that the number of stickers does not exceed the number of cubes.

 

Anya can stick an exclamation mark on the cube and get the factorial of the number written on the cube. For example, if a cube reads 5, then after the sticking it reads 5!, which equals 120.

 

You need to help Anya count how many ways there are to choose some of the cubes and stick on some of the chosen cubes at most kexclamation marks so that the sum of the numbers written on the chosen cubes after the sticking becomes equal to S. Anya can stick at most one exclamation mark on each cube. Can you do it?

 

Two ways are considered the same if they have the same set of chosen cubes and the same set of cubes with exclamation marks.

 

Input

The first line of the input contains three space-separated integers nk and S (1 ≤ n ≤ 250 ≤ k ≤ n1 ≤ S ≤ 1016) — the number of cubes and the number of stickers that Anya has, and the sum that she needs to get.

 

The second line contains n positive integers ai (1 ≤ ai ≤ 109) — the numbers, written on the cubes. The cubes in the input are described in the order from left to right, starting from the first one.

 

Multiple cubes can contain the same numbers.

Output

Output the number of ways to choose some number of cubes and stick exclamation marks on some of them so that the sum of the numbers became equal to the given number S.

Examples

input1
2 2 30
4 3
output1
1
input2
2 2 7
4 3
output2
1
input3
3 1 1
1 1 1
output3
6

Note

In the first sample the only way is to choose both cubes and stick an exclamation mark on each of them.

 

In the second sample the only way is to choose both cubes but don’t stick an exclamation mark on any of them.

 

In the third sample it is possible to choose any of the cubes in three ways, and also we may choose to stick or not to stick the exclamation mark on it. So, the total number of ways is six.

题意

给出n个数,n≤26,在其中选择不超过k个数添加上阶乘符号,选择其中部分数,使他们之和为给定值S≤1016。问有多少种方案(选数的位置不同或阶乘的位置不同都算不同的方案)。

题解:

    考虑暴力。

 

    在这个题中,每个数有3种决策,分别是不选、选上、加阶乘且选上。根据样例,这个题好像没有考虑加阶乘且不选的情况,在统计答案时少进入一种情况就可以了。

 

    如果每个数有三种决策,那么完全枚举的话时间复杂度是$ 3^n$,当$ n=26$时是无法通过的。而因为我们要求的是等式左边(若干个数之和)等于等式右边(给定值)。所以我们可以考虑先搜前$ \lfloor \frac n2\rfloor$个,再搜后$ \lceil \frac n2\rceil$个。把前面搜出来的结果挂到一个hash表上,每次搜到相同的值++。

 

    hash就是压缩了空间使得数据范围很大的但是个数不是特别大的数被存在一个较小的空间里,每次查询一个数就要去它模一个固定数的余数的那个剩余系中去找有没有相应的数。

 

    同时,在搜索的过程中,我们如果保证每次数值都会改变(即不搜0的情况),那么到一个dfs阶段,都可以统计一次答案,表示没被搜到的都是0。相当于一棵dfs树上的每个节点都统计了答案,这样减少了冗余0的叶子,优化了常数。

 

    因为S≤1016,而$ 18! \le 10^{16}\le 19!$,所以添加阶乘的数,只能不超过18。因此long long预处理出18以内的阶乘。对于$ O(3^\frac n2)$的复杂度,可行性剪枝就没有必要了(如果搜到的数已经大于S就一定不合法),所以我没有加。

 

Code:

#include<cstdio>
#include<cstring>
struct node//链表
{
    long long n;
    int v;
    node *nxt;
    node(long long n,int v)
    {
        this->n=n;
        this->v=v;
        nxt=NULL;
    }
    node()
    {
        nxt=NULL;
    }
}head[27][100003],*tail[27][100003];
long long a[30],s,n,k;
long long fct[20],now;
void dfs(int x,int num)//前一半
{

    int flag=0;
    long long tmp=now%100003;
    node *p=&head[num][tmp];
    while(p->nxt)
    {
        p=p->nxt;
        if(p->n==now)
        {
            p->v++;
            flag=1;
            break;
        }
    }
    if(flag==0)
    {
        tail[num][tmp]->nxt=new node(now,1);
        tail[num][tmp]=tail[num][tmp]->nxt;
    }
    if(x>n/2)
        return;
    for(int i=x;i<=n/2;i++)
    {
        now+=a[i];
        dfs(i+1,num);//可以加可行性剪枝
        now-=a[i];

        if(a[i]<=18)//判断范围
        {
            now+=fct[a[i]];
            dfs(i+1,num+1);
            now-=fct[a[i]];
        }
    }
}
long long sum=0;
void dfs2(int x,int num)
{
    for(int i=0;i<=k-num;i++)//查表
    {
        node *p=&head[i][((s-now)%100003+100003)%100003];
        while(p->nxt)
        {
            p=p->nxt;
            if(p->n==s-now)
            {
                sum+=p->v;
                break;
            }
        }
    }
    if(x>n)
        return;
    for(int i=x;i<=n;i++)
    {
        now+=a[i];
        dfs2(i+1,num);
        now-=a[i];

        if(a[i]<=18)
        {
            now+=fct[a[i]];
            dfs2(i+1,num+1);
            now-=fct[a[i]];
        }
    }
}
int main()
{
    fct[0]=1;
    for(int i=0;i<100003;i++)
        for(int j=0;j<=26;j++)
            tail[j][i]=&head[j][i];
    for(int i=1;i<=18;i++)
        fct[i]=fct[i-1]*i;
    scanf("%d%d%lld",&n,&k,&s);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n/2;i++)//搜前一半
    {
        now=a[i];
        dfs(i+1,0);
        if(a[i]<=18)
        {
            now=fct[a[i]];
            dfs(i+1,1);
        }
    }
    tail[0][0]->nxt=new node(0,1);//算一种0的情况
    tail[0][0]=tail[0][0]->nxt;
    for(int i=n/2+1;i<=n;i++)
    {
        now=a[i];
        dfs2(i+1,0);
        if(a[i]<=18)
        {
            now=fct[a[i]];
            dfs2(i+1,1);
        }
    }
    now=0;
    dfs2(n+1,0);//同样算一种0的情况
    printf("%I64d\n",sum);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */