SS241019B. 染色（color）
SS241019B. 染色（color）
思路
首先观察结果序列长什么样子，且思考如何去重。
结果序列是若干段长度若干的颜色拼成的，满足颜色序列是原序列的一个子序列，如 111555334 可以是 123453345 的一个合法结果，对应的颜色序列是 1534。为了去重，要求颜色序列不存在两个相邻的颜色。
发现可以转换成求本质不同的子序列，满足子序列不存在两个相邻的颜色。
比如 1534 是一个合法的子序列，而 11534 不是。
对于一个长度为 \(len\) 的合法子序列，可以形成 \(\binom{n-1}{len-1}\) 个本质不同的结果。
求本质不同的没有相邻的相等颜色的子序列个数，可以使用 DP。
设 \(f_{i,j}\) 表示考虑到原序列第 \(i\) 个位置，填子序列的第 \(j\) 位的方案数。
假设原序列是 123453345，那么 \(f_6\) 可以由 \(f_{4 \sim 5}\) 转移而来。前缀和优化即可。
答案就是 \(f_{x,j}\) 乘上 \(\binom{n-1}{j-1}\)。可以插板，\(n-1\) 个位置插上 \(j-1\) 个板分成 \(j\) 块，每块非空。
由于题目只需要模 \(2\) 的结果，而且还叫你关注时间和空间限制，因此可以想到使用 bitset。加法在模 \(2\) 意义下是按位异或。把第二维变成 bitset。时间复杂度 \(O(\frac{n^2}{w})\)。
啊，但是空间会爆，空间是 \(O(\frac{n^2}{w})\) 的。
考虑 \(m\) 的数据范围是 \(2 \times 10^4\)，考虑顺序扫描原序列，维护使用 bitset。维护 \(f_i\) 表示最后一位填目前颜色，子序列长度为 \(i\) 的方案数。
答案统计最后一位填每一个颜色的答案，每一种子序列长度乘上一个相应的组合系数。
考虑枚举到 \(x\)，颜色是 \(c_x\)。维护 \(f\)。当前的 \(f\) 由上一个相同颜色到上一个颜色这一段区间的 \(f\) 相加得到。因此可以记一个到目前的前缀和数组 \(s_j\) 表示子序列长度为 \(j\)，最后一位填 \(1 \sim x\) 的数的方案和。以及每个颜色最后一次出现的历史前缀和数组 \(g_{i,j}\) 表示最后一次出现颜色 \(i\) 时候的 \(s\)，这样就可以算出目前的 \(f\) 了。然后就可以加到 \(s\) 和 \(g_{c_x}\) 里面。
最后统计答案可以直接统计 \(s\)。\(s_i\) 的系数是 \(\binom{n-1}{i-1}\)，乘法在模 \(2\) 意义下是按位与。因此我们需要快速计算这一坨东西的奇偶性。需要学习卢卡斯定理。待学习。
总时间复杂度 \(O(\frac{n^2}{w})\)，空间 \(O(\frac{nm}{w})\)。
code
#include<bits/stdc++.h>
// #define LOCAL
#define sf scnaf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
#define isdigit(x) (x>='0'&&x<='9')
template <typename T>
void read(T &x) {
x=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) ;
for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
}
template <typename T>
void write(T x,char ch) {
static int st[20];
int top=0;
do {
st[top++]=x%10;
x/=10;
}while(x);
while(top) putchar(st[--top]+'0');
putchar(ch);
}
constexpr int N=1e5+7,M=2e4+7;
int t,n,m,a[N];
bitset<N> f,g[M];
void init() {
f.reset(),g[0].reset();
rep(i,1,m) g[i].reset();
g[0][0]=1;
}
int main() {
#ifdef LOCAL
freopen("my.out","w",stdout);
#else
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
#endif
read(t);
while(t--) {
read(n),read(m);
rep(i,1,n) read(a[i]);
init();
rep(i,1,n) {
f=(g[0]^g[a[i]])<<1;
g[0]^=f;
g[a[i]]=g[0];
}
int ans=0;
rep(i,1,n) ans^=g[0][i]&(((i-1)&(n-1))==(i-1));
putchar(ans?'1':'0');
}
}