【洛谷】题解 P4871 【Oier们的镜子(mirror)】

我们可以比较暴力的做

每次枚举一个数，然后枚举子集可以用哪些东西构成

记录一下用了几组，最后除掉就行了

$7*3^n$7∗3n并不能过

然后可以用fwt优化

代码：

//2018.12.31 18:00
/*
   Name: Jiang_zi_chuan
   Copyright: Jiang_zi_chuan
   Author: Jiang_zi_chuan
   Date: 31/12/18 18:00
   Description: 算法类型
*/
// luogu-judger-enable-o2
//#define LOCAL
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <bits/stdc++.h>

#define INF 0x3f
#define ull unsigned long long
#define ll long long
#define FOR(a, b, n) for(register int a = b; b >= n ? a >= n : a <= n; b >= n ? a-- : a++)
#define M(a, n) memset(a, n, sizeof(a));
#define S(n) scanf("%d", &n)
#define P(n) printf("%d", n)
#define G(n) getline(cin, n)
#define PI acos(-1.0)
#define QAQ(n) 0
#define chen_zhe 0x3f

using namespace std;

const int NR = 1000;
#define lowbit(x) (x & ( -x ))
const int N = 16;
const int N2 = 1 << 15;
int n, a[N], b[N2], sum[N2], f[N][N2];
const int mo = 1e9 + 7;
void ps(int &x, int y)
{
  x += y;
  x %= mo;
}
int main()
{
  S(n);
  FOR(i, 1, n) 
    S(a[i]);
  sort(a + 1, a + n + 1);
  FOR(i, 1, n) 
    b[1 << (i - 1)] = a[i];
  int l = (1 << n) - 1;
  f[0][0] = 1;
  FOR(i, 1, l) 
    sum[i] = sum[i - lowbit(i)] + b[lowbit(i)];
  FOR(i, 1, n) 
  {
    FOR(j, 0, l) 
      if (f[i - 1][j])
      {
        ps(f[i][j | (1 << (i - 1))], f[i - 1][j]);
        for(register int k = j; k; k = (k - 1) & j)
          if (sum[k] == a[i])
          {
            ps(f[i][j ^ k], f[i - 1][j]);
            if (!(k - lowbit(k))) 
              ps(f[i][j ^ k], f[i - 1][j]);
          }
      }
  }
  int ans = 0;
  FOR(i, 0, l) 
    ps(ans, f[n][i]);
  P(ans);
  return 0; 
}