牛客训练赛52 A题题解

牛客训练赛52 A题

解题思路
打表+快速幂

#include<iostream>
using namespace std;
#define maxn 10000005
long long fac_num[maxn]={0};


void fac(long long n)
{
    for(long long i=2;i<=n;i++)
    {
        fac_num[i-1]=(fac_num[i-2]*i)%998244353;
    }
}

long long binaryPow(long long a,long long b,long long m)
{
    if(b==0) return 1;
    if(b%2==1) return a*binaryPow(a,b-1,m)%m;
    else
    {
        long long mul=binaryPow(a,b/2,m);
        return mul*mul%m;
    }
}

int main()
{
    int T;
    fac_num[0]=1;
    fac(maxn);
    while(scanf("%d",&T)!=EOF)
    {
        while(T--)
        {
            long long n;
            scanf("%lld",&n);
            long long sum=((1+n)*n/2)%998244353;
            sum=sum*sum;
            printf("%d ",sum%998244353);
            printf("%d%c",binaryPow(fac_num[n-1],2*n,998244353),"\n"[T==0]);
        }
    }
    return 0;
 }