排列组合

排列组合就是计算题啊。。

  • 数学期望线性
  • 概率dp
  • 计算题,找规律
  • 递推

A. Game on Tree

 

期望可加性

需要知道一个定理:Esum=EiE_{sum}=\sum E_i,可以把整个树上的期望变为单点的期望值之和。

要求删除整个树的操作数的期望值,我们就转化为求每个点的操作数期望值。

单点期望值=\sum 各种情况出现的概率*各种情况下的对该点的操作数。

首先我们考虑在哪些情况下该点会被删除

  • 该点某一个祖宗节点被删除
  • 该点被删除

对于第一种情况,我们对该点并无操作,操作数=0;对于第二种情况,操作数=1。

**再来看两种情况概率,由于只有上述两种情况会删除该点,所以对其子节点的操作不应该考虑。**因此总的情况数应等于该点的所有祖宗节点+自身。设祖宗节点+1=k,则第一种情况概率为(k-1)/k;第二种情况概率为1/k.

前面说了子节点不应该考虑,通过观察根节点可以更能理解,若考虑所有子节点,则根节点自身被删除的概率为1/n,n为总节点数,所以根节点操作数的期望值应该是1/n,这就说明我们可能不通过直接删除根节点自身而去除根节点,然而由于根节点无父节点,所以这是不可能的,这就说明我们不应考虑子节点,因为子节点并未达到删除当前节点的目的。

再考虑实现方法,k为当前点的深度,每个点的期望值=1/深度。所以我们只要把深度求出来。

求深度dfs一下就好了。

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
int n;
vector<int>G[maxn];
int par[maxn];
int dep[maxn];
void add_edge(int u, int v) {
G[u].push_back(v);
G[v].push_back(u);
}
void dfs(int x,int d) {
dep[x] = d;
for (int i = 0; i < G[x].size(); i++) {
if (G[x][i] != par[x]) {
par[G[x][i]] = x;
dfs(G[x][i], d + 1);
}
}
}
int main() {
cin.sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
add_edge(u, v);
}
dfs(1,1);
double ans = 0;
for (int i = 1; i <= n; i++) {
ans += (1.0 / dep[i]);
}
printf("%.12f", ans);
return 0;
}

 

B. Bad Luck Island

 

概率dp

有趣的题目,石头剪刀布三个种族,求最终存活的概率。

dp[i] [j] [k]表示石头剩余i个,剪刀剩余j个,布剩余k个,这种情况出现过的概率。

初始dp[r] [s] [p]=1,因为r,s,p的情况已知出现过了,概率为1.

最终情况,rsp中某两个为0,这种情况一旦出现就不会再变化,所以它出现过就表示它是最终结果,我们可以放心的把它加到答案中去。

状态转移:

若i>0,则说明i还可以减少,此时可以推出i-1的概率,即i的概率*石头遇上布的概率。

jk同理。

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
using namespace std;
#define ll long long
int r, s, p;
double dp[105][105][105];
int main() {
cin >> r >> s >> p;
dp[r][s][p] = 1;
for (int i = r; i >= 0; i--) {
for (int j = s; j >= 0; j--) {
for (int k = p; k >= 0; k--) {
int kind = 0;
if (i > 0)kind++;
if (j > 0)kind++;
if (k > 0)kind++;
if (kind <= 1)continue;
int sum = i * j + i * k + j * k;
if (i > 0) {
dp[i - 1][j][k] += dp[i][j][k] * i*k / sum;
}
if (j > 0) {
dp[i][j - 1][k] += dp[i][j][k] * i*j / sum;
}
if (k > 0) {
dp[i][j][k - 1] += dp[i][j][k] * j*k / sum;
}
}
}
}
double a1 = 0, a2 = 0, a3 = 0;
for (int i = 1; i <= r; i++) {
a1 += dp[i][0][0];
}
for (int i = 1; i <= s; i++) {
a2 += dp[0][i][0];
}
for (int i = 1; i <= p; i++) {
a3 += dp[0][0][i];
}
printf("%.12f %.12f %.12f", a1, a2, a3);
return 0;
}

 

