Wannafly17-B-求值2（找公式）

链接： https://www.nowcoder.com/acm/contest/114/B 来源：牛客网 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld

题目描述

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的值。 示例1

输入

复制 3

输出

复制 28

补充：n<=10^6

本题完全就是用个组合数的模板在百度条公式就可以做出来，比第一题还要水，可是我居然忘记了给结果取模。

就一直wa，最后知道真相的我眼泪流下来。

公式：[C(n,0)]^2+.....+[C(n,n)^2]=C(2n,n)

#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <vector> #include <map> #define ll long long #define M 998244353 #define x 2000001 using namespace std; ll fac[x]={1,1},inv[x]={1,1},f[x]={1,1}; ll C(ll a,ll b){     if(b>a)return 0;     return fac[a]*inv[b]%M*inv[a-b]%M; } void init(){     for(int i=2;i<x;i++){         fac[i]=fac[i-1]*i%M;         f[i]=(M-M/i)*f[M%i]%M;         inv[i]=inv[i-1]*f[i]%M;     } }    int main() {     int n;     ll ans=0;     scanf("%d",&n);     init();     for(int i=1;i<=n;i++){             ans=ans+C(2*i,i)%M;     }     cout <<ans%M<<endl;     return 0; }