【codechef】Chef and the Number Sequence（构成最长公共子序列为L的可能性）

hueel

　　大厨拥有一个长度为 N 的序列 A，其中的每个元素都是 1 到 K 之间的整数（包括 1 和 K）。现在大厨想要得到到另一个序列 B，它的长度与 A 同为 N，而且每个元素也都是 1 到 K 之间的整数（同样包括 1 和 K）。大厨要求序列 A 和序列 B 的最长公共子序列的长度恰好为 L。请你求出有多少个序列 B 可以满足大厨的要求。由于答案可能非常大，请输出答案对 109 + 7 取模之后的结果。
　　输入格式
　　输入数据第一行包含一个整数 T，表示数据组数。接下来是 T 组数据。每组数据的第一行包含三个以空格隔开的整数 N、K，和 L。每组数据的第二行包含 N 个整数 A1, A2, . . . , AN，以空格隔开。
　　输出格式
　　对于每组数据，输出一行，包含一个整数，即满足要求的 B 序列的方案数对 109 + 7 取模之后的结果。数据范围· 1 ≤ T ≤ 10· 1 ≤ N, K ≤ 16· 1 ≤ L ≤ N· 序列 A 中的每个元素都是 1 到 K 之间的整数（包括 1 和 K）
　　


Constraints

• 1 ≤ T ≤ 10
  
• 1 ≤ N,K ≤ 16
  
• 1 ≤ L ≤ N
  
• The sequence A consists of integers between 1 and K (both inclusive).
  

Example

Input:
2
2 2 1
1 2
3 3 2
1 2 2
Output:
3
11
　　第一个样例：满足要求的序列 B 一共三种：[1, 1]、[2, 2]，和 [2, 1]。这三个序列与序列 A 的最长公共子序列长度均为 1。注意 [1, 2] 不是一个满足要求的序列，因为它与序列 A 的最长公共子序列长度为 2。第二个样例：满足要求的序列 B 一共 11 种：[1, 1, 2]、[1, 2, 1]、[1, 2, 3]、[1, 3, 2]、[2, 1, 2]、[2, 2, 1]、[2, 2, 2]、[2, 2, 3]、[2, 3, 2]、[3, 1, 2]，和 [3, 2, 2]。说明我们认为两个序列不同，当且仅当两个序列有至少一个位置上的元素值不同。


　　https://www.codechef.com/COOK61/problems/SEQLCS


　　————————————————————————
　　是一道不错的难题。next[d][j]表示在构造我们要求的其中一种数列时向末位插入数字j(1<=j<=k)之后最长公共子序列变化。d和mask都是二进制，表示取了A数组的某几位组成最长公共子序列。dp[d]表示距离构成B数组还差i位，还差d的二进制表示的几位最长公共子序列。
　　为了避免重复算，比如1 2 2,避免算两次1 2,或者算两次2，中间那一段难懂的代码就是完成这个操作。所以还是以1 2 2为例，二进制d取3和取5是一样的，取2和取4也是一样的，因此每次都要把这些一样的情况的mask归成一样的，这样在算dp时才会只算一次。
　　

#include <bits/stdc++.h>
using namespace std;
const int N = 18;
const int M = (1 << 16) + 2;
const int MOD = 1000000007;
int dp[N][M], next[M][N], a[N], oldLCS[N], newLCS[N];
int t, n, k, l, i, j, d, res;
int main() {
// freopen(&quot;input.in&quot;, &quot;r&quot;, stdin);
// freopen(&quot;output.out&quot;, &quot;w&quot;, stdout);
scanf(&quot;%d&quot;, &t);
while (t--) {
scanf(&quot;%d %d %d&quot;, &n, &k, &l);
for (i = 1; i <= n; ++i) {
scanf(&quot;%d&quot;, a + i);
}
memset(dp, 0, sizeof dp);
for (d = 0; d < (1 << n); ++d) {
oldLCS[0] = 0;
for (j = 0; j < n; ++j) {
oldLCS[j + 1] = oldLCS[j] + ((d >> j) & 1);
}
for (j = 1; j <= k; ++j) {
newLCS[0] = 0;
for (i = 1; i <= n; ++i) {
if (a == j) {
newLCS = oldLCS[i - 1] + 1;
} else {
newLCS = max(oldLCS, newLCS[i - 1]);
}
}
int mask = 0;
for (i = 1; i <= n; ++i) {
if (newLCS > newLCS[i - 1]) {
mask += (1 << (i - 1));
}
}
next[d][j] = mask;
//          cout<<&quot;// &quot;<<d<<&quot; &quot;<<j<<&quot; &quot;<<mask<<endl;
}
}
dp[0][0] = 1;
for (i = 0; i < n; ++i) {
for (d = 0; d < (1 << n); ++d) {
if (dp[d] > 0) {
cout<<i<<&quot; &quot;<<d<<endl;
for (j = 1; j <= k; ++j) {
dp[i + 1][next[d][j]] += dp[d];
dp[i + 1][next[d][j]] %= MOD;
}
}
}
}
res = 0;
for (d = 0; d < (1 << n); ++d) {
if (__builtin_popcount(d) == l) {
res = res + dp[n][d];
if (res >= MOD) res -= MOD;
}
}
printf(&quot;%d\n&quot;, res);
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long LL;
typedef pair<int, int> PII;
int tt;
int n, k, l;
int a[16], d[1 << 16], nd[1 << 16];
const int MOD = 1e9 + 7;
int bc[1 << 16];
inline void modAdd(int &x, int y) {
x += y;
if (x >= MOD) x -= MOD;
}
int f[17], g[17];
int t[1 << 16][16];
int main() {
//freopen(&quot;input.txt&quot;, &quot;r&quot;, stdin);
REP(i, 1 << 16) bc = __builtin_popcount(i);
scanf(&quot;%d&quot;, &tt);
REP(test, tt) {
scanf(&quot;%d%d%d&quot;, &n, &k, &l);
REP(i, n) scanf(&quot;%d&quot;, a + i), --a;
int MX = 1 << n;
memset(d, 0, sizeof d);
d[0] = 1;
REP(mask, MX) {
int c = 0;
f[0] = 0;
REP(i, n) {
if (mask & (1 << i)) ++c;
f[i + 1] = c;
}
REP(j, k) {
REP(q, n) {
if (a[q] == j) {
g[q + 1] = f[q] + 1;
} else {
g[q + 1] = f[q + 1];
}
}
for (int q = 1; q < n; ++q) {
g[q + 1] = max(g[q + 1], g[q]);
}
g[0] = 0;
int nmask = 0;
REP(q, n) if (g[q + 1] > g[q]) {
nmask |= 1 << q;
}
t[mask][j] = nmask;
//            cout<<&quot;// &quot;<<mask<<&quot; &quot;<<j<<&quot; &quot;<<nmask<<endl;
}
//        cout<<&quot;-----------&quot;<<endl;
}
REP(times, n) {
memset(nd, 0, sizeof nd);
REP(mask, MX) if (d[mask]) {
REP(j, k) {
int nmask = t[mask][j];
modAdd(nd[nmask], d[mask]);
}
}
memcpy(d, nd, sizeof d);
}
int ans = 0;
REP(mask, MX) if (bc[mask] == l) {
modAdd(ans, d[mask]);
}
printf(&quot;%d\n&quot;, ans);
}
return 0;
}