Paperfolding【组合数】-2020杭电多校5

题意：

纸张对折，允许上下左右四个方向，给出 (n) 次操作，问 (n) 次折叠后从中心横竖裁剪后可得到多少张纸的数学期望。
(1≤T≤10^5,0≤n≤10^{18})
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6822

分析：

可以把折叠操作分为垂直和水平的操作，分别设其操作次数为 (x) 和 (y) ，那么折叠可以将原矩形划分为 (2^x*2^y) 个小矩形，经过裁剪后，可以得到 ((2^x+1)*(2^y+1)) 个矩形。
综合以上分析和二项式定理化简，最终的答案为：

[egin{align} EX & = frac{1}{2^n}sum_{i=0}^{n}{C_{n}^{i}(2^i+1)(2^{n-i}+1)}\ & = frac{1}{2^n}*(4^n+2*3^n+2^n) \ & = 2^n+2*frac{3^n}{2^n}+1 end{align} ]

复杂度：(O(logn))

代码：

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int mod=998244353;
ll power(ll a,ll b)
{
    ll res=1;
    a%=mod;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int main()
{
    int T;
    scanf("%d",&T);
    ll n;
    while(T--)
    {
        scanf("%lld",&n);
        ll ans=0,x=power(2LL,n),y=power(3LL,n);
        ll inv=power(x,mod-2);
        ans=(x+2*y*inv%mod+1)%mod;
        printf("%lld
",ans);
    }
    return 0;
}