Constrained Tower Moves

A variation of the Tower of Hanoi requires moving all disks in the order (1\rightarrow 2\rightarrow 3\rightarrow 1). Given (n) disks on peg (1), determine the number of moves (a) to transfer them all to peg (2), and (b) to peg (3), modulo (998244353). Multiple queries ask for the XOR-sum of all (a) and (b) after taking the modulus. Constraints: (T\le 1.2\times10^6), (n\le 10^{12}).

Manual enumeration for (n=1,2,3,4) gives:

• (n=1): (1, 2)
• (n=2): (5, 7)
• (n=3): (15, 21)
• (n=4): (43, 59)

The recurrence relations emerge: [ a_i = \begin{cases} 1 & i=1 \ 2b_{i-1}+1 & i>1 \end{cases} ] [ b_i = a_{i-1} + a_i + 1 ]

Build a transition matrix. Let vector ([a_i, b_i, 1]) multiply by (A) to produce ([a_{i+1}, b_{i+1}, 1]). Since (a_{i+1}=2b_i+1) and (b_{i+1}=a_i+2b_i+2), [ A = \begin{bmatrix} 0 & 1 & 0 \ 2 & 2 & 0 \ 1 & 2 & 1 \end{bmatrix} ]

Complexity (O(27,T\log n)) can be reduced by:

• Processing queries offline.
• Precomputing (A^{2^i}) for (i\in[0,40]).
• Manual loop unrolling and modular reduction optimizations.

Further simplification drops the third dimension. The recurrence can be captured with: [ \begin{bmatrix} a+1 & b+1 \end{bmatrix} \begin{bmatrix} 0 & 1 \ 2 & 2 \end{bmatrix} = \begin{bmatrix} (2b+1)+1 & (a+2b+2)+1 \end{bmatrix} ] The code below implements the (3\times 3) approach with optimizations.

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define ll long long
#define N 1200010
#define P 998244353
using namespace std;
ll read(){
    ll x=0,w=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*w;
}
int add(int x,int y){
    x+=y;
    return x>=P?x-P:x;
}
int md(ll x){
    return x>=P?x%P:x;
}
struct Mat{
    int a[3][3];
    Mat(){
        a[0][0]=a[0][1]=a[0][2]=0;
        a[1][0]=a[1][1]=a[1][2]=0;
        a[2][0]=a[2][1]=a[2][2]=0;
    }
    Mat operator*(const Mat &b)const{
        Mat c;
        c.a[0][0]=add(add(md(1ll*a[0][0]*b.a[0][0]),md(1ll*a[0][1]*b.a[1][0])),md(1ll*a[0][2]*b.a[2][0]));
        c.a[0][1]=add(add(md(1ll*a[0][0]*b.a[0][1]),md(1ll*a[0][1]*b.a[1][1])),md(1ll*a[0][2]*b.a[2][1]));
        c.a[0][2]=add(add(md(1ll*a[0][0]*b.a[0][2]),md(1ll*a[0][1]*b.a[1][2])),md(1ll*a[0][2]*b.a[2][2]));
        c.a[1][0]=add(add(md(1ll*a[1][0]*b.a[0][0]),md(1ll*a[1][1]*b.a[1][0])),md(1ll*a[1][2]*b.a[2][0]));
        c.a[1][1]=add(add(md(1ll*a[1][0]*b.a[0][1]),md(1ll*a[1][1]*b.a[1][1])),md(1ll*a[1][2]*b.a[2][1]));
        c.a[1][2]=add(add(md(1ll*a[1][0]*b.a[0][2]),md(1ll*a[1][1]*b.a[1][2])),md(1ll*a[1][2]*b.a[2][2]));
        c.a[2][0]=add(add(md(1ll*a[2][0]*b.a[0][0]),md(1ll*a[2][1]*b.a[1][0])),md(1ll*a[2][2]*b.a[2][0]));
        c.a[2][1]=add(add(md(1ll*a[2][0]*b.a[0][1]),md(1ll*a[2][1]*b.a[1][1])),md(1ll*a[2][2]*b.a[2][1]));
        c.a[2][2]=add(add(md(1ll*a[2][0]*b.a[0][2]),md(1ll*a[2][1]*b.a[1][2])),md(1ll*a[2][2]*b.a[2][2]));
        return c;
    }
}init,base,now,bs[50];
int m;ll q[N];
void qpow(ll b){
    int cnt=0;
    while(b){
        if(b&1)now=now*bs[cnt];
        cnt++,b>>=1;
    }
}
int ansa,ansb;
int main(){
    init.a[0][0]=init.a[0][2]=1,init.a[0][1]=2;
    base.a[2][0]=base.a[0][1]=base.a[2][2]=1;
    base.a[1][0]=base.a[1][1]=base.a[2][1]=2;
    bs[0]=base;
    for(int i=1;i<50;i++)bs[i]=bs[i-1]*bs[i-1];
    m=read();
    for(int i=1;i<=m;i++)q[i]=read();
    sort(q+1,q+1+m),q[0]=1;
    now=init;
    for(int i=1;i<=m;i++){
        qpow(q[i]-q[i-1]);
        ansa^=now.a[0][0],ansb^=now.a[0][1];
    }
    printf("%d %d\n",ansa,ansb);
    return 0;
}

