Easy Integration(Wallis积分)(2020牛客多校第一场J题)

07/14 15:35
阅读数 142

原题题面

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K

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

题面解析

比赛时使用了二项式定理拆分,果不其然算不出来了,于是看了题解用了Wallis积分
由于数据组数是 1 e 5 1e5 1e5,而 n n n 1 e 6 1e6 1e6,因此考虑要去推结论。
由于积分形式是 ( X X X X X ) n (XXXXX)^n (XXXXX)n的形式,且括号内的值域为 [ 0 , 1 4 ] [0,\frac{1}{4}] [0,41],故考虑Wallis积分。
简单来说就是如下结果:
在这里插入图片描述
所以我们可以得到如下证明:
在这里插入图片描述





于是我们可以很轻松地得到代码:

#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
分享
在线直播报名
返回顶部
顶部