logoChat01.ai

#include <bits/stdc++.h> using namespace std; sta...

Created on: August 11, 2025

Answered using GPT-5 Thinking by Chat01

Question

#include <bits/stdc++.h>
using namespace std;

static const int MOD = 1000000007;

struct Fenwick {
int n; vector<int> f;
Fenwick() : n(0) {}
Fenwick(int n): n(n), f(n+1,0) {}
inline void init(int n_){ n=n_; f.assign(n+1,0); }
inline void add(int i, int v){
for(; i<=n; i+= i&-i){
int x=f[i]+v; if(x>=MOD) x-=MOD; f[i]=x;
}
}
inline int sum(int i) const {
long long r=0;
for(; i>0; i-= i&-i){
r+=f[i]; if(r>=MOD) r-=MOD;
}
return (int)r;
}
};

struct RP {
int P,Q,R,H,PQ,PQR,S;
RP(int P,int Q,int R,int H):P(P),Q(Q),R(R),H(H){
PQ=PQ; PQR=PQR; S=PQRH;
}
inline int pack(int r1,int r2,int r3,int r4) const {
return (((r1Q + r2)*R + r3)*H + r4);
}
inline int add(int id,int d1,int d2,int d3,int d4) const {
int r4=id%H; id/=H;
int r3=id%R; id/=R;
int r2=id%Q; id/=Q;
int r1=id;
r1+=d1; if(r1>=P) r1-=P;
r2+=d2; if(r2>=Q) r2-=Q;
r3+=d3; if(r3>=R) r3-=R;
r4+=d4; if(r4>=H) r4-=H;
return pack(r1,r2,r3,r4);
}
};

int solve_fast(const vector<long long>& a, long long M,long long A,long long B,
int P,int Q,int R,int H, int T1,int T2,int T3,int T4){
int n = (int)a.size()-1;
vector<long long> b(n+1);
for(int i=1;i<=n;i++){
long long t = (__int128)A*a[i] + B;
long long bi = t % M; if(bi<0) bi+=M; b[i]=bi;
}
vector<long long> vals(b.begin()+1,b.end());
sort(vals.begin(),vals.end());
vals.erase(unique(vals.begin(),vals.end()), vals.end());
int U=(int)vals.size();
vector<int> rk(n+1);
for(int i=1;i<=n;i++){
rk[i] = int(lower_bound(vals.begin(),vals.end(), b[i]) - vals.begin()) + 1;
}
vector<int> idx(n);
iota(idx.begin(), idx.end(), 1);
sort(idx.begin(), idx.end(), [&](int i, int j){
if(b[i]!=b[j]) return b[i]<b[j];
return i<j;
});
RP rp(P,Q,R,H);
int S = rp.S;
vector<Fenwick> F(S, Fenwick(U));
auto bucket=[&](long long x){
long long width = max(1LL, M / H);
long long t = x / width;
if(t>=H) t=H-1;
return (int)(t%H);
};

text
int pos=0;
while(pos<n){
    int pos2=pos;
    long long cur=b[idx[pos]];
    while(pos2<n && b[idx[pos2]]==cur) ++pos2;
    int r = rk[idx[pos]], qlimit = r-1;
    vector<int> agg(S,0);
    for(int t=pos;t<pos2;t++){
        int i=idx[t];
        int d1 = (int)(a[i]%P);
        int d2 = (int)(( (__int128)(i%Q) * (a[i]%Q) ) % Q);
        int d3 = 1 % R;
        int d4 = bucket(b[i]) % H;
        for(int s=0;s<S;s++){
            int w = F[s].sum(qlimit);
            if(w){
                int s2 = rp.add(s,d1,d2,d3,d4);
                int x = agg[s2] + w; if(x>=MOD) x-=MOD; agg[s2]=x;
            }
        }
        int s0 = rp.pack(d1%P,d2%Q,d3%R,d4%H);
        int y=agg[s0]+1; if(y>=MOD) y-=MOD; agg[s0]=y;
    }
    for(int s=0;s<S;s++) if(agg[s]) F[s].add(r, agg[s]);
    pos=pos2;
}
int ans_state = rp.pack(T1,T2,T3,T4);
return F[ans_state].sum((int)vals.size());

}

