Optimizing Prefix Sum Calculations

When determining the height configuration of vertical light beams (forming a non-increasing sequence), the state of horizontal beams can be uniquely determined.

By incrementally adding horizontal light beams, the dynamic programming recurrence takes the form of a prefix sum calculation.

This leads to an elegant 80-point solution:

#include <cstdio>
#include <algorithm>
using namespace std;

int read(){
    char c=getchar();int x=0;
    while(c<48||c>57) c=getchar();
    do x=(x<<1)+(x<<3)+(c^48),c=getchar();
    while(c>=48&&c<=57);
    return x;
}

const int MAX_N=503, MOD=998244353;
int rows, cols, result;
int heights[MAX_N];

void add_mod(int &x,int v){if((x+=v)>=MOD) x-=MOD;}

int prefix_sum[1000003];

int main(){
    rows=read(); cols=read();
    for(int i=1;i<=cols;++i) heights[i]=min(read(), rows);
    prefix_sum[0]=1;
    for(int i=1;i<=cols;++i)
        for(int j=1;j<=heights[i];++j) add_mod(prefix_sum[j], prefix_sum[j-1]);
    for(int i=0;i<=rows;++i) add_mod(result, prefix_sum[i]);
    printf("%d\n",result);
    return 0;
}

This approach effectively computes prefix sums on a langth 10^9 array and retrieves specific elements.

For optimization, we maintain a data structure supporting: array-wide prefix sum operations, element queries, and uniform value additions.

For polynomial function f representing sequence {f(0),f(1),f(2)...}, we construct:

[f(x)=\sum_{i=0}^{k} c_i{x+i \choose i} ]

After prefix sum:

[g(x)=\sum_{i=1}^{k+1} c_{i-1} {x+i \choose i} ]

This shifts all coefficients right by one position. Uniform addition is achieved via (c_0\leftarrow c_0+value).

Segmenting the sequence by value ranges and maintaining this structure per segment enables fast prefix sum computation.

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

int read(){
    char c=getchar();int x=0;
    while(c<48||c>57) c=getchar();
    do x=(x<<1)+(x<<3)+(c^48),c=getchar();
    while(c>=48&&c<=57);
    return x;
}

const int LIMIT=504, PRIME=998244353;
int dimension, count;
int values[LIMIT], sorted_vals[LIMIT];
int modular_inverse[LIMIT];

struct polynomial{
    int coefficients[LIMIT], degree;
    void shift_right(int x){
        for(int i=++degree;i;--i) coefficients[i]=coefficients[i-1];
        coefficients[0]=x;
    }
    void initialize(){coefficients[degree=0]=0;}
    int evaluate(int x){
        int term=1;
        ll res=0;
        for(int i=0;i<=degree;++i){
            res+=(ll)coefficients[i]*term%PRIME;
            term=(ll)term*modular_inverse[i+1]%PRIME*(x+i+1)%PRIME;
        }
        return res%PRIME;
    }
} segments[LIMIT];

int main(){
    dimension=read(); count=read(); modular_inverse[1]=1;
    for(int i=1;i<=count;++i) sorted_vals[i]=values[i]=min(read(), dimension);
    for(int i=2;i<=count+2;++i) modular_inverse[i]=(ll)modular_inverse[PRIME%i]*(PRIME-PRIME/i)%PRIME;
    sorted_vals[count+1]=dimension; sort(sorted_vals+1, sorted_vals+count+2);
    int unique_count=unique(sorted_vals+1, sorted_vals+count+2)-sorted_vals-1;
    for(int i=1;i<=unique_count;++i) segments[i].initialize();
    for(int i=1;i<=count;++i){
        int initial=1;
        for(int j=1;j<=unique_count;++j){
            if(values[i]<sorted_vals[j]) continue;
            segments[j].shift_right(initial);
            initial=segments[j].evaluate(sorted_vals[j]-sorted_vals[j-1]-1);
        }
    }
    ll total=1;
    for(int i=1;i<=unique_count;++i){
        segments[i].shift_right(0);
        total+=segments[i].evaluate(sorted_vals[i]-sorted_vals[i-1]-1);
    }
    printf("%d\n",int(total%PRIME));
    return 0;
}

Modular Subset Sum Selection

This problem requires selecting n elements from 2n-1 numbers such that their sum equals 0 modulo n.

When an absolute majority exists, output n identical elements. Otherwise, pair indices with distinct values.

Through induction, selecting the most frequent element maintains validity. Using a heap simplifies implementation.

We strengthen constraints by selecting one element per pair, including isolated elements, checking feasibility.

