题目链接：https://codeforces.com/contest/1553
1553E.Permutation Shift
题目大意：是否能在转置(k)轮和交换(m)次的条件下将((1,2,3,...,n))变成((a_{1},a_{2}，a_{3},...,a_{n}))，(0leq k<n,0leq mleq frac{n}{3})，转置指元素后移(k)位，交换指两个元素交换位置
题目思路：
先将每个数都减(1)
转置0轮((0,1,2,3))
转置1轮((3,0,1,2))
转置2轮((2,3,0,1))
转置3轮((1,2,3,0))
不难发现转置k轮实际上就是(p[i] = i-k(mod n))
对于每一个转置我们可以求出对a序列来说不动点的个数
a序列为((1,2,0,3))
转置0轮((0,1,2,3))，不动点数(cnt[0] = 1)
转置1轮((3,0,1,2))，不动点数(cnt[1] = 0)
转置2轮((2,3,0,1))，不动点数(cnt[2] = 1)
转置3轮((1,2,3,0))，不动点数(cnt[3] = 2)
不动点即(a[i] =p[i] = i-k(mod n)),得 (k = i-a[i] (mod n))，因(++cnt[k])即可
剩下都是需要移动的点，交换(m)次最多可导致(2m)个元素交换，因此可以判断如果(cnt[k]+2m<n)当前转置就不满足条件，跳过即可
因为(mleq frac{n}{3})，最多可以交换(frac{2n}{3})个元素，剩下(frac{n}{3})是不动点的个数，又因为(sum cnt[k] = n)，最多只有3个(k)是满足条件的，直接暴力即可
暴力求出环数(num)，需要移动的点即为(n-num)，对于原序列和a序列每个(i)都会引条边指向(a[i])，即(i
ightarrow a[i])，而转置k轮又会导致(i- k
ightarrow a[i])，即(i
ightarrow a[i] + k)，遍历边即可
AC代码：
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <deque>
#include <queue>
#include <cmath>
#include <map>
#include <set>
using namespace std;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
//typedef __int128 int128;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int N = 3e5 + 10, M = 4e7 + 10;
const int base = 1e9;
const int P = 131;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const double PI = acos(-1.0);
int a[N], cnt[N], ans[5];
int pos;
bool vis[N];
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
pos = 0;
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i)
{
scanf("%d", &a[i]);
--a[i];
++cnt[(i - a[i] + n) % n];
}
for (int k = 0; k < n; ++k)
{
if (cnt[k] + 2 * m < n)
continue;
for (int i = 0; i < n; ++i)
vis[i] = false;
int num = 0;
for (int i = 0; i < n; ++i)
{
if (vis[i])
continue;
for (int j = i; !vis[j]; j = (a[j] + k) % n)
vis[j] = true;
++num;
}
if (n - num <= m)
ans[++pos] = k;
}
printf("%d ", pos);
for (int i = 1; i <= pos; ++i)
printf("%d ", ans[i]);
printf("
");
}
return 0;
}
1553F.Pairwise Modulo
题目大意：求(p_k = sum_{1 le i, j le k} a_i mod a_j)
题目思路：记(a_i)的前缀和为(s_i),每增加一个(a_{i})，答案加
对于(a_{i}sum_{j=1}^{i-1}left lfloor frac{a_{j}}{a_{i}}
ight
floor)，区间查询([da_i,(d+1)a_i))的个数，此区间每个数的贡献为(d)，然后对(a_j)进行单点插入个数1
对于(sum_{j=1}^{i-1}left lfloor frac{a_{i}}{a_{j}}
ight
floor a_{j})，单点查询(a_i)对前面所有的(a_j)的贡献，然后枚举(a_j)的倍数(da_j)，对(da_j)进行单点增加(a_j)，说的可能不清楚，那我上图！
AC代码：
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <deque>
#include <queue>
#include <cmath>
#include <map>
#include <set>
using namespace std;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
//typedef __int128 int128;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int N = 3e5 + 10, M = 4e7 + 10;
const int base = 1e9;
const int P = 131;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const double PI = acos(-1.0);
int n;
ll a[N], s[N], ai[N], aj[N];
int lowbit(int x)
{
return x & -x;
}
void add(ll tr[], int x, ll c)
{
for (int i = x; i < N; i += lowbit(i))
tr[i] += c;
}
ll sum(ll tr[], int x)
{
ll res = 0;
for (int i = x; i; i -= lowbit(i))
res += tr[i];
return res;
}
ll getai(ll x)
{
ll res = 0;
for (ll d = 1; d * x <= N; ++d)
{
ll cnt = sum(ai, min((ll)N, (d + 1) * x) - 1) - sum(ai, d * x - 1);
res += cnt * d;
}
return x * res;
}
ll getaj(ll x)
{
return sum(aj, x);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%lld", &a[i]);
s[i] = s[i - 1] + a[i];
}
ll ans = 0;
for (int i = 1; i <= n; ++i)
{
ans += s[i - 1] + (i - 1) * a[i] - getai(a[i]) - getaj(a[i]);
printf("%lld ", ans);
add(ai, a[i], 1);
for (ll d = 1; d * a[i] <= N; ++d)
add(aj, d * a[i], a[i]);
}
return 0;
}