当前位置：首页 > news >正文

2020 牛客多校第一场J - Easy Integration（求积分/找规律）

news 来源：原创 2024/5/19 7:44:20

传送门

首先我们写下每一项：

$n = 1$ ： $\frac{1}{2}-\frac{1}{3}$
$n = 2$ ： $\frac{1}{3}-\frac{2}{4}+\frac{1}{5}$
$n = 3$ ： $\frac{1}{4}-\frac{3}{5}+\frac{3}{6}-\frac{1}{7}$
$n = 4$ ：…

没错，分子就是组合数 $C_n^i$ ，分母是从 $n + 1$ 到 $2 * n + 1$ 一共 $n + 1$ 个数，而且正负是交替的，写成通项公式也就是：

$\sum_{i=n+1}^{2*n+1}(-1)^j\frac{C_n^j}{i}$ ， $j$ 从0到n，共 $n + 1$ 项

一开始写到这里以为大功告成了，冷静分析一波发现时间复杂度为 $O (T * n)$ ，当时心里拔凉拔凉，想着去化简这个通式，发现无从下手

大概过了一个小时，尝试另外一个策略，求出每一项的解，看看有没有规律，答案是有的！可以计算得到

$n = 1$ ： $\frac{1}{6}=\frac{1}{2*3}$
$n = 2$ ： $\frac{2}{60}=\frac{2}{3*4*5}$
$n = 3$ ： $\frac{6}{840}=\frac{6}{4*5*6*7}$
$n = 4$ ： $\frac{24}{15120}=\frac{24}{5*6*7*8*9}$
$n = 5$ ： $\frac{120}{332640}=\frac{120}{6*7*8*9*10*11}$

分母的规律显而易见，而分子实际上和 $n$ 对应起来就是一个递推式，也就是 $f (i) = i * f (i - 1)$ ，而且，实际上不就是 $i!$ 吗（比赛没有想到= =），而分母还可以写成 $\frac{(2*n+1)!}{n!}$ ，即最后的答案 $\frac{(n!)^2}{(2*n+1)!}$

只需要使用阶乘的逆元这一知识点即可，另外注意预处理 $2 e 6$ 范围内的阶乘和逆元

实际上正规的解法应该是求积分：

在这里插入图片描述
然后看到还有这种解法，贝塔函数是概率论的一个函数模型

在这里插入图片描述

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <bitset>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int p=998244353;
const int maxn=2e6+100;

ll fact[maxn];
ll inv[maxn];

ll quick_mod(ll x,ll n,ll p){
	ll ans=1;
    while(n){
        if(n&1) ans=ans*x%p;
        x=x*x%p;
        n>>=1;
    }
	return ans;
}

void solve(int n){
	fact[0]=1;
	for (int i=1;i<=n; i++) {
		fact[i]=fact[i-1]*i%p;
	}
	inv[n]=quick_mod(fact[n],p-2,p);
	for (int i=n-1;i>=0;i--) {
		inv[i]=inv[i+1]*(i+1)%p;
	}
}


int main(){
    int n;
    solve(maxn-10);
    while(cin>>n){
        ll ans=(fact[n]*fact[n])%p*inv[2*n+1]%p;
        cout<<ans<<endl;
    }
}