Transform by choosing arbitrary elements from each pair, then adding the difference between alternatives to an array. This creates n-1 non-zero elements requiring a subset sum of target_value modulo n.

For the classic modular subset problem with small modulus:

Let S_i rperesent reachable subset sums modulo n from first i elements. When S_{i-1} is not universal, |S_{i-1}|<|S_i|. Starting with |S_0|=1, S_{n-1} becomes universal.

Proof by contradiction: If |S_{i-1}|=|S_i|, then ∀x∈S_{i-1}, x+a_i∈S_{i-1}, implying ∀k∈[0,n-1], x+ka_i∈S_{i-1}. Since n is prime, ka_i forms a complete residue system, making S_{i-1} universal.

In competitive programming terms, each new element sets at least one new position to 1 in the DP array. Using bitset achieves 90 points.

Better properties exist: cyclic shifts followed by bitwise OR operations create equal numbers of 0↔1 and 1↔0 transitions. Finding differing positions and applying OR operations maintains complexity.

Dynamic maintenance uses data structures tracking interval hashes with jumps. Implemented with Fenwick tree + binary search (double logarithmic), though single logarithmic approaches exist.

Construction: Given element x, find any value v not in current modular subset. Consider chain 0→x→2x mod n→3x mod n→...→v. Binary search locates 1→0 transition with single logarithmic complexity.

For composite n, the Erdős–Ginzburg–Ziv theorem applies. For n=ab, find a elements summing to multiple of a, remove them until a-1 remain. This creates 2b-1 groups, from which b groups sum to multiple of ab.

#include <cstdio>
#include <vector>
#include <algorithm>
#pragma GCC optimize(2,3,"Ofast")
using namespace std;

int read(){
    char c=getchar();int x=0;
    while(c<48||c>57) c=getchar();
    do x=(x<<1)+(x<<3)+(c^48),c=getchar();
    while(c>=48&&c<=57);
    return x;
}

const int MAX_SIZE=600003, MODULUS=998244353;
typedef long long ll;
int n_elements, limit;
int powers[MAX_SIZE], prefix[MAX_SIZE];
bool reachable[MAX_SIZE], solution[MAX_SIZE];

struct hash_sequence{
    int tree[MAX_SIZE];
    void update(int x){
        for(int i=x+1;i<=limit;i+=(i&-i))
            ((tree[i]+=powers[x])>=MODULUS)&&(tree[i]-=MODULUS);
        for(int i=x+n_elements+1;i<=limit;i+=(i&-i))
            ((tree[i]+=powers[x+n_elements])>=MODULUS)&&(tree[i]-=MODULUS);
    }
    int calculate(int l,int r){
        int res=0;
        for(int i=r+1;i;i^=(i&-i))
            ((res+=tree[i])>=MODULUS)&&(res-=MODULUS);
        for(int i=l;i;i^=(i&-i))
            ((res-=tree[i])<0)&&(res+=MODULUS);
        return res;
    }
} current;

int elements[MAX_SIZE], temp[MAX_SIZE], first_idx[MAX_SIZE], second_idx[MAX_SIZE];
int stack[MAX_SIZE], top;
vector<int> groups[MAX_SIZE], size_lists[MAX_SIZE];
int max_size, second_max;

void add_back(int x){
    if(groups[x].empty()) return;
    size_lists[groups[x].size()].emplace_back(x);
}

int pop_maximum(){
    while(max_size&&size_lists[max_size].empty()) --max_size;
    int p=size_lists[max_size].back();size_lists[max_size].pop_back();
    int x=groups[p].back();groups[p].pop_back();
    return x;
}

int pop_second_max(){
    if(second_max>max_size) second_max=max_size;
    while(second_max&&size_lists[second_max].empty()) --second_max;
    int p=size_lists[second_max].back();size_lists[second_max].pop_back();
    int x=groups[p].back();groups[p].pop_back();
    return x;
}

