abc360 E 题解

E

对于位置2~n，它们的概率是相等的。

n*n个(x,y)对。其中x可以等于y。

对于x/y，y的逆元rev(y)为mul(y,mod-2)。

加、减、乘、除都可以做。比如48/9和16/3的结果是一样的，48*rev(9)%mod = 16*rev(3)%mod。比如3*rev(2)%mod = (rev(2)+rev(2)+rev(2))%mod.

对于每次操作，有多少概率黑球在位置1：

a. 黑球上次在位置1，这次不进行修改

　　概率：(n-1)*(n-1)+1 / n^2

b. 黑球上次在其它地方，这次移动到位置1

　　概率：2 / n^2

举个例子，以n为3为例，

(x,y)总共有1 1, 1 2, 1 3, 2 1, 2 2, 2 3, 3 1, 3 2, 3 3

对于a，有2 2, 2 3, 3 2, 3 3, 1 1。共5个

对于b，对于数字2，有2 1, 1 2, 对于数字3，有3 1, 3 2。共2个

递推式为：

注意n*n-2*n+2，要先取模，否则它再乘上其它数，有可能大于Long Long范围。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define LL long long
 4 #define ULL unsigned long long
 5 
 6 const LL mod=998244353;
 7 
 8 const double eps_1=1e-5;
 9 const double eps_2=1e-10;
10 
11 const int maxn=1e5+10;
12 
13 LL a[maxn];
14 
15 LL mul(LL x, LL y)
16 {
17     LL z=1;
18     while (y)
19     {
20         if (y&1)
21             z=z*x%mod;
22         x=x*x%mod;
23         y>>=1;
24     }
25     return z;
26 }
27 
28 LL rev(LL x)
29 {
30     return mul(x,mod-2);
31 }
32 
33 int main()
34 {
35     LL n,k,i,rev_n,one,other;
36     cin>>n>>k;
37     a[0]=1;
38     rev_n = rev(n);
39     for (i=1;i<=k;i++)
40     {
41         //n*n-2*n+2 放在前面
42         a[i] = ( (n*n-2*n+2) % mod *a[i-1] % mod + (1-a[i-1]+mod) * 2 % mod ) % mod
43              * rev_n % mod * rev_n % mod;
44     }
45     one = a[k];
46     other = (1-one+mod) * rev(n-1) % mod;
47     cout << ( one + (n-1) * (2+n) % mod * rev(2) % mod * other % mod ) % mod;
48 
49     return 0;
50 }

F

G