题解 P8944【The Da Vinci Code】
cyffff
·
·
题解
\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 取模。
## 思路
交换 $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]$ 交换各两种。
$$b_i\gets \dfrac{(n^2-2n)b_i+2\sum b}{n^2}$$
注意到 $\sum b=1$。
$$b_i\gets \dfrac{(n-2)}{n}b_i+\dfrac{2}{n^2}$$
我们定义 $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)$。
代码：
```cpp
#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~