07/14 15:35

原题题面

Given n, find the value of ∫ 0 1 ( x − x 2 ) n   d x \int_0^1 {(x-x^2)^n} \,{\rm d}x 01(xx2)ndx.
It can be proved that the value is a rational number p q \frac{p}{q} qp.
Print the result as p ⋅ q − 1   m o d   998244353 p·q^{-1}\ mod\ 998244353 pq1 mod 998244353.

输入描述

he input consists of several test cases and is terminated by end-of-file.
Each test case contains an integer n.

• 1 ≤ n ≤ 1 0 6 1 \leq n \leq 10^6 1n106
• The number of test cases does not exceed 1 0 5 10^5 105.

1
2
3

166374059
432572553
591816295

题面解析

#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
long long quick_mul (long long a,long long b,long long c)//快速乘
{
return (a*b-(long long)((long double)a*b/c)*c+c)%c;
}
long long quick_pow (long long a,long long b,long long c)//快速幂
{
long long ans=1,base=a;
while (b!=0)
{
if (b&1)
ans=quick_mul (ans,base,c);
base=quick_mul (base,base,c);
b>>=1;
}
return ans%c;
}
long long factoral[2000050];
void init()
{
factoral[0]=1;
for(int i=1; i<=2000001; i++)
{
factoral[i]=i*factoral[i-1]%mod;
}
}
int main()
{
long long n;
init();
while(~scanf("%lld",&n))
{
long long sum=factoral[2*n+1];
long long sum1=quick_pow(factoral[n],mod-2,mod);
sum1=quick_pow(sum1,2,mod);
sum=sum*sum1%mod;
printf("%lld\n",quick_pow(sum,mod-2,mod));
}
}


OEIS真好玩 A002457

0
0 收藏

0 评论
0 收藏
0