Khoa học

Nguồn: CF461C Appleman and a Sheet of Paper, độ khó 2200.

Nhận thấy rằng với các giá trị p ≤ floor(now/2), việc duy trì trực tiếp là hợp lệ về mặt độ phức tạp.

Trong trường hợp p > floor(now/2), việc đảo ngược nửa bên phải cũng đúng.

Do đó, ta duy trì một nhãn đảo ngược, thực hiện thao tác trực tiếp và cập nhật tổng đoạn, thời gian chạy là O(n log n).

Mã nguồn

const int N=2e5+5;
int sum[N*4],add[N*4];
void build(int p,int l,int r) {
    if(l==r) return sum[p]=1,void();
    int mid=(l+r)>>1;
    build(p*2,l,mid),build(p*2+1,mid+1,r);
    sum[p]=sum[p*2]+sum[p*2+1];
}
void update(int p,int l,int r,int x,int v) {
    if(l==r) {sum[p]+=v;return;}
    int mid=(l+r)>>1;
    if(x<=mid) update(p*2,l,mid,x,v);
    else update(p*2+1,mid+1,r,x,v);
    sum[p]=sum[p*2]+sum[p*2+1];
}
int query(int p,int l,int r,int x,int y) {
    if(x<=l&&r<=y) return sum[p];
    int mid=(l+r)>>1,ret=0;
    if(x<=mid) ret+=query(p*2,l,mid,x,y);
    if(y>mid) ret+=query(p*2+1,mid+1,r,x,y);
    return ret;
} 
int main() {
    int n,q;scanf("%d %d",&n,&q);
    build(1,1,n);int st=1,ed=n,OP=0;
    FOR(TTT,1,q) {
        int op,x,y,len=ed-st+1;
        scanf("%d %d",&op,&x);
        if(op==2) {
            scanf("%d",&y);
            int l=x,r=y-1;
            if(OP) l=len-l-1,r=len-r-1,swap(l,r);
            printf("%d\n",query(1,1,n,l+st,r+st));
        }
        else {
            int mid=(ed-st+1)/2;
            if(x<=mid) {
                if(!OP) {
                    int r=st+2*x-1,z;
                    FOR(i,1,x) z=query(1,1,n,st+i-1,st+i-1),update(1,1,n,r-i+1,z);
                    st=st+x;
                }
                else {
                    int l=ed-2*x+1,z;
                    FOR(i,1,x) z=query(1,1,n,ed-i+1,ed-i+1),update(1,1,n,l+i-1,z);
                    ed=ed-x;
                }
            }
            else {
                if(!OP) {
                    OP^=1;
                    x=ed-st+1-x;
                    int l=ed-2*x+1,z;
                    FOR(i,1,x) z=query(1,1,n,ed-i+1,ed-i+1),update(1,1,n,l+i-1,z);
                    ed=ed-x;
                }
                else {
                    OP^=1;
                    x=ed-st+1-x;
                    int r=st+2*x-1,z;
                    FOR(i,1,x) z=query(1,1,n,st+i-1,st+i-1),update(1,1,n,r-i+1,z);
                    st=st+x;
                }
            }
        }
    }
}

Dũng giả

Nguồn: AT code_festival_2017_quala_f Squeezing Slimes, độ khó 3091.

Đối với mỗi a_i, số bước tối thiểu để hợp lại là floor(log2(a_i)), nếu không phải lũy thừa của 2 thì cần thêm một bước nữa, và luôn có thể tạo ra số bước này.

Giả sử các phần tử độc lập, đáp án sẽ là tổng của tất cả floor(log2(a_i)). Tuy nhiên, hai phần tử có thể được xử lý cùng nhau, xét trường hợp này.

Giả sử đã có k thao tác trước đó, bây giờ muốn làm b_i = floor(log2(a_i)) lần. Phân tích từng trường hợp:

• Nếu k < b_i, phải bổ sung b_i - k thao tác.
• Nếu k > b_i, chỉ có thể chuyển từ k thao tác nhưng chỉ giữ lại b_i thao tác.

Chú ý kiểm tra trường hợp không phải lũy thừa của 2, độ phức tạp là O(n).

Mã nguồn

int main() {
    int n;
    ll cur=0,ans=0;
    n=read();
    FOR(i,1,n) {
        int x=read();
        int w=__lg(x),fl=0;
        if((1<<w)!=x) fl=1;
        if(cur<w) ans+=w-cur;
        if(cur>w) fl=0;
        cur=w;
        if(fl) ans++,cur++;
    }
    printf("%lld\n",ans);
}

Xuất kết quả

Nguồn: CF1418G Three Occurrences, độ khó 2500.

Duyệt điểm cuối phải r, xét duy trì các điểm đầu trái l có thể là đáp án.

