专栏文章

题解：P11891 [XRCOI Round 1] B. 稻花香里说丰年

22672434062xzl
P11891题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipvspji
此快照首次捕获于
2025/12/03 18:45
3 个月前
此快照最后确认于
2025/12/03 18:45
3 个月前
查看原文

O(n2)O(n^2) 15pts

对于 T(l,r)T(l,r) 可采用前缀和的方法。
设 sumn=∑i=1n[ai≠bi]sum_n=\sum_{i=1}^{n} [a_i\ne b_i],T(l,r)=sumr−suml−1T(l,r)=sum_r-sum_{l-1}。
对于 A(l,r)A(l,r) 在 [l,r][l,r] 中的 00 统计其后有多少 11，所以 A(l,r)=∑i=lr([ai=0]×∑j=i+1r[aj=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)=∑i=lr([bi=1]×∑j=i+1r[bj=0])B(l,r)=\sum_{i=l}^{r} \left ( [b_i=1]\times \sum_{j=i+1}^{r}[b_j=0] \right )。
二者皆可以用前缀和优化，设 s1n=∑i=1n[ai=0]s1_n=\sum_{i=1}^{n}[a_i=0]，则 A(l,r)=∑i=lr([ai=0]×(r−s1r−i+s1i))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=1n((i−s1i)s1i+(i−s2i)s2i−s3i)sumi×sumpi−(i−s1i)sumi×s5i−(i−s2i)sumi×s6i+sumi×s7i−((i−s1i)s1i+(i−s2i)s2i−s3i)s4i+(i−s1i)s8i+(i−s2i)s9i−s10i\sum_{i=1}^n ((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} \\ 。
至于特殊输入的部分, 对 2642^{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)O(n) 100pts

显然开 1313 个 5×1075\times 10^7 的数组是会 CE，即使只开 55 个也会 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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...