前言
T1 不知道啥是冒泡排序，理解了一会儿题面代码发现是啥意思了于是就签了。
后面的题都不是很可做，T2、T4 计数，T3 高级玩意看不懂。
但是 T2 有点可做，但我的 DP 不知道哪儿假了，暴力还打挂了，不然加个 bitset 就操过去了。
T1 冒泡排序
\(i\) 只能和 \(i+k,i+2k,……\) 换，对于每一个模 \(k\) 的余数拎出来放 vector 里排序即可。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e6+10;
template<typename Tp> inline void read(Tp&x)
{x=0;register bool z=true;register char c=getchar_unlocked();for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n,k,a[N]; vector<int>b[N];
signed main()
{freopen("bubble.in","r",stdin),freopen("bubble.out","w",stdout);read(n,k); for(int i=1;i<=n;i++) read(a[i]);for(int i=1;i<=k;i++){for(int j=i;j<=n;j+=k) b[i].push_back(a[j]);sort(b[i].begin(),b[i].end(),[](int x,int y){return x>y;});}for(int i=1;i<=n;i++){write(b[(i-1)%k+1].back()),b[(i-1)%k+1].pop_back();putchar_unlocked(' ');}
}
T2 染色
当最后的数列为原数列的子序列，最后的数列是合法的，（1 1 1 2 2 3 3 视为 1 2 3），这是显然的。
\(f_{i,j,k}\) 表示处理到第 \(i\) 位，子序列长度为 \(j\)，结尾为 \(k\) 的方案数，有：
\[f_{i,j,a_i}=[j=1]+\sum_{k=1}^{i-1}\sum_{h=1}^m[a_i\ne h]f_{k,j-1,h}
\]
直接前缀和优化成 \(O(nm)\) 的，bitset 优化成 \(O(\frac{nm}{w})\)。
插板法，最后答案为 \(\sum\limits_{i=1}^nC_{n-1}^{i-1}\sum\limits_{j=1}^mf_{n,i,j}\)。
关于 \(C_n^m\) 的奇偶性，有 \(C_n^m\bmod 2=[n\&m=m]\)，lucas 定理直接证。
点击查看代码
#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e5+10,M=2e4+10;
template<typename Tp> inline void read(Tp&x)
{x=0;register bool z=true;register char c=getchar_unlocked();for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int T,n,m,len,a[N]; bitset<N>f[M],g,tmp; bool ans;
inline bool C(int n,int m) {return (n&m)==m;}
signed main()
{freopen("color.in","r",stdin),freopen("color.out","w",stdout);for(read(T);T;T--){read(n,m),ans=0,g=0; for(int i=1;i<=m;i++) f[i]=0;for(int i=1;i<=n;i++) read(a[i]); len=unique(a+1,a+1+n)-a-1;for(int i=1,x;i<=len;i++)tmp=g^f[x=a[i]],f[x]=tmp<<1,f[x][1]=1,g=tmp^f[x];for(int i=1;i<=len;i++) ans^=g[i]&C(n-1,i-1);putchar_unlocked(ans?'1':'0');}
}
T3 图
咕了。
T4 山峦
咕了。
