<div class="post_brief"><p>
看上去比较不可做的DP。好像别人写的记搜跑得飞快。</p>

 

我看我是写最小表示写上瘾了。

 

压一下状态，有点像今天第二题。算每种值的有多少。然后直接跑。

 

感觉废状态比较多啊，跑得好慢。另外用memset清空高维数组会比较快。

 

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;


const int mod = 1e9 + 7;
const int maxn = 17;
const int maxst = 16009;


#define mbit(a,b) ((a)<<((b)<<2))
#define gbit(a,b) (((a)>>((b)<<2))&0xf)
#define _l (long long int)


int m, c[maxn], n, mt, tots, slst[maxst];
int f[2][7][maxst];


void dfsState(int t, int l, int v) {
if (l == mt + 1) {
slst[tots ++] = v | t;
}
else {
for (int i = 0; i <= t; ++ i)
dfsState(t - i, l + 1, v | mbit(i, l));
}
}


inline int fState(int x) {
return lower_bound(slst, slst + tots, x) - slst;
}


inline void incm(int& a, int b) {
a += b;
if (a >= mod)
a -= mod;
}


#define clearFCur() { 

for (int i = 1; i <= mt; ++ i) 

for (int j = 0; j < tots; ++ j) 

f[cur][i][j] = 0; 

}


int dp() {
int cur(0), prv(1);
int sb(0);
for (int i = 0; i <= mt; ++ i)
sb |= mbit(c[i], i);
memset(f, 0, sizeof(f));
for (int i = 1; i <= mt; ++ i)
if (gbit(sb, i) > 0)
f[cur][i - 1][fState(sb - mbit(1, i) + mbit(1, i - 1))] = gbit(sb, i);
for (int ti = 1; ti < n; ++ ti) {
swap(cur, prv);
//		clearFCur();
memset(f[cur], 0, sizeof(f[cur]));
for (int i = 0; i <= mt; ++ i)
for (int j = 0; j < tots; ++ j)
if (f[prv][i][j]) {
int s(slst[j]), c;
for (int k = 1; k <= mt; ++ k)
if ((c = gbit(s, k) - (k == i)))
incm(f[cur][k - 1][fState(s - mbit(1, k) + mbit(1, k - 1))], _l f[prv][i][j] * c % mod);
}
}
return f[cur][0][fState(m)];
}


int main() {
#ifndef ONLINE_JUDGE
freopen(“in.txt”, “r”, stdin);
#endif


scanf("%d", &amp;m);
memset(c, 0, sizeof(c));
mt = 0;
n = 0;
for (int i = 0; i &lt; m; ++ i) {
	int tmp;
	scanf("%d", &amp;tmp);
	n += tmp;
	++ c[tmp];
	if (tmp &gt; mt)
		mt = tmp;
}
tots = 0;
dfsState(m, 1, 0);
sort(slst, slst + tots);
printf("%d\n", dp());



}