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

· · 题解

前言

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

思路

首先很能得出一个 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;
}