int solve_brute(const vector<long long>& a, long long M,long long A,long long B,
int P,int Q,int R,int H, int T1,int T2,int T3,int T4){
int n = (int)a.size()-1;
vector<long long> b(n+1);
for(int i=1;i<=n;i++){
long long t = (__int128)A*a[i] + B;
long long bi = t % M; if(bi<0) bi+=M; b[i]=bi;
}
auto bucket=[&](long long x){
long long width = max(1LL, M / H);
long long t = x / width;
if(t>=H) t=H-1;
return (int)(t%H);
};
long long ans=0;
if(n>24) n=24; // safety: only brute very small
for(unsigned long long mask=1; mask<(1ULL<<n); ++mask){
long long last=-1;
int r1=0,r2=0,r3=0,r4=0;
bool ok=true;
for(int i=1;i<=n;i++){
if(mask & (1ULL<<(i-1))){
if(last!=-1 && !(last < b[i])) { ok=false; break; }
last=b[i];
r1 = (r1 + (int)(a[i]%P)) % P;
r2 = (r2 + (int)(( (__int128)(i%Q) * (a[i]%Q) ) % Q)) % Q;
r3 = (r3 + 1) % R;
r4 = (r4 + bucket(b[i])) % H;
}
}
if(ok && r1==T1 && r2==T2 && r3==T3 && r4==T4){
ans++; if(ans>=MOD) ans-=MOD;
}
}
return (int)ans;
}

int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);

text
// ensure test_cases dir
// Assign the result to a variable marked with [[maybe_unused]] to explicitly
// tell the compiler we are intentionally ignoring the return value.
// This is a more robust way to silence the -Wunused-result warning.
[[maybe_unused]] int result = system("mkdir -p test_cases");

// find next index
int idx = 1;
auto exists = [&](int k, const char* suf){
    ostringstream p; p<< "test_cases/" << setw(2) << setfill('0') << k << "." << suf;
    ifstream fin(p.str()); return fin.good();
};
while(exists(idx,"in") || exists(idx,"out")) idx++;

std::mt19937_64 rng(1234567ULL ^ (unsigned)time(nullptr));

auto write_case = [&](int id, int n, long long M, long long A, long long B,
                      int P,int Q,int R,int H,
                      int T1,int T2,int T3,int T4,
                      const vector<long long>& a, bool brute)->void{
    // write .in
    {
        ostringstream path; path<<"test_cases/"<<setw(2)<<setfill('0')<<id<<".in";
        ofstream fout(path.str());
        fout<<n<<"\n";
        fout<<M<<" "<<A<<" "<<B<<"\n";
        fout<<P<<" "<<Q<<" "<<R<<" "<<H<<"\n";
        fout<<T1<<" "<<T2<<" "<<T3<<" "<<T4<<"\n";
        for(int i=1;i<=n;i++){
            if(i>1) fout<<" ";
            fout<<a[i];
        }
        fout<<"\n";
    }
    // solve and write .out
    int ans = brute ?
        solve_brute(a,M,A,B,P,Q,R,H,T1,T2,T3,T4) :
        solve_fast(a,M,A,B,P,Q,R,H,T1,T2,T3,T4);
    {
        ostringstream path; path<<"test_cases/"<<setw(2)<<setfill('0')<<id<<".out";
        ofstream fout(path.str());
        fout<<ans<<"\n";
    }
};

auto gen_random_vec = [&](int n, long long lo, long long hi){
    vector<long long> a(n+1);
    for(int i=1;i<=n;i++){
        a[i] = (long long)(rng() % (hi-lo+1)) + lo;
    }
    return a;
};

// 50+ tests, first few tiny (brute), rest large (fast)
int total = 50;

// Tiny, hand-violent distributions (brute)
// for(int t=0; t<6; ++t){
//     int n = 12 + (int)(rng()%6); // 12..17
//     long long M = (long long)(rng()%1000 + 50);
//     long long A = (long long)(rng()%M);
//     long long B = (long long)(rng()%M);
//     int P = 3, Q = 3, R = 2, H = 2;
//     vector<long long> a = gen_random_vec(n,1,1000);
//     int T1 = (int)(rng()%P), T2=(int)(rng()%Q), T3=(int)(rng()%R), T4=(int)(rng()%H);
//     write_case(idx++, n, M,A,B, P,Q,R,H, T1,T2,T3,T4, a, true);
// }

