杨辉三角【牛客tracker & 每日一题】

杨辉三角

时间限制：1 秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

小F对杨辉三角颇有研究，他把杨辉三角第

n

n

n 行的数提出来，从左到右分别为

a

[

0

]

,

a

[

1

]

,

…

,

a

[

n

−

1

]

a[0], a[1], \\dots, a[n-1]

a[0],a[1],…,a[n−1]。

现在他想知道

∑

i

=

0

n

−

1

i

2

×

a

[

i

]

\\sum_{i=0}^{n-1} i^2 \\times a[i]

∑i=0n−1​i2×a[i] 的值是多少，答案对

998244353

998244353

998244353 取模。

输入描述

输入一个正整数

n

n

n，

n

≤

10

18

n \\le 10^{18}

n≤1018。

输出描述

输出题目中式子的值，答案对

998244353

998244353

998244353 取模。

示例 1

输入：

3

输出：

6

数据范围

• $1\le n\le 10^{18}$

解题思路

本题是组合恒等式推导 + 快速幂的数学问题。给定杨辉三角第

n

n

n 行的系数

a

[

i

]

=

(

n

−

1

i

)

a[i] = \\binom{n-1}{i}

a[i]=(in−1​)（

i

=

0

,

1

,

…

,

n

−

1

i=0,1,\\dots,n-1

i=0,1,…,n−1），要求计算

S

=

∑

i

=

0

n

−

1

i

2

⋅

a

[

i

]

(

m

o

d

998244353

)

S = \\sum_{i=0}^{n-1} i^2 \\cdot a[i] \\pmod{998244353}

S=i=0∑n−1​i2⋅a[i](mod998244353) 由于

n

n

n 可达

10

18

10^{18}

1018，无法逐项计算，需要利用二项式系数的矩公式直接得到闭式解。

1. 问题等价转化

杨辉三角第

n

n

n 行（从

1

1

1 开始计数）的第

i

i

i 个数为

a

[

i

]

=

(

n

−

1

i

)

a[i] = \\binom{n-1}{i}

a[i]=(in−1​)。于是目标为

S

=

∑

i

=

0

n

−

1

i

2

(

n

−

1

i

)

S = \\sum_{i=0}^{n-1} i^2 \\binom{n-1}{i}

S=i=0∑n−1​i2(in−1​) 利用

i

2

=

i

(

i

−

1

)

+

i

i^2 = i(i-1) + i

i2=i(i−1)+i，拆分为两个已知的二项式系数加权和：

S

=

∑

i

=

0

n

−

1

i

(

i

−

1

)

(

n

−

1

i

)

+

∑

i

=

0

n

−

1

i

(

n

−

1

i

)

S = \\sum_{i=0}^{n-1} i(i-1)\\binom{n-1}{i} + \\sum_{i=0}^{n-1} i\\binom{n-1}{i}

S=i=0∑n−1​i(i−1)(in−1​)+i=0∑n−1​i(in−1​)

2. 组合恒等式

由二项式定理及其导数可得：

• 一阶矩： $$\sum _{i=0}^{n-1}i\left(\genfrac{}{}{0ex}{}{n-1}{i}\right)=(n-1)2^{n-2}$$
• 二阶下降阶乘矩： $$\sum _{i=0}^{n-1}i(i-1)\left(\genfrac{}{}{0ex}{}{n-1}{i}\right)=(n-1)(n-2)2^{n-3}$$

3. 边界情况

• $n=1$
• $n=2$
• $n\ge 3$

4. 算法实现

• 模数 $M=998244353$
• 对 $n\ge 3$
• 指数 $n-3$
• 对 $n=1$

5. 复杂度分析

• 时间复杂度：快速幂 $O(\log n)$
• 空间复杂度：$O(1)$

总结

利用二项式系数的矩公式，将复杂的加权和化简为

n

(

n

−

1

)

2

n

−

3

n(n-1)2^{n-3}

n(n−1)2n−3，再通过快速幂在

O

(

log

⁡

n

)

O(\\log n)

O(logn) 时间内求出模意义下的结果。注意对

n

=

1

,

2

n=1,2

n=1,2 进行特判，并确保模数正确为

998244353

998244353

998244353。

代码内容

#include <bits/stdc++.h>
using namespace std;

#define endl '\\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=1e3+10;
const ll INF=1e18;
const ll M=1e6+10;
const ll MOD=99824353;

ll qpow(ll a,ll b)
{
ll res=1;
while(b>0)
{
if(b&1)res=res*a%MOD;
b>>=1;
a=a*a%MOD;
}
return res;
}

void solve()
{
ll n;
cin>>n;
if(n==1)
{
cout<<0<<endl;
}
else if(n==2)
{
cout<<1<<endl;
}
else
{
cout<<(n%MOD)*((n–1)%MOD)%MOD*qpow(2,n–3)%MOD<<endl;
}
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
ll t=1;
while(t—)
{
solve();
}
return 0;
}