自动搬运

查看原文

来自洛谷，原作者为

	cyffff Not yet for the story on the last page, it's not the end.

搬运于2025-08-24 22:43:59，当前版本为作者最后更新于2023-01-15 19:16:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\text{Link}$

和官方题解不同的解释方法。

题意

有一个排列 $a_i=i$。有 $k$ 次操作，每次操作均匀随机选取 $i,j\in[1,n]$，交换 $a_i,a_j$。$x$ 在 $[1,n]$ 中以 $b_i$ 为权随机，求 $k$ 次操作后 $x=a_i$ 的概率。对质数 $3221225473$ 取模。

$n\le 2\times 10^7$，$k<2^{64}$。

思路

交换 $a_i,a_j$ 和交换 $b_i,b_j$ 是相同的。

考虑进行一次操作后 $b_i$ 的期望。用总和除以方案数求。总方案为 $n^2$，其中有 $n^2-2n$ 种与 $b_i$ 无关。剩下的 $b_i$ 与 $b_j,j\in[1,n]$ 交换各两种。

注意到 $\sum b=1$。

我们定义 $f(x)=\dfrac{(n-2)}nx+\dfrac{2}{n^2}$，$f^{(k)}(x)=f(f^{(k-1)}(x))$，则最终 $b_i$ 等于 $f^{(k)}(b_i)$。我们只需要求出 $f^{(k)}(x)$ 的解析式，将每个 $b_i$ 代入即可。

显然，$f^{(k)}(x)$ 也是一次函数，我们设 $f(x)=px+q$，归纳可得 $f^{(k)}(x)=p^kx+q(\sum_{i=0}^{k-1}p^i)$，我们所需的只有求逆元，等比数列求和，写个快速幂即可。注意特判 $k=1$。

时间复杂度 $O(n+\log\bmod)$。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
namespace IO{//by cyffff
	
}
typedef unsigned int uint;

const uint mod = 3221225473u;
const int N = 20000010;

ull seed;

ull getnext() {
	seed ^= seed << 13;
	seed ^= seed >> 17;
	seed ^= seed << 5;
	return seed;
}

uint rd(uint l, uint r) {
	return getnext() % (r - l + 1) + l;
}

int n;
ull k;
uint b[N];

inline uint qpow(uint a,uint b){
	uint res=1;
	while(b){
		if(b&1) res=(ull)res*a%mod;
		a=(ull)a*a%mod;
		b>>=1;
	}
	return res;
}
//bi=(n-2)/nbi+2/n^2
ull ans;
int main() {
	n=read(),k=read(),seed=read();
	ull sum = 0;
	for (int i = 1; i < n; ++ i) b[i] = rd(2u, mod - 1), (sum += b[i]) %= mod;
	b[n] = mod + 1 - sum;
	uint in=qpow(n,mod-2),in2=(ull)in*in%mod;
	uint k1=(ull)(n-2)*in%mod,b1=(ull)2*in2%mod;
	uint k2,b2;
	if(k==1){k2=k1,b2=b1;}
	else{
		uint ki=qpow(((ull)k1%mod+mod-1)%mod,mod-2);
		k2=qpow(k1,k%(mod-1)),b2=((ull)k2+mod-1)%mod*ki%mod*b1%mod;
	}
	for(int i=1;i<=n;i++)
		b[i]=((ull)k2*b[i]%mod+b2)%mod,ans^=(ull)b[i]*i;
	write(ans);
	flush();
}

再见 qwq~