Harbour.Space Scholarship Contest 2021-2022

E. Permutation Shift

思路：
原问题等价于把 ${resulting\ array\ p}$ 往左挪 ${k}$ 位，然后最多交换 ${m}$ 次得到原排列，求有多少种 ${k}$ 。

假设排列 ${a=\{1,2,3,4,...,n\}}$ 表示原排列， ${f[i]=\{n-i+1,n-i+2,...,n,1,2,...,n-i\}}$ 表示原排列往右挪 ${k}$ 位得到的排列，那么当 ${i!=j}$ 时， ${f[i]、f[j]}$ 对应位置上数字相同的个数为 ${0}$ 。

一个通常能想到的套路就是枚举 ${k}$ ，然后把排列 ${p}$ 往左挪 ${k}$ 位得到排列 ${x}$ ，然后判断排列 ${x}$ 能不能通过最多 ${m}$ 次交换得到原排列。一个很简单的结论就是，排列 ${x}$ 和排列 $a$ 如果有 ${cnt}$ 个位置不同，那么最少需要交换 $cnt/2$ 次，最多需要交换 $cnt-1$ 次。转化一下就是，排列 ${x}$ 最小需要有 $n-2*m$ 个对应位置的数字相同。

假设有 ${y}$ 个 ${k}$ 满足这一题的条件，满足条件的 ${k}$ 的集合 ${B=\{b_1,b_2,b_3....\}}$ ，那么排列 ${p、f[b_i]}$ 对应位置上数字相同的个数不小于 ${n-2*m}$ ,又因为当 ${i!=j}$ 时, ${f[b_i]、f[b_j]}$ 对应位置上数字相同的个数为 ${0}$ 。所以有不等式 ${(n-2*m)*y<=n}$ ，而 ${m<=\frac{n}{3}}$ ,解得 ${y<=3}$ 。也就是说 ${k}$ 最多只有三种情况，当排列 ${p、f[b_i]}$ 对应位置上数字相同的个数不小于 ${n-2*m}$ 时可以直接暴力判断是否满足题目条件。

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5+7,mod=998244353;
vector<int>v;
int cnt[maxn],a[maxn],p[maxn],n,m;
bool vis[maxn];
bool check(int k) {
    int tot(0);
    for(int i=k+1;i<=n;++i) p[++tot]=a[i],vis[i]=false;
    for(int i=1;i<=k;++i) p[++tot]=a[i],vis[i]=false;
    int ans=n,pos;
    for(int i=1;i<=n;++i) {
        if(vis[i]) continue;//i已经交换过了
        --ans;
        pos=i;
        while(!vis[pos]) {
            vis[pos]=true;
            pos=p[pos];
        }
    }
    return ans<=m;
}
inline void solve() {
    cin>>n>>m;
    int minsize=n-2*m;
    for(int i=0;i<n;++i) cnt[i]=0;
    for(int i=1;i<=n;++i) {
        cin>>a[i];
        cnt[(i-a[i]+n)%n]+=1;
    }
    v.clear();
    for(int i=0;i<n;++i) {
        if(cnt[i]>=minsize&&check(i)) v.emplace_back(i);
    }
    cout<<v.size();
    for(int i:v) cout<<' '<<i;
    cout<<'\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}

F. Pairwise Modulo

${a_i,a_j}$ 的下标大小关系不确定，不方便理解，一般的套路拆分成两个公式：

1. ${s_k=\sum_{1\le i<j\le k}}{a_i\ mod\ a_j}$

2. ${t_k=\sum_{1\le j<i\le k}}{a_i\ mod\ a_j}$

尝试去掉取余来对公式变形：

1. ${s_k=\sum_{1\le i<j\le k}{a_i\ mod\ a_j}}$

${=s_{k-1}+\sum_{1\le i< k}{a_k\ mod\ a_i}}$

${=s_{k-1}+\sum_{1\le i< k}{(a_k\ -\ a_i*⌊\frac{a_k}{a_i}⌋)}}$

${=s_{k-1}+a_k*(k-1)-\sum_{1\le i< k}{\ a_i*⌊\frac{a_k}{a_i}⌋}}$

考虑公式后面的一部分，可以发现 ${a_i}$ 对大于等于 ${a_i*x}$ 的数 $s_k$ 的贡献是 ${x*a_i}$ ，所以可以把所有树状数组下标为 $a_i*x$ 的位置加上 $-a_i$ ，然后前面所有 $a_i$ 对 ${s_k}$ 的贡献就是树状数组区间 ${1\sim a_k}$ 的和了。

2. ${t_k=\sum_{1\le j<i\le k}}{a_i\ mod\ a_j}$

${=t_{k-1}+\sum_{1\le i< k}{(a_i\ -\ a_k*⌊\frac{a_i}{a_k}⌋)}}$

${=t_{k-1}+\sum_{1\le i< k}{a_i}+\sum_{1\le i< k}{(a_k*⌊\frac{a_i}{a_k}⌋)}}$

考虑公式后面的部分，其实可以枚举 ${⌊\frac{a_i}{a_k}⌋=1,2...}$ ，然后用树状数组求区间 ${[a_k*x,a_k*(x+1))}$ 内有多少个数，贡献就是 ${a_k*x*cnt}$

code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5+7,mod=998244353;
struct node{
    ll t[maxn];
    void add(int p,ll x) {
        while(p<maxn) {
            t[p]+=x;
            p+=(p&-p);
        }
    }
    ll sum(int p) {
        ll res(0);
        while(p>0) {
            res+=t[p];
            p-=(p&-p);
        }
        return res;
    }
}A,B;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    ll ans(0),pre(0);
    cin>>n;
    for(int i=0,x;i<n;++i) {
        cin>>x;
        ans+=1LL*x*i;
        ans+=A.sum(x);
        ans+=pre;
        pre+=x;
        for(int j=x;j<maxn;j+=x) {
            int l=j,r=min(j+x-1,maxn-1);
            ans-=(B.sum(r)-B.sum(l-1))*j;
            A.add(l,-x);//log maxn
        }//log maxn
        B.add(x,1);
        cout<<ans<<' ';
    }//n
    cout<<'\n';
    return 0;
}