Maximizing Cyclic Dot Products

Given an array (a_0,\dots,a_{n-1}) and (m) queries with parameter (k), rearrange (a) to maximize (\sum_{i=0}^{n-1} a_i \cdot a_{(i+k)\bmod n}).

Constraints: (2\le n\le 5000), (1\le m\le n), (0\le k<n), (1\le a_i\le 10^5).

A greedy strategy sorts (a) descending, then places elements into cycles determined by step (k). There are (\gcd(n,k)) independent cycles. The largest unplaced value is put at a position whose left/right neighbor at distance (k) is empty, prioritizing the side with the larger adjacent element if both are empty.

#include<bits/stdc++.h>
#define ll long long
#define N 5010
using namespace std;
int read(){
    int x=0,w=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*w;
}
int n,a[N];
int pos[N],gcd,now,res[N];
int gl(int x,int k){
    return (x-k+n)%n;
}
int gr(int x,int k){
    return (x+k)%n;
}
void solve(){
    int k=read();
    if(!k){
        ll ans=0;
        for(int i=0;i<n;i++)ans+=1ll*a[i]*a[i];
        printf("%lld\n",ans);
        return;
    }
    if(k*2==n){
        ll ans=0;
        for(int i=0;i<n/2;i++)
            ans+=2ll*a[i*2]*a[i*2+1];
        printf("%lld\n",ans);
        return;
    }
    memset(pos,-1,sizeof(pos)),memset(res,-1,sizeof(res));
    gcd=__gcd(k,n),now=n-1;
    for(int i=0,tp;i<gcd;i++){
        pos[now]=i,res[i]=now;
        tp=gl(pos[now],k),pos[now-1]=tp,res[tp]=now-1;
        now-=2;
        for(int j=3;j<=n/gcd;j++){
            tp=gl(pos[now+2],k);
            if(~res[tp])tp=gr(pos[now+2],k);
            pos[now]=tp,res[tp]=now--;
        }
    }
    ll ans=0;
    for(int i=0;i<n;i++)
        ans+=1ll*a[res[i]]*a[res[gr(i,k)]];
    printf("%lld\n",ans);
}
int main(){
    n=read();
    for(int i=0;i<n;i++)a[i]=read();
    sort(a,a+n);
    int T=read();
    while(T--)solve();
    return 0;
}

Distribution-Based Expected Ranking

For each (i\in[1,n]), (a_i) is a uniform random real number in ([l_i,r_i]). Compute the expected rank of (a_i), defined as the number of (j) with (a_j \ge a_i) (including (i) itself).

Constraints: (n\le 10^5), (1\le l_i < r_i \le 10^5).

Working directly on (\mathbb R) is avoidable by discretizing into unit intervals of length 1. Assign each whole interval ([x,x+1]) a weight equal to the probability density (1/(r-l)). For two intervals ([x,x+1]) and ([y,y+1]):

• If (x<y), the second contributes fully to the first.
• If (x=y), the contribution is half its weight.

Prefix sums over the allowable range do the rest. Subtract the self-contribution for the exact expected rank.

#include<bits/stdc++.h>
#define db double
#define N 100010
#define R 99999
using namespace std;
int read(){
    int x=0,w=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*w;
}
int n,_l[N],_r[N];
db s[N],s2[N],s3[N];
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        _l[i]=read(),_r[i]=read()-1;
        db w=1.0/(_r[i]-_l[i]+1);
        s[_r[i]]+=w,s[_l[i]-1]-=w;
    }
    for(int i=R;~i;i--)s[i]+=s[i+1];
    for(int i=R;~i;i--)s2[i]=s2[i+1]+s[i];
    for(int i=R;~i;i--)s3[i]=s3[i+1]+s2[i];
    for(int i=1,l,r;i<=n;i++){
        l=_l[i],r=_r[i];
        db ans=(s3[l+1]-s3[r+2]+(s2[l]-s2[r+1])/2.0)/(r-l+1);
        ans-=((r-l)/2.0+0.5)/(r-l+1);
        printf("%.10lf\n",ans+1);
    }
    return 0;
}