题解 | #杨辉三角#

链接：https://ac.nowcoder.com/acm/problem/223434 来源：牛客网

题目描述 小F对杨辉三角颇有研究，他把杨辉三角第nn行的数提出来，从左到右分别为a[0],a[1],...,a[n-1]a[0],a[1],...,a[n−1]。 现在他想知道\sum_{i=0}^{n-1}{i^{2}\times a[i]}∑ i=0 n−1 ​ i 2 ×a[i]的值是多少，答案对9982435399824353取模。

这个题目其实是个公式的推理和快速幂的使用

因为有：Σni=0Cnn=2n 以及 kCkn=(n−1)Ck−1n−1。

所以：原式 = Σn−1i=0i2Cin−1=Σn−1i=0i×iCin−1=Σn−1i=0i×(n−1)×Ci−1n−2=(n−1)×Σn−1i=0(i−1+1)×Ci−1n−2

拆成两部分：

原式=(n−1)×Σn−1i=1Ci−1n−2+(n−1)×Σn−1i=1(i−1)Ci−1n−2=(n−1)2n−2+(n−1)(n−2)2n−3=n(n−1)2n−3

using namespace std;
typedef long long ll;
#define mod 99824353
long long qpow(long long a, long long b) {
	long long ans = 1;
	for(; b; b >>= 1) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}
int main()
{
    ll n;
    cin>>n;
    if(n==1||n==0){
        printf("0");
        return 0;
    }
    else if(n==2){
        printf("1");
        return 0;
    }
    ll ans;
    ans=((n%mod)*((n-1)%mod))%mod*qpow(2,n-3)%mod;
    printf("%lld",ans);
    return 0;
}