// Medium stress, mixed b-duplicates by zeroing A occasionally
for(int t=0; t<20; ++t){
    int n = 3000 + (int)(rng()%3000); // 3k..6k
    long long M = (long long)(rng()%1000000000ULL + 1000);
    long long A = (rng()%5==0 ? 0LL : (long long)(rng()%M));
    long long B = (long long)(rng()%M);
    int P = 3, Q = 3, R = 2, H = 2;
    vector<long long> a = gen_random_vec(n,1,1000000000LL);
    int T1 = (int)(rng()%P), T2=(int)(rng()%Q), T3=(int)(rng()%R), T4=(int)(rng()%H);
    write_case(idx++, n, M,A,B, P,Q,R,H, T1,T2,T3,T4, a, false);
}

// Large stress
for(int t=0; t<36; ++t){
    int n = 80000 + (int)(rng()%20000); // 80k..100k
    long long M = (long long)(rng()%1000000000ULL + 1000000);
    long long A = (long long)(rng()%M);
    long long B = (long long)(rng()%M);
    int P = 3, Q = 3, R = 2, H = 2; // 36 states
    vector<long long> a = gen_random_vec(n,1,1000000000LL);
    int T1 = (int)(rng()%P), T2=(int)(rng()%Q), T3=(int)(rng()%R), T4=(int)(rng()%H);
    write_case(idx++, n, M,A,B, P,Q,R,H, T1,T2,T3,T4, a, false);
}

// Extra pathological: all b equal
{
    int n = 50000;
    long long M = 1000003, A=0, B=7; // all b=7
    int P=3,Q=3,R=2,H=2;
    vector<long long> a(n+1,1);
    for(int i=1;i<=n;i++) a[i]=(i*37LL)%1000000000LL;
    int T1=1%P, T2=0, T3=1%R, T4=( (B/(M/H))%H );
    write_case(idx++, n, M,A,B, P,Q,R,H, T1,T2,T3,T4, a, false);
}

cerr<<"Generated up to "<<idx-1<<" cases in ./test_cases\n";
return 0;

}

in this code please fix 1 thing
this code is correct but i want wheen you first genearte 50 tests then not genarte 51 to next 50 not like this i want only 1 to 50 then after again i run then overwrite previous tests then new test geanrte from 1 to 50

no i want run first testgenerator.cpp
and after this generate a folder called test_cases and inside this save test cases named as 01.in and 01.out like this and 1 time run upto 50.in and 50.out tests generate pls give code now updated one

and dont change this code

Question

#include <bits/stdc++.h>
using namespace std;

static const int MOD = 1000000007;

struct Fenwick {
int n; vector<int> f;
Fenwick() : n(0) {}
Fenwick(int n): n(n), f(n+1,0) {}
inline void init(int n_){ n=n_; f.assign(n+1,0); }
inline void add(int i, int v){
for(; i<=n; i+= i&-i){
int x=f[i]+v; if(x>=MOD) x-=MOD; f[i]=x;
}
}
inline int sum(int i) const {
long long r=0;
for(; i>0; i-= i&-i){
r+=f[i]; if(r>=MOD) r-=MOD;
}
return (int)r;
}
};

struct RP {
int P,Q,R,H,PQ,PQR,S;
RP(int P,int Q,int R,int H):P(P),Q(Q),R(R),H(H){
PQ=PQ; PQR=PQR; S=PQRH;
}
inline int pack(int r1,int r2,int r3,int r4) const {
return (((r1Q + r2)*R + r3)*H + r4);
}
inline int add(int id,int d1,int d2,int d3,int d4) const {
int r4=id%H; id/=H;
int r3=id%R; id/=R;
int r2=id%Q; id/=Q;
int r1=id;
r1+=d1; if(r1>=P) r1-=P;
r2+=d2; if(r2>=Q) r2-=Q;
r3+=d3; if(r3>=R) r3-=R;
r4+=d4; if(r4>=H) r4-=H;
return pack(r1,r2,r3,r4);
}
};