C. Basketball Team

 

纯概率计算题

考虑反面,要求有队友的概率,可能有1个,2个等等,比较麻烦,我们考虑没有队友的概率。

接着分类讨论,主要注意点是要把公式化简,不能硬用组合数莽,否则会爆。

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
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
#define ll long long
int n, m, k;
int a[1005];
int sum;
int main() {
cin >> n >> m >> k;
for (int i = 1; i <= m; i++) {
cin >> a[i];
sum += a[i];
}
if (sum < n) {
cout << -1;
}
else if (sum == n) {
if (a[k] > 1) {
cout << 1;
}
else cout << 0;
}
else {
if (a[k] == 1)
cout << 0;
else {
double p = 1;
int u = sum - a[k];
int v = sum - 1;
for (int i = 0; i < n - 1; i++) {
p *= (1.0*u) / v;
u--;
v--;
}
cout << 1 - p;
}
}
return 0;
}

 

D. Intercity Travelling

 

找规律

每个点有01两种情况,考虑a1,a2,a3,a_1,a_2,a_3,\cdots,什么时候出现。

起初都是a1a_1,接着有一半的加油站,表示出现了一半的a2a_2,这一半的a2a_2,在下一波又有一半变成a3a_3,以此类推。

注意第一次有一半a1a_1变为a2a_2,还剩下一半a1a_1,它们又会变成a2a3,a_2,a_3,\cdots,不能忘了这一支。

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
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
const int maxn = 1e6 + 5;
#define ll long long
ll n, a[maxn];
const int mod = 998244353;
ll ans;
ll p[maxn];
int main() {
p[0] = 1;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
p[i] = p[i - 1] * 2 % mod;
}
for (int i = 1; i <= n; i++) {
ans = (ans +a[i]*(p[n-i]+(n-i+mod)%mod*p[n-i-1]%mod)%mod) % mod;
}
cout << ans;
return 0;
}

 

E. Little Pony and Expected Maximum

 

计算题

期望值=该数数值*该数为最大值的概率

一个数成为最大的数,当且仅当比该数大的数都不出现,并且该数出现了。

接下来求出各个数出现或不出现的概率,乘起来就好了。

注意公式化简和精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
const int maxn = 1e5 + 5;
#define ll long long
double ans;
int n, m;
double p[maxn];
double q[maxn];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
p[i] = 1.0*i/n;
}
for (int i = 1; i <= n;i++) {
ans += i*pow(p[i], m)*(1 - pow(1.0*(i - 1) / i, m));
}
printf("%.12f", ans);
return 0;
}

 

G. Bus Number

 

枚举+组合数公式

回忆到的每个数至少会出现一次且有次数上限,而没回忆到的数都不会出现。

所以我们可以枚举每种数出现的次数组合。

对于每种情况,先考虑无限制的排列数,再减去有前导零的排列数。

假设共有sum位,则无限制的排列数要首先去重,即P=PsumsumPa0Pa1PanP=\frac{P_{sum}^{sum}}{P_{a_0}P_{a_1}\cdots P_{a_n}},其中a0a_0表示0的个数;有前导零的情况,就是先确定第一位为0,接下来sum-1位按上面的公式排列去重。最终两者相减。

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
using namespace std;
#define ll long long
ll ans;
int ct[10];
int tmp[10];
ll P[20];
void init() {
P[0] = 1;
for (int i = 1; i < 20; i++) {
P[i] = i * P[i - 1];
}
}
void dfs(int x) {
if (x == 10) {
int sum = 0;
for (int i = 0; i <= 9; i++) {
sum += tmp[i];
}
ll a = P[sum];
for (int i = 0; i <= 9; i++) {
a /= P[tmp[i]];
}
a -= (a*tmp[0] / sum);
ans += a;
return;
}
if (ct[x] == 0)dfs(x + 1);
else {
for (int i = 1; i <= ct[x]; i++) {
tmp[x] = i;
dfs(x + 1);
}
}
}
int main() {
init();
string s;
cin >> s;
for (int i = 0; i < s.length(); i++) {
ct[s[i] - '0']++;
}
dfs(0);
cout << ans;
return 0;
}

 