Tách riêng từng màu, tìm tập hợp các điểm cuối hợp lệ cho mỗi màu, giao của tất cả các tập hợp chính là đáp án.

Ký hiệu pre_{x,c,k} là vị trí thứ k màu c phía sau x.

Phân loại theo màu tại r:

• Nếu màu tại r là col_r, cần chứa k phần tử màu này, tập hợp hợp lệ là (pre_{r,col_r,k+1}, pre_{r,col_r,k}].
• Nếu không phải, có thể chọn k hoặc không chọn, nên tập hợp hợp lệ là (pre_{r,x,1}, r].

Vì tập hợp hợp lệ của mỗi màu không giao nhau, có thể dùng cây phân đoạn để duy trì giá trị lớn nhất và số lượng, đạt O(n log n).

Mã nguồn

const int N=5e5+5;
int add[N*4];
struct node {int ma,cnt;} tr[N*4];
node operator + (node a,node b) {
    node ret;
    ret.ma=max(a.ma,b.ma),ret.cnt=0;
    if(ret.ma==a.ma) ret.cnt+=a.cnt;
    if(ret.ma==b.ma) ret.cnt+=b.cnt;
    return ret;
}
void pushadd(int p,int v) {add[p]+=v,tr[p].ma+=v;}
void pushdown(int p) {
    if(add[p]) {
        pushadd(p*2,add[p]),pushadd(p*2+1,add[p]);
        add[p]=0;
    }
}
void build(int p,int l,int r) {
    if(l==r) {tr[p].cnt=1;return;}
    int mid=(l+r)>>1;
    build(p*2,l,mid),build(p*2+1,mid+1,r);
    tr[p]=tr[p*2]+tr[p*2+1];
}
void update(int p,int l,int r,int x,int y,int v) {
    if(x>y) return;
    if(x<=l&&r<=y) return pushadd(p,v);
    int mid=(l+r)>>1;pushdown(p);
    if(x<=mid) update(p*2,l,mid,x,y,v);
    if(y>mid) update(p*2+1,mid+1,r,x,y,v);
    tr[p]=tr[p*2]+tr[p*2+1];
}
int id[N],col[N],pre[N],nxt[N],tmp[N],cur[N],colcnt;
int main() {
    int n,K;scanf("%d",&n);K=3;
    FOR(i,1,n) {
        scanf("%d",&col[i]);
        id[i]=++tmp[col[i]];
        if(tmp[col[i]]==1) cur[col[i]]=i,colcnt++;
    }
    build(1,1,n);
    FOR(i,1,n) tmp[i]=0;
    FOR(i,1,n) pre[i]=tmp[col[i]],tmp[col[i]]=i;
    FOR(i,1,n) tmp[i]=0;
    ROF(i,n,1) nxt[i]=tmp[col[i]],tmp[col[i]]=i;
    ll ans=0;
    FOR(i,1,n) {
        update(1,1,n,i,i,colcnt);
        update(1,1,n,pre[i]+1,i,-1);
        if(id[i]==K) update(1,1,n,1,cur[col[i]],1);
        if(id[i]>K) {
            int &pk=cur[col[i]];
            update(1,1,n,pre[pk]+1,pk,-1);
            update(1,1,n,pk+1,nxt[pk],1);
            pk=nxt[pk];
        }
        if(tr[1].ma==colcnt) ans+=tr[1].cnt;
    }
    printf("%lld\n",ans);
}

Thuật thuật

Nguồn: 「BJOI2019」勘破神机.

Xét m = 2 trước.

Khi m = 2, kết quả tương đương với ∑_{i=l}^r C(f_i, k), trong đó f_i là số Fibonacci.

Xét công thức:

[\begin{aligned} \sum_{n=l}^r \binom{f_n}{k} & = \sum_{n=l}^{r}\frac{f_n!}{(f_n-k)!k!}\ & = \frac{1}{k!}\sum_{n=l}^r f_{n}^{\underline{k}}\ & = \frac{1}{k!}\sum_{n=l}^r \sum_{i=0}^k (-1)^{k-i} \begin{bmatrix} k\i \end{bmatrix} f_n^i\ \end{aligned} ]

Sử dụng công thức tổng quát của f_k:

[f_n=\frac{5+\sqrt{5}}{10}(\frac{1+\sqrt{5}}{10})^n+\frac{5-\sqrt{5}}{10}(\frac{1-\sqrt{5}}{10})^n ]

Đặt f_n = Aα^n + Bβ^n, thế vào biểu thức:

