杭电多校第五场 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}$。

用快速幂求解即可。

完整代码

#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;
}