H. Malek Dance Club

 

递推

要找两个数,满足a>b,且(a^n) < (b^n)。我刚开始考虑异或的单调性,但是发现它并不单调且没有规律。

考虑递推,看能否把位数减小,归并到1位的情况。

分两种情况,最高位为0或1.

最高位为0,现在假设我们已知 位数-1的情况,只要考虑最高位对答案的影响。最高位为0,则表示无影响,则我们在已知的 位数-1 的配对上都加上最高为1,或者0,他们仍然是满足条件的。

f(0x)=2f(x)f(0x)=2f(x)

最高位为1,首先,我们在位数-1的配对上都加上最高位0或者1,由于两个数a,b最高位都被异或了,所以相当于没有最高位,仍然是满足条件的。其次,抛开位数-1,我们创造出两个数,一个数a最高位是0,另一个b最高位是1.两者必然是a<b,然而异或了1,之后,a最高位变1,b最高位变0.则是(a^n) > (b^n)。满足条件。从开头为0的数中选择a,有 2n12^{n-1}种选择,从开头为1的数中选择b,同样有2n12^{n-1}种选择,则共有4n14^{n-1}种配对。同时,由于两个数一个最高位0,另一个1,所以不会与前面的情况重复,可以放心加上。

f(1x)=2f(x)+4n1f(1x)=2f(x)+4^{n-1}

只有一位的情况:

  • f(1)=1,即a=0,b=1,由于a,b无差别,所以a=1,b=0是同一种匹配。

  • f(0)=0

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
using namespace std;
#define ll long long
const int mod = 1000000007;
string s;
ll ans;
ll p[105];
void init() {
p[0] = 1;
for (int i = 1; i < 105; i++) {
p[i] = p[i - 1] * 4 % mod;
}
}
ll solve(int x) {
if (x == 0) {
if (s[0] == '1')
return 1;
else return 0;
}
if (s[x] == '0') {
return 2 * solve(x - 1) % mod;
}
else {
return (2 * solve(x - 1) % mod + p[x]) % mod;
}
}
int main() {
init();
cin >> s;
reverse(s.begin(), s.end());
cout<< solve(s.length()-1);
return 0;
}

 

I. Inna and Nine

 

找规律,分类讨论

把相邻的能合成9的数合成9,要求9最多的方案数。

如果奇数个能合成9,例如363,则有两种方案,合成39或93,ans*2;若偶数个,如3636,则必须全部合成9,只有1种.

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
#define ll long long
int main() {
string s;
cin >> s;
ll cnt = 1;
ll ans = 1;
for (int i = 1; i <= s.length(); i++) {
if (i == s.length() || (s[i] + s[i - 1] - 2 * '0' != 9)) {
if (cnt > 1 && (cnt & 1)) {
ans *= (cnt + 1)/2;
}
cnt = 1;
}
else {
cnt++;
}
}
cout << ans;
return 0;
}

 

J. Monotonic Renumeration

 

区间合并

相同的两个数之间也必定是相同的。

所以问题变为有几段不相同的数,即把相同数作为区间端点,求有几个区间。

这里看到一个较巧妙地方法。

  1. 把一个数字最后出现的位置记录下来。

  2. 新建一个指针从最左端起移动,若指针所指位置不是当前数字最后位置,则指针移动到当前数字最后位置,相当于把中间都略过了。

  3. 若指针与i相等,说明扫完了一个区间,即将开始新的一个区间。这时计数器+1.

  4. i到达最后结束。

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
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const int mod = 998244353;
map<ll, int> mp;
ll a[maxn];
ll ans = 1;
int n;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
mp[a[i]] = i;
}
int r = 1;
for (int i = 1; i <= n; i++) {
if (r >= i)
r = max(r, mp[a[i]]);
else {
ans = ans * 2 % mod;
r = mp[a[i]];
}
}
cout << ans;
return 0;
}