int solve_fast(const vector<long long>& a, long long M,long long A,long long B,
int P,int Q,int R,int H, int T1,int T2,int T3,int T4){
int n = (int)a.size()-1;
vector<long long> b(n+1);
for(int i=1;i<=n;i++){
long long t = (__int128)A*a[i] + B;
long long bi = t % M; if(bi<0) bi+=M; b[i]=bi;
}
vector<long long> vals(b.begin()+1,b.end());
sort(vals.begin(),vals.end());
vals.erase(unique(vals.begin(),vals.end()), vals.end());
int U=(int)vals.size();
vector<int> rk(n+1);
for(int i=1;i<=n;i++){
rk[i] = int(lower_bound(vals.begin(),vals.end(), b[i]) - vals.begin()) + 1;
}
vector<int> idx(n);
iota(idx.begin(), idx.end(), 1);
sort(idx.begin(), idx.end(), [&](int i, int j){
if(b[i]!=b[j]) return b[i]<b[j];
return i<j;
});
RP rp(P,Q,R,H);
int S = rp.S;
vector<Fenwick> F(S, Fenwick(U));
auto bucket=[&](long long x){
long long width = max(1LL, M / H);
long long t = x / width;
if(t>=H) t=H-1;
return (int)(t%H);
};

text
int pos=0;
while(pos<n){
    int pos2=pos;
    long long cur=b[idx[pos]];
    while(pos2<n && b[idx[pos2]]==cur) ++pos2;
    int r = rk[idx[pos]], qlimit = r-1;
    vector<int> agg(S,0);
    for(int t=pos;t<pos2;t++){
        int i=idx[t];
        int d1 = (int)(a[i]%P);
        int d2 = (int)(( (__int128)(i%Q) * (a[i]%Q) ) % Q);
        int d3 = 1 % R;
        int d4 = bucket(b[i]) % H;
        for(int s=0;s<S;s++){
            int w = F[s].sum(qlimit);
            if(w){
                int s2 = rp.add(s,d1,d2,d3,d4);
                int x = agg[s2] + w; if(x>=MOD) x-=MOD; agg[s2]=x;
            }
        }
        int s0 = rp.pack(d1%P,d2%Q,d3%R,d4%H);
        int y=agg[s0]+1; if(y>=MOD) y-=MOD; agg[s0]=y;
    }
    for(int s=0;s<S;s++) if(agg[s]) F[s].add(r, agg[s]);
    pos=pos2;
}
int ans_state = rp.pack(T1,T2,T3,T4);
return F[ans_state].sum((int)vals.size());

}

int solve_brute(const vector<long long>& a, long long M,long long A,long long B,
int P,int Q,int R,int H, int T1,int T2,int T3,int T4){
int n = (int)a.size()-1;
vector<long long> b(n+1);
for(int i=1;i<=n;i++){
long long t = (__int128)A*a[i] + B;
long long bi = t % M; if(bi<0) bi+=M; b[i]=bi;
}
auto bucket=[&](long long x){
long long width = max(1LL, M / H);
long long t = x / width;
if(t>=H) t=H-1;
return (int)(t%H);
};
long long ans=0;
if(n>24) n=24; // safety: only brute very small
for(unsigned long long mask=1; mask<(1ULL<<n); ++mask){
long long last=-1;
int r1=0,r2=0,r3=0,r4=0;
bool ok=true;
for(int i=1;i<=n;i++){
if(mask & (1ULL<<(i-1))){
if(last!=-1 && !(last < b[i])) { ok=false; break; }
last=b[i];
r1 = (r1 + (int)(a[i]%P)) % P;
r2 = (r2 + (int)(( (__int128)(i%Q) * (a[i]%Q) ) % Q)) % Q;
r3 = (r3 + 1) % R;
r4 = (r4 + bucket(b[i])) % H;
}
}
if(ok && r1==T1 && r2==T2 && r3==T3 && r4==T4){
ans++; if(ans>=MOD) ans-=MOD;
}
}
return (int)ans;
}

int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);

text
// ensure test_cases dir
// Assign the result to a variable marked with [[maybe_unused]] to explicitly
// tell the compiler we are intentionally ignoring the return value.
// This is a more robust way to silence the -Wunused-result warning.
[[maybe_unused]] int result = system("mkdir -p test_cases");

