题解归档 - cf2226F

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2226F
• 本地来源：problems/cf2226F/idea.md
• 题目链接：https://codeforces.com/contest/2226/problem/F
• 原始标题：cf2226F - Inversion Invasion

思路

cf2226F - Inversion Invasion

Pattern: group by gcd(value, n) and multiply valid count by expected inversions.

Groups:

• For each divisor d | n, let G_d = {v : gcd(v, n) = d}.
• |G_d| = phi(n/d).
• If fixed[d] positions are constrained to group d, remaining free values in that group are rem[d] = |G_d| - fixed[d].
• If any rem[d] < 0, no valid permutation exists forever.

Number of valid permutations:

• Let R be the number of free positions.
• Free positions choose group labels with counts rem[d], and each group value set is permuted internally.
• ways = R! * prod |G_d|! / prod rem[d]!.
• After fixing one more position to group x, ways *= rem[x] / R.

Inversion expectation:

• Precompute w[a][b]: probability that a random value from group a is greater than a random value from group b.
• For a != b, count ordered cross-group pairs by sweeping values from low to high.
• For a == b, w[a][a] = 1/2.

Expected inversion sum is split into:

• fixed-fixed pairs: deterministic group labels, maintained incrementally.
• fixed-free pairs: for each fixed group a, keep total free positions before/after those fixed positions.
• free-free pairs: if S = sum_a sum_b rem[a] * (rem[b] - [a=b]) * w[a][b], contribution is S / 2.

Dynamic update for query (pos, x):

• Query how many already-fixed positions of every group are before pos.
• Add the new fixed-fixed contribution.
• Remove pos from the free side of existing fixed-free pairs.
• Add pos as a fixed position with its current free-before/free-after counts.
• Decrease rem[x] and update row/column sums of w for the new free multiset.

Check:

• Brute enumerates all permutations for n <= 8.
• Stress compares random divisor constraints and overfilled groups.

代码

来源：problems/cf2226F/solution.cpp

/* Author: likely
 * Time: 2026-06-27
**/
#include<bits/stdc++.h>
using namespace std;

const int MOD=998244353;

static long long mod_pow(long long a,long long e){
    long long r=1;
    while(e){
        if(e&1) r=r*a%MOD;
        a=a*a%MOD;
        e>>=1;
    }
    return r;
}

