http://codeforces.com/contest/1158/problem/F
先考虑如何求一个序列的density。
假设要求序列\(A[1..n]\)的density。
找到\(A[1..n]\)的最小一个前缀\(A[1..i]\),使其包含\(1-c\)的所有颜色。
那么我们可以 以这些颜色作为那些序列的开头,并且这样一定是最优的,那么\(Density(A[1..n])=Density(A[i+1..n])+1\)
此时我们可以得到一个显然的状压dp:
\(f[i][j][S]\)表示前\(i\)个中,已有\(j\)个包含\(1-c\)的段,最后一个段现在包含\(S\)中的颜色。
时间复杂度:\(O(n^2/c*2^c)\)
事实上可以搞出更快的dp。
设\(g[i][j]\)表示在\(A[i..j]\)中选一个子序列,这个子序列包含\(A[j]\),且恰好包含\(1-c\)的颜色。
“恰好”的定义:选了\(A[j]\)之后才包含\(1-c\)的颜色。
那么枚举\(j\),再倒着枚举\(i\),用一个桶统计每个颜色出现次数,即可算出\(g\)。
同理可以算出\(h[i][j]\)表示在\(A[i..j]\)中选一个子序列,这个子序列包含\(A[j]\),且不能包含\(1-c\)的颜色。
设\(f[i][j]\)表示以\(i\)结尾的子序列中,恰有\(j\)个\(1-c\)的段,利用\(g\)可以很快的转移。
算出\(f\)后,利用\(h\)可以统计答案案。
时间复杂度:\(O(n^3/c)\)
综合两个算法即可通过本题。
Code:
#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i < _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;
const int mo = 998244353;
ll ksm(ll x, ll y) {
ll s = 1;
for(; y; y /= 2, x = x * x % mo)
if(y & 1) s = s * x % mo;
return s;
}
const int N = 3005;
int n, c, a[N];
ll ans[N];
namespace sub1 {
ll a2[N], inv[N];
ll g[N][N], h[N][N], sh[N];
ll cnt[N], sum, c0;
void cl() {
fo(i, 1, c) cnt[i] = 0;
sum = 1; c0 = c;
}
void add(int x) {
if(!cnt[x]) {
cnt[x] ++;
c0 --;
} else {
sum = sum * inv[cnt[x]] % mo;
cnt[x] ++;
sum = sum * (a2[cnt[x]] - 1) % mo;
}
}
ll f[N][N];
void work() {
a2[0] = 1; fo(i, 1, n) a2[i] = a2[i - 1] * 2 % mo;
fo(i, 0, n) inv[i] = ksm(a2[i] - 1, mo - 2);
fo(j, 1, n) {
cl();
fd(i, j, 1) {
add(a[i]);
if(c0) {
g[i][j] = 0;
h[i][j] = a2[j - i];
} else {
ll v = sum * inv[cnt[a[j]]] % mo;
g[i][j] = v;
h[i][j] = (a2[j - i] - v * a2[cnt[a[j]] - 1] % mo + mo) % mo;
}
}
}
f[0][0] = 1;
fo(i, 0, n - 1) fo(j, 0, n / c) if(f[i][j]) {
fo(k, i + 1, n) f[k][j + 1] = (f[k][j + 1] + f[i][j] * g[i + 1][k]) % mo;
}
fo(i, 0, n) fo(j, i, n) sh[i] = (sh[i] + h[i][j]) % mo;
fo(i, 0, n) fo(j, 0, n / c) {
if(i > 0) ans[j] = (ans[j] + f[i][j]) % mo;
ans[j] = (ans[j] + f[i][j] * sh[i + 1]) % mo;
}
}
}
namespace sub2 {
int m;
ll f[2][N][1 << 10]; int o;
void work() {
m = (1 << c) - 1;
f[o][0][0] = 1;
fo(i, 1, n) {
fo(j, 0, i / c) fo(s, 0, m) f[!o][j][s] = f[o][j][s];
fo(j, 0, (i - 1) / c) {
fo(s, 0, m - 1) if(f[o][j][s]) {
int ns = s | (1 << (a[i] - 1));
int nj = j;
if(ns == m) ns = 0, nj ++;
f[!o][nj][ns] = (f[!o][nj][ns] + f[o][j][s]) % mo;
}
}
o = !o;
}
fo(j, 0, n / c) fo(s, 0, m)
ans[j] = (ans[j] + f[o][j][s]) % mo;
ans[0] = (ans[0] - 1 + mo) % mo;
}
}
int main() {
scanf("%d %d", &n, &c);
fo(i, 1, n) scanf("%d", &a[i]);
if(c > 10)
sub1 :: work();
else
sub2 :: work();
fo(i, 0, n) pp("%lld ", ans[i]); hh;
}