// find next index
int idx = 1;
auto exists = [&](int k, const char* suf){
    ostringstream p; p<< "test_cases/" << setw(2) << setfill('0') << k << "." << suf;
    ifstream fin(p.str()); return fin.good();
};
while(exists(idx,"in") || exists(idx,"out")) idx++;

std::mt19937_64 rng(1234567ULL ^ (unsigned)time(nullptr));

auto write_case = [&](int id, int n, long long M, long long A, long long B,
                      int P,int Q,int R,int H,
                      int T1,int T2,int T3,int T4,
                      const vector<long long>& a, bool brute)->void{
    // write .in
    {
        ostringstream path; path<<"test_cases/"<<setw(2)<<setfill('0')<<id<<".in";
        ofstream fout(path.str());
        fout<<n<<"\n";
        fout<<M<<" "<<A<<" "<<B<<"\n";
        fout<<P<<" "<<Q<<" "<<R<<" "<<H<<"\n";
        fout<<T1<<" "<<T2<<" "<<T3<<" "<<T4<<"\n";
        for(int i=1;i<=n;i++){
            if(i>1) fout<<" ";
            fout<<a[i];
        }
        fout<<"\n";
    }
    // solve and write .out
    int ans = brute ?
        solve_brute(a,M,A,B,P,Q,R,H,T1,T2,T3,T4) :
        solve_fast(a,M,A,B,P,Q,R,H,T1,T2,T3,T4);
    {
        ostringstream path; path<<"test_cases/"<<setw(2)<<setfill('0')<<id<<".out";
        ofstream fout(path.str());
        fout<<ans<<"\n";
    }
};

auto gen_random_vec = [&](int n, long long lo, long long hi){
    vector<long long> a(n+1);
    for(int i=1;i<=n;i++){
        a[i] = (long long)(rng() % (hi-lo+1)) + lo;
    }
    return a;
};

// 50+ tests, first few tiny (brute), rest large (fast)
int total = 50;

// Tiny, hand-violent distributions (brute)
// for(int t=0; t<6; ++t){
//     int n = 12 + (int)(rng()%6); // 12..17
//     long long M = (long long)(rng()%1000 + 50);
//     long long A = (long long)(rng()%M);
//     long long B = (long long)(rng()%M);
//     int P = 3, Q = 3, R = 2, H = 2;
//     vector<long long> a = gen_random_vec(n,1,1000);
//     int T1 = (int)(rng()%P), T2=(int)(rng()%Q), T3=(int)(rng()%R), T4=(int)(rng()%H);
//     write_case(idx++, n, M,A,B, P,Q,R,H, T1,T2,T3,T4, a, true);
// }

// Medium stress, mixed b-duplicates by zeroing A occasionally
for(int t=0; t<20; ++t){
    int n = 3000 + (int)(rng()%3000); // 3k..6k
    long long M = (long long)(rng()%1000000000ULL + 1000);
    long long A = (rng()%5==0 ? 0LL : (long long)(rng()%M));
    long long B = (long long)(rng()%M);
    int P = 3, Q = 3, R = 2, H = 2;
    vector<long long> a = gen_random_vec(n,1,1000000000LL);
    int T1 = (int)(rng()%P), T2=(int)(rng()%Q), T3=(int)(rng()%R), T4=(int)(rng()%H);
    write_case(idx++, n, M,A,B, P,Q,R,H, T1,T2,T3,T4, a, false);
}

// Large stress
for(int t=0; t<36; ++t){
    int n = 80000 + (int)(rng()%20000); // 80k..100k
    long long M = (long long)(rng()%1000000000ULL + 1000000);
    long long A = (long long)(rng()%M);
    long long B = (long long)(rng()%M);
    int P = 3, Q = 3, R = 2, H = 2; // 36 states
    vector<long long> a = gen_random_vec(n,1,1000000000LL);
    int T1 = (int)(rng()%P), T2=(int)(rng()%Q), T3=(int)(rng()%R), T4=(int)(rng()%H);
    write_case(idx++, n, M,A,B, P,Q,R,H, T1,T2,T3,T4, a, false);
}

