题解：B3802 [NICA #1] 交换

· · 题解

原题：

题目信息

题目概括：

有 n 个数，每个数在 1 到 n 中只出现了一次。进行 m 次操作，第 i 次操作会交换 (i-1)\mod (n+1)+1 大的和 (i-1)\bmod (n+1)+2 大的数字（详细内容看题目）。操作结束后这些数是什么样的？

解题思路：

给大家分享一下我的做题过程：

第一步，看标签：数学。

第二步，看数据范围：这一看，我发现 m 的取值范围竟然高达 10^{1000000}！

这么大的数据，先不谈程序效率，单轮存储方式：除了高精度，还有什么存的下呢？

再想起来标签，再回顾了一下题目，我发现这个题目有一个技巧：具有周期性。

为什么呢？我们可以举这样一个例子：

3 10
1 2 3

可以发现，每一次的交换结果如下：

1 3 2
2 3 1
3 2 1
3 1 2
2 1 3
1 2 3
1 3 2
2 3 1
3 2 1
3 1 2

我们可以发现：第 6 行以前的部分一直在重复。通过多组数据发现：数据它是有周期性的，而周期便是 n\times (n-1)！

有了这个结论，那我们岂不是效率大增，只需要交换 m \bmod n \times (n-1) 不就行了？

可这样子仍需要进行 10^{10}次，还是会超时。

我们还要进行优化！

还是刚刚那一组数据为例子，当 m=2 时：

2 3 1

当 m=4 时：

3 1 2

当 m=6 时：

1 2 3

可以发现，每一个 n-1 的操作时，所做的就是把第一个放在最后一个去。这个同样也具有周期性。

对于剩下的操作中，我们把 n-1 提取出来，让所有数字加上 \lfloor \frac{m}{n-1} \rfloor 后取余 n 即可。这个就模拟了以上过程。

进行两次优化之后，终于进入了时间限制！

代码：

以上是大体思路。有了思路就好了，代码实现参考下面代码。

直接复制会爆零，仅供参考~

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,a[1000000+1000],v[1000000+1000];
string m;
int main(){
    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
    }
    ll num=0;
    for(ll i=0;i<m.size();i++) num=(num*10+m[i]-'0')%(n*(n-1)); //第一层优化 
    for(ll i=1;i<=n;i++) a[i]=(a[i]+num/(n-1)-1)%n-1;//第二层优化 
    for(ll i=1;i<=n;i++) v[a[i]]=i;//给数字编号 
    for(ll i=1;i<=num%(n-1);i++){//交换 
        ll t1=n-(i-1)%(n-1);
        ll t2=n-(i-1)%(n-1)-1;
        swap(a[v[t1]],a[v[t2]]);
        swap(v[t1],v[t2]);
    }
    for(ll i=1;i<=n;i++) cout<<a[i]<<" ";
    return 0;
}

结尾：

以上题解，dalao请回避，仅供蒟蒻参考，因为其中很多内容都试是出来的，没有严谨的数学推理。但这样做也是一种方式。

这是我第一篇题解，哪里不好我努力改正~