B. hat

B. hat

传送门

思路：显然无论怎么交换，最终相同概率的个数是不会变等于$n-1$，即每次交换只存在两种概率，而且对于交换$(x,y)$，就是相当于$p_x,p_y$概率交换，所以我们可以找到最终那一个唯一的不同的概率的位置，因为初始化$pos=1$, 若$(x,y)$中有$pos$，则$pos$变为另一个位置，接下来我们只考虑没有被看见的交换，显然在这次操作后的位置$i$有兔子的概率$p^{\prime }$，存在两种情况，该位置原来有兔子，但没有交换它，则此时概率为：

$p\times \frac{n-2}{n},$因为是从$n$个数中选两个数，则没有被选中的概率是$\frac{n-2}{2}$。

第二种情况，该位置原来没有兔子，但是与它交换的位置有兔子。

首先被选中的概率是$\frac{2}{n}$，然后与它交换的位置有兔子的概率是$\frac{1}{n-1}$，($n-1$位置等可能性)，所以概率是$(1-p)\times \frac{2}{n}\times \frac{1}{n-1}$

综上$p^{\prime }=p\times \frac{n-2}{n}+(1-p)\times \frac{2}{n}\times \frac{1}{n-1}$

然后用费马小定理转化一下，递推就行了。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=998244353; #define mst(a) memset(a,0,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg register #define PII pair<int,int> #define fi first #define se second ll ksm(ll a,ll n){ ll ans=1; while(n){ if(n&1) ans=ans*a%mod; a=a*a%mod; n>>=1; } return ans; } struct p{ int id,x,y; }a[N]; int main(){ int t; scanf("%d",&t); while(t--){ int n,m,k; scanf("%d%d%d",&n,&m,&k); int pos=1; ll ans1=1,ans2=0; for(int i=1;i<=k;i++){ int id,x,y; scanf("%d%d%d",&id,&x,&y); if(x==pos) pos=y; else if(pos==y) pos=x; } ll inv1=ksm(n,mod-2)%mod,inv2=ksm(n-1,mod-2)%mod,x=(n-2)*inv1%mod,y=(2*inv1*inv2)%mod; for(int i=1;i<=m-k;i++) { ans1=(ans1*x)%mod+((1-ans1+mod)%mod)*y%mod,ans1%=mod; ans2=(ans2*x)%mod+((1-ans2+mod)%mod)*y%mod,ans2%=mod; } for(int i=1;i<=n;i++) if(pos==i) printf("%lld ",ans1); else printf("%lld ",ans2); printf("\n"); } return 0; }

对于$bouns:m\le 10^{10},k\le 10^5$,显然可以用数学公式求和。

$p^{\prime }=\frac{2}{n(n-1)}+(\frac{n-2}{n}-\frac{2}{n(n-1)})\times p$

令$(\frac{n-2}{n}-\frac{2}{n(n-1)})=k$

$\frac{2}{n(n-1)}=b$。

转化为等比数列：

$$\begin{gathered} p_{i+1}=k{p}_i+b \\ {p}_{i+1}+\frac{b}{k-1}=k(p_i+\frac{b}{k-1}) \end{gathered}$$

$p_n+\frac{b}{k-1}=p_1\times k^{n-1}$

$p_n=p_1\times k^{n-1}-\frac{b}{k-1}$

呃大概思路是这样，但是有很多细节需要注意。。。还是太菜不会写。