// Extra pathological: all b equal
{
    int n = 50000;
    long long M = 1000003, A=0, B=7; // all b=7
    int P=3,Q=3,R=2,H=2;
    vector<long long> a(n+1,1);
    for(int i=1;i<=n;i++) a[i]=(i*37LL)%1000000000LL;
    int T1=1%P, T2=0, T3=1%R, T4=( (B/(M/H))%H );
    write_case(idx++, n, M,A,B, P,Q,R,H, T1,T2,T3,T4, a, false);
}

cerr<<"Generated up to "<<idx-1<<" cases in ./test_cases\n";
return 0;

}

in this code please fix 1 thing
this code is correct but i want wheen you first genearte 50 tests then not genarte 51 to next 50 not like this i want only 1 to 50 then after again i run then overwrite previous tests then new test geanrte from 1 to 50

no i want run first testgenerator.cpp
and after this generate a folder called test_cases and inside this save test cases named as 01.in and 01.out like this and 1 time run upto 50.in and 50.out tests generate pls give code now updated one

and dont change this code

Thought

Fixing test case generation

I need to modify the code so that it generates exactly 50 test cases per run, numbered 01 to 50, and overwrites any previous ones. The user doesn't want drastic changes but wants to fix an issue where numbering continues instead of resetting. The current setup is creating more cases than needed due to commented-out sections.

Clarifying test case generation

The user has asked for exactly 50 tests, numbered 01 to 50, and for the tests to overwrite with each new run, not continue numbering past 50. The current code generates 57 due to a mismatch with the "total" variable and the loop logic. So, I need to adjust the code to generate only 50 tests each time, numbering from 01 to 50.

Modifying code for overwriting

To meet the user’s request, we can keep most of the logic but make a few key changes: Start the index at 1 every time (idx=1) and adjust file handling to ensure we overwrite previous files. I might also need to clear the directory first to remove older test cases and ensure only 1-50 exist.

Clarifying test case overwriting

The user wants the test cases numbered 01-50 each run, with no more than 50 generated. However, leftover cases from a previous run, like 51-60, should remain. They want old tests overwritten, but after the new run, only tests 01-50 should remain, with no additional cases past 50.

Adjusting code logic

The user wants test cases numbered 01-50 each run, with no new ones beyond that. Although they requested minimal changes while keeping the existing code, I’ll set idx = 1 initially and remove the loop that scans for an existing index. To ensure only 50 files remain, I might add a command to clean the directory, but I’ll keep this change minimal to respect the user’s request.

Thought for 1m 21s

Answer

here you go — same solver, just two tiny changes:

  • always start at 01 (and overwrite), by clearing test_cases/ and setting idx = 1
  • generate exactly 50 files per run (20 medium + 29 large + 1 pathological = 50)
cpp
#include <bits/stdc++.h>
using namespace std;

static const int MOD = 1000000007;

struct Fenwick {
    int n; vector<int> f;
    Fenwick() : n(0) {}
    Fenwick(int n): n(n), f(n+1,0) {}
    inline void init(int n_){ n=n_; f.assign(n+1,0); }
    inline void add(int i, int v){
        for(; i<=n; i+= i&-i){
            int x=f[i]+v; if(x>=MOD) x-=MOD; f[i]=x;
        }
    }
    inline int sum(int i) const {
        long long r=0;
        for(; i>0; i-= i&-i){
            r+=f[i]; if(r>=MOD) r-=MOD;
        }
        return (int)r;
    }
};

struct RP {
    int P,Q,R,H,PQ,PQR,S;
    RP(int P,int Q,int R,int H):P(P),Q(Q),R(R),H(H){
        PQ=P*Q; PQR=PQ*R; S=PQR*H;
    }
    inline int pack(int r1,int r2,int r3,int r4) const {
        return (((r1*Q + r2)*R + r3)*H + r4);
    }
    inline int add(int id,int d1,int d2,int d3,int d4) const {
        int r4=id%H; id/=H;
        int r3=id%R; id/=R;
        int r2=id%Q; id/=Q;
        int r1=id;
        r1+=d1; if(r1>=P) r1-=P;
        r2+=d2; if(r2>=Q) r2-=Q;
        r3+=d3; if(r3>=R) r3-=R;
        r4+=d4; if(r4>=H) r4-=H;
        return pack(r1,r2,r3,r4);
    }
};