[\begin{aligned} \frac{1}{k!}\sum_{n=l}^r \sum_{i=0}^k (-1)^{k-i} \begin{bmatrix} k\i \end{bmatrix} f_n^i & = \frac{1}{k!}\sum_{n=l}^r \sum_{i=0}^k (-1)^{k-i} \begin{bmatrix} k\i \end{bmatrix} (A\alpha^n+B\beta^n)^i\ & = \frac{1}{k!}\sum_{n=l}^r \sum_{i=0}^k (-1)^{k-i} \begin{bmatrix} k\i \end{bmatrix} \sum_{j=0}^i\binom{i}{j}A^j\alpha^{nj}B^{i-j}\beta^{n(i-j)}\ & = \frac{1}{k!}\sum_{i=0}^k(-1)^{k-i} \begin{bmatrix} k\i \end{bmatrix} \sum_{j=0}^i\binom{i}{j} A^iB^{i-j}\sum_{n=l}^r(\alpha^j\beta^{i-j})^n \end{aligned} ]

Biểu thức cuối là tổng cấp số nhân, có thể tính trực tiếp với độ phức tạp O(k^2 log r). Cần đặc biệt chú ý khi công bội bằng 1.

Do 5 không có căn bậc hai modulo 998244353, cần tự viết lớp số phức mở rộng.

Tiếp tục với m = 3, đây là bài toán tương tự, công thức đệ quy là g_i = 4g_{i-1} - g_{i-2}. Có thể dùng phương trình đặc trưng để tìm dạng Aα^n + Bβ^n, đạt cùng độ phức tạp.

Mã nguồn bỏ qua một vài chi tiết, có thể tham khảo code.

Mã nguồn

const int N=505,mod=998244353;
int inc(int x,int y) {x+=y;if(x>=mod) x-=mod;return x;}
void Inc(int &x,int y) {x+=y;if(x>=mod) x-=mod;}
int dec(int x,int y) {x-=y;if(x<0) x+=mod;return x;}
void Dec(int &x,int y) {x+=y;if(x<0) x-=mod;}
int mul(int x,int y) {return 1ll*x*y%mod;}
void Mul(int &x,int y) {x=1ll*x*y%mod;}
int fpow(int x,ll y) {
    int ret=1;
    for(;y;y>>=1) {
        if(y&1) Mul(ret,x);
        Mul(x,x);
    }
    return ret;
}
int inv(int x) {return fpow(x,mod-2);}
int V,C[N][N],S[N][N],fac[N],ifac[N];
struct Complex {
    int x,y;
    Complex operator + (const Complex &a) const {return {inc(x,a.x),inc(y,a.y)};}
    Complex operator - (const Complex &a) const {return {dec(x,a.x),dec(y,a.y)};}
    Complex operator * (const Complex &a) const {return {inc(mul(x,a.x),mul(V,mul(y,a.y))),inc(mul(x,a.y),mul(y,a.x))};}
    Complex operator * (const int &a) const {return {mul(x,a),mul(y,a)};}
} A,B,alph,bt;
Complex fpow(Complex x,ll y) {
    Complex ret={1,0};
    for(;y;y>>=1) {
        if(y&1) ret=ret*x;
        x=x*x;
    }
    return ret;
}
Complex inv(Complex a) {
    int tmp=dec(mul(a.x,a.x),mul(V,mul(a.y,a.y)));tmp=inv(tmp);return {mul(a.x,tmp),mod-mul(a.y,tmp)};
}
int main() {
    int T=read(),m=read();
    if(m==2) V=5;
    else V=3;
    S[1][1]=1;
    FOR(i,0,501) C[i][0]=1;
    FOR(i,1,501) FOR(j,1,i) C[i][j]=inc(C[i-1][j-1],C[i-1][j]);
    FOR(i,2,501) FOR(j,1,i) S[i][j]=dec(S[i-1][j-1],mul(i-1,S[i-1][j]));
    fac[0]=1,ifac[0]=1;
    FOR(i,1,501) fac[i]=mul(fac[i-1],i),ifac[i]=inv(fac[i]);
    if(m==2) A={inv(2),inv(10)},B={inv(2),mod-inv(10)},alph={inv(2),inv(2)},bt={inv(2),mod-inv(2)};
    else A={inv(2),inv(6)},B={inv(2),mod-inv(6)},alph={2,1},bt={2,mod-1};
    while(T--) {
        ll l=read(),r=read();int k=read();
        ll len=r-l+1;
        int ans=0;
        if(m==3) l=(l+1)>>1,r>>=1;
        ll L=r-l+1;
        FOR(i,1,k) {
            Complex tmp={0,0};
            FOR(j,0,i) {
                Complex a=fpow(A,j)*fpow(B,i-j),b=fpow(alph,j)*fpow(bt,i-j);
                Complex c=(fpow(b,L+1)-b)*inv(b-(Complex){1,0});
                if(b.x==1&&b.y==0) c=b*(L%mod);
                tmp=tmp+a*c*C[i][j]*fpow(b,l-1);
            }
            Inc(ans,mul(S[k][i],tmp.x));
        }
        printf("%d\n",mul(ans,mul(inv(len%mod),ifac[k])));
    }
}