杭电多校第五场 1009 Paperfolding 题解

题目大意

有一张纸,你有n次对折的机会,有两种方式,向左折和向右折,两种方式等概率出现,折完之后,沿中心切十字,求切完剩下的纸片数量的期望值。

解题思路

刚开始看到这个题目的时候,看到n这么大,应该是有公式的,不可能递推。

想了半天,蒙了个公式,wa了。。

看到大佬的博客,一个很好的方法。

假设上下对折a次,左右对折b次,图中的虚线为对折线,实线为裁剪线。

对着最终的纸裁剪,就相当于是对折痕的每一个纸片都十字裁剪。

可以得出最终纸片数量为$(2^a+1)(2^b+1)$。

如该图,左右对折两次,上下对折两次,纸片数量为5*5=25。

官方题解是说,原本是横竖裁一次,每对折一次是相当于每次增加了$2^n$次。

其实差不多,这俩思路。

可以得出期望为$ \large E(x) = \frac{1}{2^n}\sum_{i=0}^n C_n^i(2^i + 1)(2^{n-i} + 1)$

可以拆成$\large \sum_{i=0}^n C_n^i(2^n + 1+2^{n-i} + 2^i)$。

因为$\large \sum_{i=0}^n C_n^i$是等于$2^n$,所以$ \large E(x) = 1+2^n+\frac{1}{2^n}\sum_{i=0}^n C_n^i(2^i+2^{n-i})$。

对最后那一项,由$\large3^n=(2+1)^n=\sum_{i=0}^nC_n^i2^i1^{n-i}=\sum_{i=0}^nC_n^i2^i$。

同理可得,$\large3^n=\sum_{i=0}^nC_n^i2^{n-i}$。

所以$ \large E(x) = 1+2^n+\frac{2\times 3^n}{2^n}$。

用快速幂求解即可。

完整代码

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 <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const ll mod = 998244353;

ll qpow(ll a, ll b) {
ll ans = 1;
while (b) {
if (b & 1) ans = (ans * a % mod) % mod;
a = (a * a % mod) % mod, b >>= 1;
}
return ans;
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t;
cin >> t;
while (t--) {
ll n;
cin >> n;
ll ans = (1 + qpow(2, n) % mod + 2 * (qpow(3, n) % mod * qpow(qpow(2, n), mod - 2) % mod)) % mod;
cout << ans << endl;
}
return 0;
}
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信