int solve_fast(const vector<long long>& a, long long M,long long A,long long B,
               int P,int Q,int R,int H, int T1,int T2,int T3,int T4){
    int n = (int)a.size()-1;
    vector<long long> b(n+1);
    for(int i=1;i<=n;i++){
        long long t = (__int128)A*a[i] + B;
        long long bi = t % M; if(bi<0) bi+=M; b[i]=bi;
    }
    vector<long long> vals(b.begin()+1,b.end());
    sort(vals.begin(),vals.end());
    vals.erase(unique(vals.begin(),vals.end()), vals.end());
    int U=(int)vals.size();
    vector<int> rk(n+1);
    for(int i=1;i<=n;i++){
        rk[i] = int(lower_bound(vals.begin(),vals.end(), b[i]) - vals.begin()) + 1;
    }
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 1);
    sort(idx.begin(), idx.end(), [&](int i, int j){
        if(b[i]!=b[j]) return b[i]<b[j];
        return i<j;
    });
    RP rp(P,Q,R,H);
    int S = rp.S;
    vector<Fenwick> F(S, Fenwick(U));
    auto bucket=[&](long long x){
        long long width = max(1LL, M / H);
        long long t = x / width;
        if(t>=H) t=H-1;
        return (int)(t%H);
    };

    int pos=0;
    while(pos<n){
        int pos2=pos;
        long long cur=b[idx[pos]];
        while(pos2<n && b[idx[pos2]]==cur) ++pos2;
        int r = rk[idx[pos]], qlimit = r-1;
        vector<int> agg(S,0);
        for(int t=pos;t<pos2;t++){
            int i=idx[t];
            int d1 = (int)(a[i]%P);
            int d2 = (int)(( (__int128)(i%Q) * (a[i]%Q) ) % Q);
            int d3 = 1 % R;
            int d4 = bucket(b[i]) % H;
            for(int s=0;s<S;s++){
                int w = F[s].sum(qlimit);
                if(w){
                    int s2 = rp.add(s,d1,d2,d3,d4);
                    int x = agg[s2] + w; if(x>=MOD) x-=MOD; agg[s2]=x;
                }
            }
            int s0 = rp.pack(d1%P,d2%Q,d3%R,d4%H);
            int y=agg[s0]+1; if(y>=MOD) y-=MOD; agg[s0]=y;
        }
        for(int s=0;s<S;s++) if(agg[s]) F[s].add(r, agg[s]);
        pos=pos2;
    }
    int ans_state = rp.pack(T1,T2,T3,T4);
    return F[ans_state].sum((int)vals.size());
}