struct Fenwick{
    int n=0;
    vector<int> bit;
    void init(int n_){
        n=n_;
        bit.assign(n+1,0);
    }
    void add(int idx,int val){
        for(idx++;idx<=n;idx+=idx&-idx) bit[idx]+=val;
    }
    int sum_first(int cnt) const{
        int res=0;
        for(int idx=cnt;idx>0;idx-=idx&-idx) res+=bit[idx];
        return res;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    int max_need=2000000;
    vector<int> inv(max_need+1),fact(max_need+1);
    inv[1]=1;
    for(int i=2;i<=max_need;i++) inv[i]=(long long)(MOD-MOD/i)*inv[MOD%i]%MOD;
    fact[0]=1;
    for(int i=1;i<=max_need;i++) fact[i]=(long long)fact[i-1]*i%MOD;
    const int inv2=(MOD+1)/2;
    while(T--){
        int n,q;
        cin>>n>>q;
        vector<pair<int,int>>qry(q);
        vector<int> divisors;
        for(int d=1;(long long)d*d<=n;d++){
            if(n%d==0){
                divisors.push_back(d);
                if(d*d!=n) divisors.push_back(n/d);
            }
        }
        sort(divisors.begin(),divisors.end());
        int D=(int)divisors.size();
        vector<int> id_of(n+1,-1);
        for(int i=0;i<D;i++) id_of[divisors[i]]=i;
        vector<vector<int>>pos_by_group(D);
        for(int i=0;i<q;i++){
            int p,x;
            cin>>p>>x;
            int g=id_of[x];
            qry[i]={p,g};
            pos_by_group[g].push_back(p);
        }
        for(auto &v:pos_by_group){
            sort(v.begin(),v.end());
            v.erase(unique(v.begin(),v.end()),v.end());
        }
        vector<int> cnt(D,0),seen(D,0);
        vector<vector<long long>> greater_cnt(D,vector<long long>(D,0));
        for(int v=1;v<=n;v++){
            int g=id_of[std::gcd(v,n)];
            for(int j=0;j<D;j++) greater_cnt[g][j]+=seen[j];
            seen[g]++;
        }
        cnt=seen;
        vector<vector<int>> w(D,vector<int>(D,0));
        for(int i=0;i<D;i++){
            for(int j=0;j<D;j++){
                if(i==j){
                    w[i][j]=inv2;
                }else{
                    w[i][j]=greater_cnt[i][j]%MOD;
                    w[i][j]=(long long)w[i][j]*inv[cnt[i]]%MOD*inv[cnt[j]]%MOD;
                }
            }
        }
        vector<Fenwick> by_group(D);
        for(int i=0;i<D;i++) by_group[i].init((int)pos_by_group[i].size());
        vector<int> rem=cnt,fixed_cnt(D,0);
        vector<int> row(D,0),col(D,0);
        for(int i=0;i<D;i++){
            long long sr=0,sc=0;
            for(int j=0;j<D;j++){
                sr+=1LL*rem[j]*w[i][j]%MOD;
                sc+=1LL*rem[j]*w[j][i]%MOD;
            }
            row[i]=sr%MOD;
            col[i]=sc%MOD;
        }
        int free_cnt=n;
        int ways=fact[n];
        int same_sub=0;
        long long s_acc=0;
        for(int i=0;i<D;i++){
            int val=row[i]-w[i][i];
            if(val<0) val+=MOD;
            s_acc+=1LL*rem[i]*val%MOD;
        }
        int free_free=s_acc%MOD;
        int fixed_fixed=0;
        vector<long long> free_after(D,0),free_before(D,0);
        bool bad=false;
        for(int qi=0;qi<q;qi++){
            int pos=qry[qi].first;
            int x=qry[qi].second;
            if(bad||rem[x]==0){
                bad=true;
                cout<<0<<(qi+1==q?'\n':' ');
                continue;
            }
            vector<int> before(D);
            int fixed_before_total=0;
            for(int g=0;g<D;g++){
                auto &vec=pos_by_group[g];
                int upto=(int)(lower_bound(vec.begin(),vec.end(),pos)-vec.begin());
                before[g]=by_group[g].sum_first(upto);
                fixed_before_total+=before[g];
            }
            long long gain=0;
            int fixed_total=n-free_cnt;
            for(int g=0;g<D;g++){
                int after=fixed_cnt[g]-before[g];
                gain+=1LL*before[g]*w[g][x]%MOD;
                gain+=1LL*after*w[x][g]%MOD;
                free_after[g]-=before[g];
                free_before[g]-=after;
            }
            fixed_fixed=(fixed_fixed+gain)%MOD;
            int free_before_pos=pos-1-fixed_before_total;
            int free_after_pos=n-pos-(fixed_total-fixed_before_total);
            free_before[x]+=free_before_pos;
            free_after[x]+=free_after_pos;
            auto &vec=pos_by_group[x];
            int at=(int)(lower_bound(vec.begin(),vec.end(),pos)-vec.begin());
            by_group[x].add(at,1);
            fixed_cnt[x]++;
            ways=(long long)ways*rem[x]%MOD*inv[free_cnt]%MOD;
            int old_row_x=row[x],old_col_x=col[x];
            int delta=old_row_x+old_col_x;
            if(delta>=MOD) delta-=MOD;
            delta-=2LL*w[x][x]%MOD;
            if(delta<0) delta+=MOD;
            free_free-=delta;
            if(free_free<0) free_free+=MOD;
            for(int g=0;g<D;g++){
                row[g]-=w[g][x];
                if(row[g]<0) row[g]+=MOD;
                col[g]-=w[x][g];
                if(col[g]<0) col[g]+=MOD;
            }
            rem[x]--;
            free_cnt--;
            long long mix=0;
            if(free_cnt>0){
                for(int g=0;g<D;g++){
                    mix+=(free_after[g]%MOD)*row[g]%MOD;
                    mix+=(free_before[g]%MOD)*col[g]%MOD;
                }
                mix%=MOD;
                mix=mix*inv[free_cnt]%MOD;
            }
            int expected=fixed_fixed;
            expected+=mix;
            if(expected>=MOD) expected-=MOD;
            expected=(expected+(long long)free_free*inv2)%MOD;
            int ans=(long long)ways*expected%MOD;
            cout<<ans<<(qi+1==q?'\n':' ');
        }
    }
    return 0;
}