Fork me on GitHub

Wannafly挑战赛17 B

发表于 | 分类于

题目描述

Ans = 0;
For(inti = 1; i <= n; i++)
For(int v = 0; v <= n; v++)
Ans = (Ans + C(i, v) * C(i, v)) % 998244353;
C(i,v)为组合数第i行第v列的数。
给你上面的代码中的n，请你输出Ans的值。

输入描述:

输入一个整数n

输出描述:

输出Ans的值。

输入

3

输出

28
备注:
n<=106

思路：

推出公式(2n)!/n!n!,然后递推求和。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
long long x=0,y=0,mod=998244353;
void gcd(long long n,long long m,long long &x,long long &y)
{
   if(!m)
   {
       x=1,y=0;
       return;
   }
   gcd(m,n%m,y,x);
   y-=n/m*x;
}
int main()
{
    long long n,gg=2,g=2;
    std::cin>>n;

    for(long long i=2;i<=n;i++)
    {
        g=g*(i*2)%mod*(i*2-1)%mod;
        long long f=i*i%mod;
        x=0,y=0;
        gcd(f,mod,x,y);
        g=g*(x%mod+mod)%mod;
        gg=(gg+g)%mod;
    }
    std::cout<<gg<<std::endl;
}

总结：还要加强递推。