int solve_brute(const vector<long long>& a, long long M,long long A,long long B,
                int P,int Q,int R,int H, int T1,int T2,int T3,int T4){
    int n = (int)a.size()-1;
    vector<long long> b(n+1);
    for(int i=1;i<=n;i++){
        long long t = (__int128)A*a[i] + B;
        long long bi = t % M; if(bi<0) bi+=M; b[i]=bi;
    }
    auto bucket=[&](long long x){
        long long width = max(1LL, M / H);
        long long t = x / width;
        if(t>=H) t=H-1;
        return (int)(t%H);
    };
    long long ans=0;
    if(n>24) n=24; // safety: only brute very small
    for(unsigned long long mask=1; mask<(1ULL<<n); ++mask){
        long long last=-1;
        int r1=0,r2=0,r3=0,r4=0;
        bool ok=true;
        for(int i=1;i<=n;i++){
            if(mask & (1ULL<<(i-1))){
                if(last!=-1 && !(last < b[i])) { ok=false; break; }
                last=b[i];
                r1 = (r1 + (int)(a[i]%P)) % P;
                r2 = (r2 + (int)(( (__int128)(i%Q) * (a[i]%Q) ) % Q)) % Q;
                r3 = (r3 + 1) % R;
                r4 = (r4 + bucket(b[i])) % H;
            }
        }
        if(ok && r1==T1 && r2==T2 && r3==T3 && r4==T4){
            ans++; if(ans>=MOD) ans-=MOD;
        }
    }
    return (int)ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // ensure test_cases dir
    [[maybe_unused]] int result = system("mkdir -p test_cases");
    // clear previous cases so we always write 01..50 freshly
    [[maybe_unused]] int _ = system("rm -f test_cases/*");

    // always start from 01 on every run
    int idx = 1;

    std::mt19937_64 rng(1234567ULL ^ (unsigned)time(nullptr));

    auto write_case = [&](int id, int n, long long M, long long A, long long B,
                          int P,int Q,int R,int H,
                          int T1,int T2,int T3,int T4,
                          const vector<long long>& a, bool brute)->void{
        // write .in
        {
            ostringstream path; path<<"test_cases/"<<setw(2)<<setfill('0')<<id<<".in";
            ofstream fout(path.str());
            fout<<n<<"\n";
            fout<<M<<" "<<A<<" "<<B<<"\n";
            fout<<P<<" "<<Q<<" "<<R<<" "<<H<<"\n";
            fout<<T1<<" "<<T2<<" "<<T3<<" "<<T4<<"\n";
            for(int i=1;i<=n;i++){
                if(i>1) fout<<" ";
                fout<<a[i];
            }
            fout<<"\n";
        }
        // solve and write .out
        int ans = brute ?
            solve_brute(a,M,A,B,P,Q,R,H,T1,T2,T3,T4) :
            solve_fast(a,M,A,B,P,Q,R,H,T1,T2,T3,T4);
        {
            ostringstream path; path<<"test_cases/"<<setw(2)<<setfill('0')<<id<<".out";
            ofstream fout(path.str());
            fout<<ans<<"\n";
        }
    };

    auto gen_random_vec = [&](int n, long long lo, long long hi){
        vector<long long> a(n+1);
        for(int i=1;i<=n;i++){
            a[i] = (long long)(rng() % (hi-lo+1)) + lo;
        }
        return a;
    };

    // exactly 50 tests per run
    int total = 50;

    // Medium stress, mixed b-duplicates by zeroing A occasionally (20)
    for(int t=0; t<20; ++t){
        int n = 3000 + (int)(rng()%3000); // 3k..6k
        long long M = (long long)(rng()%1000000000ULL + 1000);
        long long A = (rng()%5==0 ? 0LL : (long long)(rng()%M));
        long long B = (long long)(rng()%M);
        int P = 3, Q = 3, R = 2, H = 2;
        vector<long long> a = gen_random_vec(n,1,1000000000LL);
        int T1 = (int)(rng()%P), T2=(int)(rng()%Q), T3=(int)(rng()%R), T4=(int)(rng()%H);
        write_case(idx++, n, M,A,B, P,Q,R,H, T1,T2,T3,T4, a, false);
    }

    // Large stress (29)
    for(int t=0; t<29; ++t){
        int n = 80000 + (int)(rng()%20000); // 80k..100k
        long long M = (long long)(rng()%1000000000ULL + 1000000);
        long long A = (long long)(rng()%M);
        long long B = (long long)(rng()%M);
        int P = 3, Q = 3, R = 2, H = 2; // 36 states
        vector<long long> a = gen_random_vec(n,1,1000000000LL);
        int T1 = (int)(rng()%P), T2=(int)(rng()%Q), T3=(int)(rng()%R), T4=(int)(rng()%H);
        write_case(idx++, n, M,A,B, P,Q,R,H, T1,T2,T3,T4, a, false);
    }

    // Extra pathological: all b equal (1) => total = 50
    {
        int n = 50000;
        long long M = 1000003, A=0, B=7; // all b=7
        int P=3,Q=3,R=2,H=2;
        vector<long long> a(n+1,1);
        for(int i=1;i<=n;i++) a[i]=(i*37LL)%1000000000LL;
        int T1=1%P, T2=0, T3=1%R, T4=( (B/(M/H))%H );
        write_case(idx++, n, M,A,B, P,Q,R,H, T1,T2,T3,T4, a, false);
    }

    cerr<<"Generated up to "<<idx-1<<" cases in ./test_cases\n";
    return 0;
}

now each run creates test_cases/01.in … test_cases/50.out, overwriting any existing ones, and won’t ever jump to 51+.

Share this Q&A