自动搬运

查看原文

来自洛谷，原作者为

	CQ_Bab 行稳致远

搬运于2025-08-24 23:11:08，当前版本为作者最后更新于2025-03-16 16:49:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

这题出得太好了，下次别出了。

思路

首先很能得出一个 dp，我们定义 $f_i$ 表示前 $i$ 个的开心值之和，然后转移为 $f_i=\sum f_j+(s_j-s_i)\times 2^{j-1}\times(sa_i-sa_j-(ca1_i-ca1_j)\times ca0_j)\times (sb_i-sb_j-(cb0_i-cb0_j)\times cb1_j)$，其中 $s_i$ 表示 $1\sim i$ 中 $a_i\neq b_i$ 的数量和，$sa_i$ 表示 $1\sim i$ 中 $01$ 子序列的数量，$ca1_i,ca0_i$ 分别表示 $1\sim i$ 中 $a_i=1/0$ 的数量，$sb_i$ 表示 $b$ 数组中 $10$ 子序列的数量，$cb_0$ 和 $cb_1$ 与 $ca0$ 和 $ca1$ 的意义相似。

然后我们考虑优化这个东西，当然只能拆开柿子了，拆开之后一共有 $16$ 个多项式，然后每一个带 $j$ 的多项式都维护一个前缀和即可，这个就不讲了。

但是，这道题还要卡空间所以我们只能开一个 $5\times 10^7$ 的数组，那么我们要将 $s,sa,sb,ca0,ca1,cb0,cb1$ 都在遍历到 $i$ 的时候计算，可是我们发现对于 $op=1$ 的情况 $f,g$ 数组都要开到 $n$，那不是炸了吗，但是我们发现对于 $n$ 会用到的 $f,g$ 下标只到 $\lfloor \frac{n}{64} \rfloor+3$ 也就只用算到这个位置了，然后就能开下了。

代码

简直就是石山，注意卡常。

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define rep1(i,x,y) for(register int i=x;i>=y;--i)
#define int long long
#define fire signed
#define il inline
template<class T> il void print(T x) {
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
template<class T> il void in(T &x) {
    x = 0; char ch = getchar();
    while (ch < '0' || ch > '9') {ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
}
int T=1;
int n,op;
const int N=5e7+10,mod=1e9+7;
unsigned long long ff[N],g[N];
int sum,f;
#define pl(x,y) (x=(x+y)%mod)
#define pl1(x,y) (x=(x+((y)%mod+mod))%mod)
fire main() {
	in(n),in(op);
	if(op==1) {
		unsigned long long x1,y1,z1,x2,y2,z2;
		in(x1),in(y1),in(z1),in(ff[1]),in(ff[2]);
		in(x2),in(y2),in(z2);
		in(g[1]),in(g[2]);
		rep(i,3,782000) {
			ff[i]=(ff[i-2]*x1+ff[i-1]*y1+z1);
			g[i]=(g[i-2]*x2+g[i-1]*y2+z2);
		}
	}else {
		rep(i,1,n) in(ff[i]),in(g[i]);
	}
	int s=0,cb0=0,cb1=0,ca0=0,ca1=0,sa=0,sb=0,jc=1,f=0;
	int saj=0,sbj=0,ca01=0,ca1ca0=0,cb11=0,sj=0,cb0cb1=0;
	int sas=0,sbs=0,sca0=0,sca1ca0=0,cb1s=0,cb0cb1s=0,s2j=1;
	rep(i,1,n) {
		int a=0,b=0;
		if(op==0) {
			a=ff[i],b=g[i];
		}else {
			a=((ff[((i-1)>>6)+3]>>((i-1)&63))&1);
			b=((g[((i-1)>>6)+3]>>((i-1)&63))&1);
		}
		s=(s+(a!=b));
		cb0=(cb0+(b==0));
		cb1=i-cb0;
		ca0=(ca0+(a==0));
		ca1=i-ca0;
		sa=(sa+(a==1)*ca0)%mod;
		sb=(sb+(b==0)*cb1)%mod;
		f=sum;
		int gg=sa+sb;
		gg=(gg*s2j);
		pl1(gg,-saj-sbj);
		pl1(gg,ca1ca0-(ca1*ca01));
		pl1(gg,cb0cb1-(cb0*cb11));
		pl(f,gg*s);
		
		pl(s2j,jc);
		pl(saj,sa*jc);
		pl(sbj,sb*jc);
		pl(ca01,ca0*jc);
		pl(ca1ca0,ca1*ca0%mod*jc);
		pl(cb11,cb1*jc);
		pl(cb0cb1,cb0*cb1%mod*jc);
		
		int gg1=0;
		pl(gg1,(sa+sb)*sj);
		pl1(gg1,-sas-sbs);
		pl1(gg1,sca1ca0-(ca1*sca0));
		pl1(gg1,cb0cb1s-(cb0*cb1s));
		pl1(f,-gg1);
		
		
		pl(sj,s*jc);
		pl(sas,s*sa%mod*jc);
		pl(sbs,s*sb%mod*jc);
		pl(sca0,ca0*s%mod*jc);
		pl(sca1ca0,s*ca1%mod*ca0%mod*jc);
		pl(cb1s,cb1*s%mod*jc);
		pl(cb0cb1s,cb1*cb0%mod*s%mod*jc);
		sum=(sum+f)%mod;
		jc=jc*2%mod;
	}
	print(f);
	return false;
}