题解：P11891 [XRCOI Round 1] B. 稻花香里说丰年
2672434062xzl
·
·
题解
O(n^2) 15pts
对于 T(l,r) 可采用前缀和的方法。
设 sum_n=\sum_{i=1}^{n} [a_i\ne b_i],T(l,r)=sum_r-sum_{l-1}。
对于 A(l,r) 在 [l,r] 中的 0 统计其后有多少 1，所以 A(l,r)=\sum_{i=l}^{r} \left ( [a_i=0]\times \sum_{j=i+1}^{r}[a_j=1] \right )。
同理可得 B(l,r)=\sum_{i=l}^{r} \left ( [b_i=1]\times \sum_{j=i+1}^{r}[b_j=0] \right )。
二者皆可以用前缀和优化，设 s1_n=\sum_{i=1}^{n}[a_i=0]，则 A(l,r)=\sum_{i=l}^{r} \left ( [a_i=0]\times (r-s1_r-i+s1_i) \right )。
=(r-s1_r)(s1_r-s1_{l-1})-\sum_{i=l}^{r}[a_i=0]\times(i-s1_i)$$。
对后半部分再用一次前缀和，设 $s3_n=\sum_{i=1}^{n}[a_i=0]\times(i-s1_i)$，则 $A(l,r)=(r-s1_r)(s1_r-s1_{l-1})-(s3_r-s3_{l-1})$。
同理可得，设 $s2_n=\sum_{i=1}^{n}[b_i=1]$，$s3_n=\sum_{i=1}^{n}[b_i=1]\times(i-s2_i)$，$B(l,r)=(r-s2_r)(s2_r-s2_{l-1})-(s4_r-s4_{l-1})$。
考虑区间 $[l,r]$，左边 $l-1$ 个数，会有 $l-2$ 个空隙，每个空隙可以隔开空隙两边，所以左边方案数为 $2^{\max(l-2,0)}$，同理可得右边为 $2^{\max(n-r-1,0)}$。
所以答案为 $\sum_{l=1}^{n}\sum_{r=l}^{n} 2^{\max(l-2,0)}2^{\max(n-r-1,0)}((r-s1_r)(s1_r-s1_{l-1})-(s3_r-s3_{l-1})+(r-s2_r)(s2_r-s2_{l-1})-(s4_r-s4_{l-1}))$。
对 $s3,s4$ 合并, $s3_n=\sum_{i=1}^{n} [a_i=0]\times (i-s1_i)+[b_i=1]\times (i-s2_i)$。
答案为 $\sum_{l=1}^{n}\sum_{r=l}^{n} 2^{\max(l-2,0)}2^{\max(n-r-1,0)}((r-s1_r)(s1_r-s1_{l-1})+(r-s2_r)(s2_r-s2_{l-1})-(s3_r-s3_{l-1})$。
参考程序：
```cpp
#include<iostream>
using namespace std;
using ll=long long;
const ll N=1e4+10,mod=1e9+7;
ll sum[N],s1[N],s2[N],s3[N];
ll p[N];
bool a[N],b[N];
int main(){
int n,op;
cin>>n>>op;
for(int i=1;i<=n;++i){
scanf("%d%d",&a[i],&b[i]);
sum[i]=sum[i-1]+(a[i]!=b[i]);
}
for(int i=1;i<=n;++i)s1[i]=s1[i-1]+(a[i]==0);
for(int i=1;i<=n;++i)s2[i]=s2[i-1]+(b[i]==1);
for(int i=1;i<=n;++i)s3[i]=(s3[i-1]+(a[i]==0)*(i-s1[i])+(b[i]==1)*(i-s2[i]))%mod;
ll ans=0;
p[0]=1;
for(int i=1;i<=n;++i)p[i]=p[i-1]*2%mod;
for(int l=1;l<=n;++l)
for(int r=l;r<=n;++r){
ans+=p[max(n-r-1,0)]*p[max(l-2,0)]%mod*(sum[r]-sum[l-1])%mod
*((r-s1[r])*(s1[r]-s1[l-1])%mod+(r-s2[r])*(s2[r]-s2[l-1])%mod-(s3[r]-s3[l-1]))%mod;
ans%=mod;
}
cout<<ans;
return 0;
}
```
## $O(n)$ 60pts
考虑再次使用前缀和优化。
对于每个 r，求出 $2^{\max(n-r-1,0)}\times \sum_{l=1}^r2^{\max (l-2,0)}\times (sum_r-sum_{l-1})\times
[(r-s1_r)(s1_r-s1_{l-1})+(r-s2_r)(s2_r-s2_{l-1})-(s3_r-s3_{l-1})]$。
对上式后半部分整理得
$
(r-s1_r)(s1_r-s1_{l-1})+(r-s2_r)(s2_r-s2_{l-1})-(s3_r-s3_{l-1})=
(r-s1_r)s1_r+(r-s2_r)s2_r-s3_r-(r-s1_r)s1_{l-1}-(r-s2_r)s2_{l-1}+s3_{l-1}\\
$。
再乘上 $(sum_r-sum_{l-1})$ 这一项
$$(sum_r-sum_{l-1})\times ((r-s1_r)s1_r+(r-s2_r)s2_r-s3_r-(r-s1_r)s1_{l-1}-(r-s2_r)s2_{l-1}+s3_{l-1})=\\
((r-s1_r)s1_r+(r-s2_r)s2_r-s3_r)sum_r-(r-s1_r)sum_r\times s1_{l-1}-(r-s2_r)sum_r\times s2_{l-1}+sum_r\times s3_{l-1}\\
-((r-s1_r)s1_r+(r-s2_r)s2_r-s3_r)sum_{l-1}+(r-s1_r)sum_{l-1}\times s1_{l-1}+(r-s2_r)sum_{l-1}\times s2_{l-1}-sum_{l-1}\times s3_{l-1}$$。
乘上 $2^{\max (i-2,0)}$ 后对每一部分进行前缀和
$$sump_n=\sum_{i=1}^{n}2^{\max (i-2,0)} \\
s4_n=\sum_{i=1}^{n} 2^{\max (i-2,0)}sum_{i-1}\\
s5_n=\sum_{i=1}^{n} 2^{\max (i-2,0)}s1_{i-1}\\
s6_n=\sum_{i=1}^{n} 2^{\max (i-2,0)}s2_{i-1}\\
s7_n=\sum_{i=1}^{n} 2^{\max (i-2,0)}s3_{i-1}\\
s8_n=\sum_{i=1}^{n} 2^{\max (i-2,0)}sum_{i-1}\times s1_{i-1}\\
s9_n=\sum_{i=1}^{n} 2^{\max (i-2,0)}sum_{i-1}\times s2_{i-1}\\
s10_n=\sum_{i=1}^{n} 2^{\max (i-2,0)}sum_{i-1}\times s3_{i-1}\\
\\
答案即为
((i-s1_i)s1_i+(i-s2_i)s2_i-s3_i)sum_i\times sump_i-(i-s1_i)sum_i\times s5_{i}-(i-s2_i)sum_i\times s6_{i}+sum_i\times s7_{i}
-((i-s1_i)s1_i+(i-s2_i)s2_i-s3_i)s4_{i}+(i-s1_i)s8_{i}+(i-s2_i)s9_{i}-s10_{i}
\\
$。
至于特殊输入的部分, 对 $2^{64}$ 取模可以用`unsigned long long` 自然溢出代替。
参考程序：
```cpp
#include<iostream>
using namespace std;
using ll=long long;
const ll N=1e6+10,mod=1e9+7;
ll sum[N],s1[N],s2[N],s3[N],s4[N],s5[N],s6[N],s7[N],s8[N],s9[N],s10[N];
ll p[N],sump[N];
bool a[N],b[N];
int n;
void init(bool op){
if(!op){
for(int i=1;i<=n;++i)
scanf("%d%d",&a[i],&b[i]);
return;
}
unsigned long long x1,y1,z1,f1,f2;
unsigned long long x2,y2,z2,g1,g2,tmp;
scanf("%llu%llu%llu%llu%llu",&x1,&y1,&z1,&f1,&f2);
scanf("%llu%llu%llu%llu%llu",&x2,&y2,&z2,&g1,&g2);
for(int i=0;i<=n/64;++i){
f1=f1*x1+f2*y1+z1;
swap(f1,f2);
for(int j=0;j<64;++j)
a[i*64+j+1]=(f2>>j)&1ull;
}
for(int i=0;i<=n/64;++i){
g1=g1*x2+g2*y2+z2;
swap(g1,g2);
for(int j=0;j<64;++j)
b[i*64+j+1]=(g2>>j)&1ull;
}
}
int main(){
int op;
cin>>n>>op;
init(op);
for(int i=1;i<=n;++i)sum[i]=sum[i-1]+(a[i]!=b[i]);
for(int i=1;i<=n;++i)s1[i]=s1[i-1]+(a[i]==0);
for(int i=1;i<=n;++i)s2[i]=s2[i-1]+(b[i]==1);
for(int i=1;i<=n;++i)s3[i]=(s3[i-1]+(b[i]==1)*(i-s2[i])+(a[i]==0)*(i-s1[i]))%mod;
p[0]=1;
for(int i=1;i<=n;++i)p[i]=p[i-1]*2ll%mod;
for(int i=1;i<=n;++i)sump[i]=(sump[i-1]+p[max(i-2,0)])%mod;
for(int i=1;i<=n;++i)s4[i]=(s4[i-1]+p[max(i-2,0)]*sum[i-1]%mod)%mod;
for(int i=1;i<=n;++i)s5[i]=(s5[i-1]+p[max(i-2,0)]*s1[i-1]%mod)%mod;
for(int i=1;i<=n;++i)s6[i]=(s6[i-1]+p[max(i-2,0)]*s2[i-1]%mod)%mod;
for(int i=1;i<=n;++i)s7[i]=(s7[i-1]+p[max(i-2,0)]*s3[i-1]%mod)%mod;
for(int i=1;i<=n;++i)s8[i]=(s8[i-1]+p[max(i-2,0)]*s1[i-1]%mod*sum[i-1]%mod)%mod;
for(int i=1;i<=n;++i)s9[i]=(s9[i-1]+p[max(i-2,0)]*s2[i-1]%mod*sum[i-1]%mod)%mod;
for(int i=1;i<=n;++i)s10[i]=(s10[i-1]+p[max(i-2,0)]*s3[i-1]%mod*sum[i-1]%mod)%mod;
ll ans=0;
for(ll i=1;i<=n;++i){
ll tmp=0;
tmp+=sump[i]*((i-s1[i])*s1[i]%mod+(i-s2[i])*s2[i]%mod-s3[i]+mod)%mod*sum[i];
tmp=(tmp-((i-s1[i])*s1[i]%mod+(i-s2[i])*s2[i]%mod-s3[i]+mod)%mod*s4[i]%mod+mod)%mod;
tmp=(tmp-(i-s1[i])*sum[i]%mod*s5[i]%mod+mod)%mod;
tmp=(tmp-(i-s2[i])*sum[i]%mod*s6[i]%mod+mod)%mod;
tmp=(tmp+sum[i]*s7[i]%mod)%mod;
tmp=(tmp+(i-s1[i])*s8[i]%mod)%mod;
tmp=(tmp+(i-s2[i])*s9[i]%mod)%mod;
tmp=(tmp-s10[i]%mod+mod)%mod;
ans+=p[max(n-i-1,0ll)]*tmp%mod;
ans%=mod;
}
cout<<ans;
return 0;
}
```
## $O(n)$ 100pts
显然开 $13$ 个 $5\times 10^7$ 的数组是会 CE，即使只开 $5$ 个也会 MLE，因此这里要用数代替数组，在统计的同时，更新前缀和数组。
上面代码中取模运算较多，需卡常，否则会 TLE，要合并一些取模运算。
参考程序：
```cpp
#include<iostream>
using namespace std;
using ll=long long;
const ll N=5e7+10,mod=1e9+7;
ll sum,s1,s2,s3,s4,s5,s6,s7,s8,s9,s10;
ll p[N],sump;
bool a[N],b[N];
int n;
bool read(){
char ch=getchar();
while(ch<'0'||ch>'1')ch=getchar();
return ch-'0';
}
void init(bool op){
if(!op){
for(int i=1;i<=n;++i){
a[i]=read();
b[i]=read();
}
return;
}
unsigned long long x1,y1,z1,f1,f2;
unsigned long long x2,y2,z2,g1,g2;
scanf("%llu%llu%llu%llu%llu",&x1,&y1,&z1,&f1,&f2);
scanf("%llu%llu%llu%llu%llu",&x2,&y2,&z2,&g1,&g2);
for(int i=0;i<=n/64;++i){
f1=f1*x1+f2*y1+z1;
swap(f1,f2);
for(int j=0;j<64;++j)
a[i*64+j+1]=(f2>>j)&1ull;
}
for(int i=0;i<=n/64;++i){
g1=g1*x2+g2*y2+z2;
swap(g1,g2);
for(int j=0;j<64;++j)
b[i*64+j+1]=(g2>>j)&1ull;
}
}
int main(){
int op;
cin>>n>>op;
init(op);
p[0]=1;
for(ll i=1;i<=n;++i)p[i]=(p[i-1]<<1ll)%mod;
ll ans=0;
for(ll i=1;i<=n;++i){
ll p1=p[max(i-2,0ll)],p2=p[max(i-2,0ll)]*sum%mod;
sump=(sump+p1)%mod;
s4=(s4+p2)%mod;
s5=(s5+p1*s1%mod)%mod;
s6=(s6+p1*s2%mod)%mod;
s7=(s7+p1*s3%mod)%mod;
s8=(s8+p2*s1%mod)%mod;
s9=(s9+p2*s2%mod)%mod;
s10=(s10+p2*s3%mod)%mod;
s1+=!a[i];
s2+=b[i];
s3=(s3+b[i]*(i-s2)+(!a[i])*(i-s1))%mod;
sum=sum+(a[i]!=b[i]);
ans+=p[max(n-i-1,0ll)]*(((i-s1)*s1%mod+(i-s2)*s2%mod-s3+mod)%mod*(sump*sum%mod-s4+mod)%mod+(sum*s7%mod-s10+mod)+(i-s1)*(s8-sum*s5%mod+mod)%mod+(i-s2)*(s9-sum*s6%mod+mod)%mod)%mod;
ans%=mod;
}
cout<<ans;
return 0;
}
```