2020杭电多校第五场 1009 Paperfolding

链接

题意

将一张纸对折n次，每一次对折有四种选择，问最后从中心水平切一刀，垂直切一刀最后得到的纸片数有多少？

比如我n=0时，就是一张纸，从中心水平切一刀，垂直切一刀，得到4片。
n=1时，横着或竖着对折一下，再从中心水平切一刀，垂直切一刀，得到6片。

思路

先说结论
假设a是横着对折的次数，b是竖着对折的次数
则最终纸片数为
$(2^{a}+1)(2^{b}+1)$(2a+1)(2b+1)
我们以虚线代表折痕，实线代表切割，
相当于每个折痕构成的小片被十字斩。
一次横折和一次竖折表示为

则a次横折和b次竖折可以表示为

故结果为$(2^{a}+1)(2^{b}+1)$(2a+1)(2b+1)
然后期望就很好懂了

一开始我直接没考虑组合，直接算的所有等可能。。。
最后算出来即可。
下面是推导过程

实现代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int qmi(int a,int b){
	int res=1;
	while(b){
		if(b&1)res=res*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return res;
}

signed main(){
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		int a=qmi(2,n)+1;
		a%=mod;
		int b=2*qmi(3,n)%mod*qmi(qmi(2,n),mod-2)%mod;
		cout<<(a+b)%mod<<endl;
	}
	return 0;
}