HDU多校5 - 6822 Paperfolding(组合数学)

题目链接：点击查看

题目大意：给出一张纸，每次对折可以向上，下，左，右四个方向对折，都是等概率的，现在问对折 n 次后，在中心画一个十字切开后能切成几份

题目分析：模拟一下可以看出水平对折和垂直对折相互独立，因为总的对折次数为 n ，所以设水平对折的次数为 x ，那么垂直对折的次数就是 y 次，且满足 x + y = n ，答案就是 ( 2^x + 1 ) * ( 2^y + 1 )

这样期望就是，写这篇博客重点是记录一下化简的过程，需要用到的前置知识就是：

C(n,m)表示组合数学n个数中选m个的方案数：C(n,0)+C(n,1)+...+C(n,n)=2^n

二项式定理：

代码：
 

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;const int mod=998244353;LL q_pow(LL a,LL b) {LL ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans; }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){LL n;scanf("%lld",&n);printf("%lld\n",(q_pow(2,n)+1+2*q_pow(3,n)*q_pow(q_pow(2,n),mod-2)%mod)%mod);}return 0; }

 

总结

以上是生活随笔为你收集整理的HDU多校5 - 6822 Paperfolding(组合数学)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。