PLEASE
Created by LXC on Sun Apr 30 02:23:46 2023
https://codeforces.com/problemset/problem/696/C
ranting: 2000
tag: combinatorics, dp, implementation, math, matrices
题意
有三个杯子排成一行，中间的杯子盖住了硬币
然后进行n次操作，每次操作随机选取左边或者右边的杯子与中间的杯子进行交换。
问最后杯子在中间的概率是多少。
n非常大，所以用k个小于1e18的数的乘积表示n。
最后的概率需要表示为分数p/q的最简形式，也就是gcd(p,q)=1
另外由于p和q巨大，所以p和q都需要模1e9+7
题解
我们设$f_n$为第n次交换后硬币在中间的概率。
交换一次，硬币一定不在中间，所以$f_1 =0$
然后对于第i次交换，硬币一定不在中间的概率是$1-f_{i-1}$，硬币在左边或者右边的杯子里，所以有0.5的概率选中与中间交换。
所以$f_i = 0.5*(1-f_{i-1})$
即$f_i + 0.5*f_{i-1} = 0.5$
这个递推式不是齐次的。
我们化为齐次形如$a+bf_i + c(a+bf_{i-1}) = 0$，其中$a,b,c$为待定系数
求得$a = -\frac{2}{3}, b = 2, c = \frac{1}{2}$
所以$-\frac{2}{3} + 2f_i - \frac{1}{2}(-\frac{2}{3}+2f_{i-1}) = 0$
可令$g_i = -\frac{2}{3} + 2f_i$，则$g_1 = -\frac{2}{3}$
$g_i = -\frac{1}{2}g_{i-1}$，这是等比数列的递推式，其通项公式$g_i = \frac{g_i}{g_{i-1}} \cdot \frac{g_{i-1}}{g_{i-2}} \cdots\cdot \frac{g_{2}}{g_{1}}\cdot g_1 = -(-\frac{1}{2})^{i-1}\frac{2}{3}$
所以$f_i = -(-\frac{1}{2})^{i-1}\frac{1}{3}+\frac{1}{3} = \frac{(-2)^{i-1}-1}{(-2)^{i-1}3}$
当i为奇数时
$f_i = \frac{2^{i-1}-1}{2^{i-1}3}$
当i为偶数时
$f_i = \frac{2^{i-1}+1}{2^{i-1}3}$
显然$2^{i-1}\pm 1$不能被$2^{i-1}$整除，只需判断$2^{i-1}\pm 1$能否能被$3$整除，若能被3整除则需要化简分数（利用费马小定理将分子乘以3在模1e9+7下的逆元即可）。
实际上$\frac{2^奇+1}{3}，\frac{2^偶-1}{3}$为整数
通过$\frac{2^偶-1}{3} = \frac{(2^{偶/2}-1)(2^{偶/2}+1)}{3}$，$\frac{2^奇+1}{3} = \frac{2(2^{偶}-1)+3}{3}$可以将指数化小。而$\frac{2^1+1}{3}，\frac{2^2-1}{3}$为整数。
所以当i为奇数时$f_i = \frac{2^{i-1}-1}{3}$为整数；当i为偶数时$f_i = \frac{2^{i-1}+1}{3}$为整数
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define N 500005
#define MOD 1000000007
using namespace std;
ll fpow(ll a, ll p, ll m) {
ll rt = 1;
while (p) {
if (p & 1)
rt *= a, rt %= m;
a = a * a % m;
p >>= 1;
}
return rt;
}
void sol() {
int k;
cin >> k;
vector<ll> v(k);
int o = 1;
ll res = 2, mod3 = 2;
for (ll& i : v) {
cin >> i;
res = fpow(res, i, MOD);
mod3 = fpow(mod3, i, 3);
if (i % 2 == 0)
o = 0;
}
res = res * fpow(2, MOD - 2, MOD) % MOD;
mod3 = mod3 * fpow(2, 1, 3) % MOD;
if (o) {
if ((mod3 + 2) % 3 == 0)
cout << (res - 1 + MOD) % MOD * fpow(3, MOD - 2, MOD) % MOD << "/"
<< res << "\n";
else
cout << (res - 1 + MOD) % MOD << "/" << res * 3 % MOD << "\n";
} else {
if ((mod3 + 1) % 3 == 0)
cout << (res + 1) % MOD * fpow(3, MOD - 2, MOD) % MOD << "/" << res
<< "\n";
else
cout << (res + 1) % MOD << "/" << res * 3 % MOD << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifndef SINGLE_INPUT
int t;
cin >> t;
while (t--) {
sol();
}
#else
sol();
#endif
return 0;
}
#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define N 500005
#define MOD 1000000007
using namespace std;
ll fpow(ll a, ll p, ll m) {
ll rt = 1;
while (p) {
if (p & 1)
rt *= a, rt %= m;
a = a * a % m;
p >>= 1;
}
return rt;
}
void sol() {
int k;
cin >> k;
vector<ll> v(k);
int o = 1;
ll res = 2;
for (ll& i : v) {
cin >> i;
res = fpow(res, i, MOD) % MOD;
if (i % 2 == 0)
o = 0;
}
res = res * fpow(2, MOD - 2, MOD) % MOD;
if (o) {
cout << (res - 1 + MOD) % MOD * fpow(3, MOD - 2, MOD) % MOD << "/"
<< res << "\n";
} else {
cout << (res + 1) % MOD * fpow(3, MOD - 2, MOD) % MOD << "/" << res
<< "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifndef SINGLE_INPUT
int t;
cin >> t;
while (t--) {
sol();
}
#else
sol();
#endif
return 0;
}
|