「考试总结」2022-02-08
数列
考虑设 \(f_i\) 表示以 \(i\) 为最后一段的最大值时的最大划分价值，将原序列建立 Cartisian 树之后可以形成的合法转移转移形态就是该点左子树的所有点和根链上向右走的那些父亲
直接实现复杂度是 \(\Theta(n^2)\) 的但是观察到使用非法转移一定没有合法转移更为优秀，因为 \(C\le 0\)，且多一个数值峰使得平方更大了
所以可以直接写一个李超树来做斜率优化即可
Code Display
const int N=1000010,inf=0x3f3f3f3f3f3f3f3f;
int n,C,a[N];
int dp[N];
struct Line{
int k,b; Line(){k=0,b=-inf;}
Line(int kk,int bb){k=kk; b=bb;}
inline int calc(int x){return k*x+b;}
}t[N<<2];
inline void insert(int p,int l,int r,Line now){
int lnow=now.calc(l),rnow=now.calc(r);
int lt=t[p].calc(l),rt=t[p].calc(r);
if(lt<=lnow&&rt<=rnow) return t[p]=now,void();
if(lnow<=lt&&rt>=rnow) return ;
int mid=(l+r)>>1;
if(t[p].calc(mid)<=now.calc(mid)){
swap(now,t[p]);
swap(lnow,lt);
swap(rnow,rt);
}
if(lt<=lnow) insert(p<<1,l,mid,now);
if(rt<=rnow) insert(p<<1|1,mid+1,r,now);
return ;
}
inline int query(int p,int l,int r,int x){
if(x>r||x>1;
return max(query(p<<1,l,mid,x),max(query(p<<1|1,mid+1,r,x),t[p].calc(x)));
}
signed main(){
freopen("array.in","r",stdin); freopen("array.out","w",stdout);
n=read(); C=read(); rep(i,1,n) a[i]=read();
rep(i,1,n){
ckmax(dp[i],query(1,1,N-10,a[i])+a[i]*a[i]+C);
insert(1,1,N-10,(Line){-2*a[i],dp[i]+a[i]*a[i]});
}
int lst=0,ans=0;
for(int i=n;i>=1;--i) if(a[i]>=lst) ckmax(ans,dp[i]),lst=a[i];
print(ans);
return 0;
}
差量
不要上来就跳进了“找 0&1 进行 \(1\) 操作，然后用 \(2\) 操作配合找值点” 的思维定式
先进行一次全局 \(2\) 操作就可以找到最大的值域 \(\rm Gap\)，然后找到包含最大 & 最小值中最短的一个前缀
不难发现该前缀的最后一个数字是最大/最小值之一
如果我们计算出来其它数字和其的数值差，找到最大的一个再对这两个点进行 \(1\) 操作就是找到了最大 & 最小值，其它数值也能还原出来
至此没有被解决的问题是求出来其它数和某个特定位置数字的数值差
这时发现如果询问 \(\{S\}\) 再询问 \(\{S\cup x\}\) 就能得到 \(x\) 与 \(\{S\}\) 中元素的价值之差，所以枚举所有二进制位，并将 \(S\) 每次设为这位为 \(0\) 的数字即可
最后从小到大计算每个位置 \(i\) 的数字和最短前缀尾部的数字的差的找到这个 \(i\) 所有为 \(0\) 的位的差值的交集即可
Code Display
#include "difference.h"
const int N=310;
vector a;
vector ret,qu;
int dlt[N];
multiset vals[N];
void find(int n, int M1, int M2) {
a.resize(n);
rep(i,0,n-1) qu.pb(i);
ret=qry2(qu);
int Mxd=0;
for(auto t:ret) ckmax(Mxd,t);
int lef=0,rig=n-1,tar=n;
while(lef<=rig){
int mid=(lef+rig)/2;
qu.clear();
rep(i,0,mid) qu.push_back(i);
ret=qry2(qu);
int nmx=0;
for(auto t:ret) ckmax(nmx,t);
if(nmx==Mxd) rig=mid-1,tar=mid;
else lef=mid+1;
}
//tar -> maximum/minimum value!
for(int bit=1;(1<<(bit-1))<=n;++bit){
qu.clear();
rep(i,0,n-1) if(i!=tar) if(i>>(bit-1)&1){}else qu.push_back(i);
multiset cur;
ret=qry2(qu);
for(auto t:ret) cur.insert(t);
qu.push_back(tar);
ret=qry2(qu);
for(auto t:ret){
if(cur.find(t)!=cur.end()) cur.erase(cur.find(t));
else vals[bit].insert(t);
}
}
rep(i,0,n-1) if(i!=tar){
int fir=1;
while(i>>(fir-1)&1) ++fir;
for(auto t:vals[fir]){
bool ban=0;
for(int bit=fir+1;(1<<(bit-1))<=n;++bit) if(i>>(bit-1)&1){} else{
if(vals[bit].find(t)==vals[bit].end()){
ban=1;
break;
}
}
if(!ban){dlt[i]=t; break;}
}
for(int bit=fir;(1<<(bit-1))<=n;++bit) if(i>>(bit-1)&1){} else{
vals[bit].erase(vals[bit].find(dlt[i]));
}
}
int argmx=-1;
for(int i=0;ia[argmx]){
rep(i,0,n-1) a[i]=a[tar]-dlt[i];
}else{
rep(i,0,n-1) a[i]=a[tar]+dlt[i];
}
answer(a);
return ;
}
异或
考虑使用 全集减去出现过 \(\{T\}\) 中元素的序列 的方式来计算答案
按照容斥式子设 \(f_{i,j}\) 表示长度为 \(i\) 的序列，全体的异或和为 \(j\) 时的在容斥式子中的贡献值，不难发现
\[ans=n^L-\sum_{i,j}f_{i,j}\times n^{n-i} \]转移也就是 \(f_{i,j}=-\sum_{k,l} f_{k,l}\times g(i-k,j,l)\)，其中 \(g_{len,a,b}\) 表示用 \(\{S\}\) 中元素拼出长度为 \(\rm len\) 的序列且整体异或和为 \(t_a\oplus t_b\) 的方案数
不难发现如果得到 \(g_{len,a,b}\) 之后可以使用一个 半在线卷积 来求得答案，其实这半在线卷积可以比原来的 \(2\) 个 \(\log\) 更快：
考虑倍增，设已经得到了 \([0,l)\) 的 \(f_{*,a,b}\) 值，先求 \([0,l)\) \(f_{*,a,b}\) 和 \(g_{*,a,b}\) 的点值并做矩阵乘法，然后清空中间结果 \(h_{*,a,b}\) 中 \([0,l)\) 的 \(*\) 的值再和原来的 \(f\) 的点值做一次矩阵乘法，这时可以得到合法的 \([l,2l)\) 处的 \(f_{*,a,b}\) 的值
正确性其实也比较好理解：不难发现 \([l,2l)\) 中每个长度的值都可以划分成若干个 \(g_{*,a,b}\) 累乘起来得到的，那么上述做法不重不漏地在长度累加第一次超过 \(l-1\) 时统计了答案，所以是可以形成双射的
这部分复杂度是 \(\Theta(m^3L+m^2L\log L)\)
最后的工作是求解 \(g_{len,a,b}\)，将所有 \(\{S\}\) 中的元素加入线性基，将线性基的基底 relabel 之后求出来 \(\{S\}\) 和 \(\{T\}\) 中的元素可以用线性基中哪些元素表示
一种直观的想法是枚举不能成功插入的元素出现次数的奇偶性，这时候就能得到线性基上面每个数字出现次数的奇偶性
那么求出来长度为 \(\rm len\) 的序列中有 \(x\) 种 特定 的元素出现了奇数次时的序列种类数，可以先求 随便有 \(x\) 种 元素出现了奇数次后除 \(\binom nx\)
随便出现可以设 \(dp_{i,j}\) 表示长度为 \(i\) 的序列有 \(j\) 个元素出现了奇数次的序列种类数，转移枚举填“已经出现了奇数次”的元素还是填“已经出现了偶数次” 的元素来得到 \(dp_{i+1,j\pm1}\)
妥当实现，不要多快速幂的 \(\log\) 的话复杂度是 \(\Theta(2^{n-|B|}m^2+m^2L)\)，其中 \(|B|\) 是线性基矩阵的秩
如果线性基之外的元素比较多的时候这个算法就会无能为力，那么对于线性基所构成的矩阵的秩比较小的时候对 \(\{S\}\) 中元素的线性基表示（\(\rm RS_i\)）并开桶，计算出 \(\{T\}\) 中元素的线性基表示 （\(\rm RT_i\)）
那么求 \(g_{len,a,b}\) 本质上就是求桶的 \(L\) 次方（乘法定义为集合幂级数的异或卷积）的 \(\rm RT_a\oplus RT_b\) 处的系数表示，由于我们只关注 \(m^2L\) 个位置的系数，所以尝试快速还原：
注意到 \(\rm FWT\) 之后每个位置的数值大小 \(\in [-n,n]\)，那么可以根据 \(\rm FWT\) 的定义式：\(\rm \frac1{2^{U}}FWT_i(-1)^{popcount(i\&j)}\to f_j\) 那么可以计算出来每个 \([-n,n]\) 中的数对新位置的贡献系数（也就是若干个 \(1,-1\) 的和）
另外注意到集合幂级数系数表示若干次幂可以对点值快速幂再还原得到，那么直接快速幂即可得到对应的贡献
注意 \(\rm FWT\) 的时候不要对负数取模和预处理 \([-n,n]\) 中的每个数字的幂来避免计算答案时带 \(\log\)
时间复杂度也是 \(\Theta(2^{|B|}m^2+m^2L)\)
所以以 \(|B|=\frac n2\) 为界点就可以得到可以通过的复杂度了！
Code Display
bool inb[N];
struct Linear_Basis{
int w[40],cnt,id[40],num;
inline bool insert(int x){
for(int i=30;i>=1;--i) if(x>>(i-1)&1){
if(!w[i]){
w[i]=x; ++cnt;
return 1;
} x^=w[i];
} return 0;
}
inline void label(){
for(int i=1;i<=30;++i) if(w[i]) id[i]=++num;
}
inline int query(int x){
int res=0;
for(int i=30;i>=1;--i) if(x>>(i-1)&1){
res|=1<<(id[i]-1);
x^=w[i];
} return x?-1:res;
}
}Init;
const int M=1<<17;
int sta[M],bit[M];
namespace Calc1{
int Repb[N],Repa[N],F[1<<17],pw[100][8010];
inline void main(){
static int id[40]={},pos[40]={};
int lim=1<=1;--i) if(x>>(i-1)&1){
if(!w[i]){
w[i]=x; Rep[i]=app;
return 1;
} x^=w[i]; app^=Rep[i];
} return 0;
}
inline int query(int x){
int ans=0;
for(int i=30;i>=1;--i) if(x>>(i-1)&1){
if(!w[i]) return -1;
x^=w[i]; ans^=Rep[i];
}
return x?-1:ans;
}
}Bas;
int invb[100];
inline int C(int n,int m){return mul(fac[n],mul(ifac[m],ifac[n-m]));}
inline int calc(int L,int i){return mul(dp[L][i],invb[i]);}
inline void main(){
fac[0]=1;
for(int i=1;i<=100;++i) fac[i]=mul(fac[i-1],i);
ifac[100]=ksm(fac[100],mod-2);
Down(i,100,1) ifac[i-1]=mul(ifac[i],i);
dp[0][0]=1;
for(int i=0;i<=n;++i) invb[i]=ksm(C(n,i),mod-2);
for(int i=0;i<=L;++i){
for(int j=0;j<=n;++j) if(dp[i][j]){
if(j) ckadd(dp[i+1][j-1],mul(dp[i][j],j));
if(j>(j-1)&1) sta[i]^=Repa[j];
}
for(int i=1;i<=m;++i){
if(~(Repb[i]=Bas.query(b[i]))) ids[++cnt]=i;
}
++cnt;
rep(i,1,cnt) rep(j,1,cnt){
static int Num[40]={};
rep(e,0,n) Num[e]=0;
int tar=Repb[ids[i]]^Repb[ids[j]];
for(int st=0;st<=S;++st){
int rem=sta[st]^tar;
int odd=__builtin_popcountll(rem)+bit[st];
Num[odd]++;
}
for(int day=1;day<=L;++day){
for(int e=0;e<=n;++e) ckadd(way[i][j][day],mul(calc(day,e),Num[e]));
}
}
return ;
}
}
int tmp1[22][22][N],tmp2[22][22][N],dp[22][22][N],tmp3[22][22][N];
signed main(){
freopen("randomxor.in","r",stdin); freopen("randomxor.out","w",stdout);
for(int i=1;i>1]+(i&1);
n=read(); m=read(); L=read();
rep(i,1,n) inb[i]=Init.insert(a[i]=read()); rep(i,1,m) b[i]=read();
if(Init.cnt>17) Calc2::main();
else Calc1::main();
rep(i,1,cnt) tmp1[i][i][0]=dp[i][i][0]=1; //init
rep(i,1,cnt) rep(j,0,L) way[i][cnt][j]=0; //can't transfer to d[i]=0
int len=1,lim=2;
while(len<=L){
int lst=len;
len<<=1; lim<<=1;
rep(i,1,cnt) rep(j,1,cnt){
rep(k,0,len-1) tmp2[i][j][k]=del(0,way[i][j][k]);
NTT(tmp2[i][j],lim,1);
NTT(tmp1[i][j],lim,1);
}
rep(i,1,cnt) rep(j,1,cnt) rep(k,1,cnt) rep(l,0,lim-1){
ckadd(tmp3[i][j][l],mul(tmp1[i][k][l],tmp2[k][j][l]));
}
rep(i,1,cnt) rep(j,1,cnt) rep(l,0,lim-1) tmp2[i][j][l]=0;
rep(i,1,cnt) rep(j,1,cnt){
NTT(tmp3[i][j],lim,-1);
rep(l,len,lim-1) tmp3[i][j][l]=0;
for(int l=0;l 其实这题目也是比较吃基本功的，哪一步都基础，但是哪一步不是最优做法了就只能付出提高复杂度的代价