luogu2396 yyy loves Maths VII

论卡（内存）常卡了一晚上不爽去抗议要求加大内存限制的悲哀2333

题目传送门

这题卡时间卡空间（卡空间是过去式）

xjb状压不用说了吧。

设\(f[x]\)=扔卡片方案为x（这个方案就是每一张卡片扔出去了/没扔出去）的方法数。强行转移

几点优化：

1、C++手动开\(O4\)

2、如果一个方案x走到的步数是个陷阱，则f[x]可以直接设为0

3、一个方案x走到的步数可以\(O(1)\)转移

4、没有用的数组删掉，变量多次利用。

最大的数据点129000+130000-KB，被128M卡掉了（128M是128000K而不是128*1024K，CNBB）

然后去申诉要求开大内存，成功了。

#prag\
ma GCC optimize("O4")
/*
Author: CNYALI_LK
LANG: C++
PROG: luogu2396.cpp
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cctype>
#define up(a,b,c) for (int a(b),end##a(c);a<=end##a;++a)
#define down(a,c,b) for (int a(b),end##a(c);a>=end##a;--a)
#define uup(a,c,b) for (int a(b),end##a(c);a<=end##a;++a)
#define udown(a,b,c) for (int a(b),end##a(c);a>=end##a;--a)
#define go(a,b) for(int a=0;a<b;++a)
#define endl '\n'
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
struct inout{
    static const int ibufl=1<<8;
    static const int obufl=1<<4;
    char in_buf[ibufl],out_buf[obufl],*inf,*ouf;
    inout(){
        inf=in_buf;ouf=out_buf;
    }
    void init(){
        fread(in_buf,1,ibufl,stdin);
    }
    inout& operator >>(int &a){
        int fh=1;
        while(!(isdigit(*inf)||*inf=='-'))++inf;
        if(*inf=='-')fh=-1,++inf;
        a=0;
        while(isdigit(*inf)){a=a*10+*inf-'0';++inf;}
        a*=fh;
        return *this;
    }
    
    void writeint(int x){
        if(x/10)writeint(x/10);
        *ouf=x%10+'0';
        ++ouf;
    }
    inout& operator <<(int a){
        if(a<0){*ouf='-';++ouf;a=-a;}
        writeint(a);
        return *this;
    }
    inout& operator <<(char a){
        *ouf=a;++ouf;
        return *this;
    }
    void out(){
        fwrite(out_buf,1,ouf-out_buf,stdout);
        ouf=out_buf;
    }
};
inout io;
template<class T>void chkmin(T &a,T b){a=a<b?a:b;}
template<class T>void chkmax(T &a,T b){a=a>b?a:b;}
int f[1<<24],zysz[1<<24];
const int mod=1000000007;
#define lowbit(x) (x&-x)
int main(){
    io.init();
    int n,m,s,sum=0,yycsb=-1,lssb=-1,i;
    io>>n;
    for(i=0;i<n;++i){io>>zysz[1<<i];sum+=zysz[1<<i];}
    io>>m;
    if(m==1)io>>yycsb;
    else if(m==2)io>>yycsb>>lssb;

    m=1<<n;
    int x;
    f[0]=1;
    for(i=1;i<m;++i){
        if(i==0){
            f[i]=1;continue;
        }
        s=i;
        x=lowbit(s);
        zysz[i]=zysz[i^x]+zysz[x];
        if(zysz[i]==yycsb||zysz[i]==lssb)continue;
        while(s){
            x=lowbit(s);
            f[i]+=f[i^x];
            if(f[i]>=mod)f[i]-=mod;
            s^=x;
        }
    }
    io<<f[m-1]<<endl;
    io.out();
    return 0;
}