int main(){
    n_elements=read(); limit=n_elements+n_elements; second_max=max_size=n_elements-1; powers[0]=1;
    for(int i=1;i<=limit;++i) powers[i]=powers[i-1]*2ll%MODULUS;
    for(int i=1;i<limit;++i) groups[elements[i]=read()].emplace_back(i);
    for(int i=0;i<n_elements;++i){
        if(int(groups[i].size())>=n_elements){
            for(int t=0;t<n_elements;++t) printf("%d ",groups[i][t]);
            putchar('\n');
            return 0;
        }
        add_back(i);
    }
    int total=0;
    for(int i=1;i<n_elements;++i){
        int x=pop_maximum(), y=pop_second_max();
        if(elements[x]>elements[y]) swap(x,y);
        add_back(elements[x]); add_back(elements[y]);
        first_idx[i]=x; second_idx[i]=y;
        temp[i]=elements[y]-elements[x];
        ((total-=elements[x])<0)&&(total+=n_elements);
    }
    int isolated=pop_maximum();
    ((total-=elements[isolated])<0)&&(total+=n_elements);
    printf("%d ",isolated);
    if(!total){
        for(int i=1;i<n_elements;++i) printf("%d ",first_idx[i]);
        putchar('\n');
        return 0;
    }
    current.update(0); reachable[0]=reachable[n_elements]=1;
    for(int round=1;round<n_elements;++round){
        int x=0,diff=temp[round];
        while(x<=n_elements){
            int l=x,r=n_elements;
            while(l<r){
                int mid=(l+r)>>1;
                if(current.calculate(x+diff,mid+diff)%MODULUS==(ll)powers[diff]*current.calculate(x,mid)%MODULUS) l=mid+1;
                else r=mid;
            }
            x=l;
            if(x>=n_elements) break;
            if(reachable[x]&&!reachable[x+diff]) stack[++top]=x+diff;
            ++x;
        }
        while(top){
            int pos=stack[top--];
            if(pos>=n_elements) pos-=n_elements;
            reachable[pos]=reachable[pos+n_elements]=1;
            prefix[pos]=round; current.update(pos);
            if(pos==total){
                while(pos){solution[prefix[pos]]=1;((pos-=temp[prefix[pos]])<0)&&(pos+=n_elements);}
                for(int i=1;i<n_elements;++i)
                    if(solution[i]) printf("%d ",second_idx[i]);
                    else printf("%d ",first_idx[i]);
                putchar('\n');
                return 0;
            }
        }
    }
    return 0;
}

Single logarithmic implementation:

#include <cstdio>
#include <bitset>
#include <algorithm>
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin)),p1==p2?EOF:*p1++)
using namespace std;

char buf[1<<21],*p1=buf,*p2=buf;
typedef long long ll;
typedef __int128 lll;

int read(){
    int c=getchar();int x=0;
    while(c<48||c>57) c=getchar();
    do x=(x<<1)+(x<<3)+(c^48),c=getchar();
    while(c>=48&&c<=57);
    return x;
}

const int MAX_N=300003;
int n;
int values[MAX_N<<1],positions[MAX_N<<1];bool present[MAX_N];
int predecessors[MAX_N],previous[MAX_N],inverses[MAX_N];
bool result_flags[MAX_N];
ll multiplier;

inline int modulo_reduction(ll x){
    x-=(((lll)x*multiplier)>>64)*n;
    return x>=n?x-n:x;
}

int main(){
    n=read(); multiplier=((lll)1<<64)/n;
    for(int i=1;i<n+n;++i) values[i]=read(), positions[i]=i;
    sort(positions+1, positions+n+n, [](int x,int y){return values[x]<values[y];});
    for(int i=1,j=1;i<n+n;i=j){
        while(j<n+n&&values[positions[i]]==values[positions[j]]) ++j;
        if(j-i>=n){
            for(int t=0;t<n;++t) printf("%d ",positions[i+t]);
            putchar('\n');
            return 0;
        }
    }
    int sum=0,t=0;
    for(int i=1;i<=n;++i){sum+=values[positions[i]];if(sum>=n) sum-=n;}
    if(sum) sum=n-sum;
    inverses[1]=1;
    for(int i=2;i<n;++i) inverses[i]=modulo_reduction((ll)inverses[n%i]*(n-n/i));
    present[0]=1;
    for(int i=1;!present[sum]&&i<n;++i){
        int diff=values[positions[i+n]]-values[positions[i]];
        if(diff<0) diff+=n;
        while(t<n&&present[t]) ++t;
        int l=0,r=modulo_reduction((ll)t*inverses[diff]);
        while(l+1<r){
            int mid=(l+r)>>1;
            if(present[modulo_reduction((ll)mid*diff)]) l=mid;
            else r=mid;
        }
        int pos=modulo_reduction((ll)r*diff);
        predecessors[pos]=i; present[pos]=1;
        if(pos>=diff) previous[pos]=pos-diff;
        else previous[pos]=pos-diff+n;
    }
    int x=sum;
    while(x){result_flags[predecessors[x]]=1;x=previous[x];}
    for(int i=1;i<=n;++i)
        if(result_flags[i]) printf("%d ",positions[i+n]);
        else printf("%d ",positions[i]);
    putchar('\n');
    return 0;
}