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

杨辉三角时间限制1 秒空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述小F对杨辉三角颇有研究他把杨辉三角第n nn行的数提出来从左到右分别为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_{i0}^{n-1} i^2 \times a[i]∑i0n−1​i2×a[i]的值是多少答案对998244353 998244353998244353取模。输入描述输入一个正整数n nnn ≤ 10 18 n \le 10^{18}n≤1018。输出描述输出题目中式子的值答案对998244353 998244353998244353取模。示例 1输入3输出6数据范围1 ≤ n ≤ 10 18 1 \le n \le 10^{18}1≤n≤1018解题思路本题是组合恒等式推导 快速幂的数学问题。给定杨辉三角第n nn行的系数a [ i ] ( n − 1 i ) a[i] \binom{n-1}{i}a[i](in−1​)i 0 , 1 , … , n − 1 i0,1,\dots,n-1i0,1,…,n−1要求计算S ∑ i 0 n − 1 i 2 ⋅ a [ i ] ( m o d 998244353 ) S \sum_{i0}^{n-1} i^2 \cdot a[i] \pmod{998244353}Si0∑n−1​i2⋅a[i](mod998244353)由于n nn可达10 18 10^{18}1018无法逐项计算需要利用二项式系数的矩公式直接得到闭式解。1. 问题等价转化杨辉三角第n nn行从1 11开始计数的第i ii个数为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_{i0}^{n-1} i^2 \binom{n-1}{i}Si0∑n−1​i2(in−1​)利用i 2 i ( i − 1 ) i i^2 i(i-1) ii2i(i−1)i拆分为两个已知的二项式系数加权和S ∑ i 0 n − 1 i ( i − 1 ) ( n − 1 i ) ∑ i 0 n − 1 i ( n − 1 i ) S \sum_{i0}^{n-1} i(i-1)\binom{n-1}{i} \sum_{i0}^{n-1} i\binom{n-1}{i}Si0∑n−1​i(i−1)(in−1​)i0∑n−1​i(in−1​)2. 组合恒等式由二项式定理及其导数可得一阶矩∑ i 0 n − 1 i ( n − 1 i ) ( n − 1 ) 2 n − 2 \sum_{i0}^{n-1} i\binom{n-1}{i} (n-1)2^{n-2}i0∑n−1​i(in−1​)(n−1)2n−2二阶下降阶乘矩∑ i 0 n − 1 i ( i − 1 ) ( n − 1 i ) ( n − 1 ) ( n − 2 ) 2 n − 3 \sum_{i0}^{n-1} i(i-1)\binom{n-1}{i} (n-1)(n-2)2^{n-3}i0∑n−1​i(i−1)(in−1​)(n−1)(n−2)2n−3因此S ( n − 1 ) ( n − 2 ) 2 n − 3 ( n − 1 ) 2 n − 2 ( n − 1 ) 2 n − 3 [ ( n − 2 ) 2 ] n ( n − 1 ) 2 n − 3 S (n-1)(n-2)2^{n-3} (n-1)2^{n-2} (n-1)2^{n-3}\big[(n-2)2\big] n(n-1)2^{n-3}S(n−1)(n−2)2n−3(n−1)2n−2(n−1)2n−3[(n−2)2]n(n−1)2n−3该公式对n ≥ 3 n \ge 3n≥3成立。3. 边界情况n 1 n 1n1只有a [ 0 ] 1 a[0]1a[0]1S 0 S 0S0。n 2 n 2n2第2 22行为1 , 1 1,11,1S 0 2 ⋅ 1 1 2 ⋅ 1 1 S 0^2\cdot1 1^2\cdot1 1S02⋅112⋅11。n ≥ 3 n \ge 3n≥3直接使用公式S n ( n − 1 ) 2 n − 3 m o d M S n(n-1)2^{n-3} \bmod MSn(n−1)2n−3modM。4. 算法实现模数M 998244353 M 998244353M998244353注意代码中误写为99824353 9982435399824353少了一个4应修正为998244353 998244353998244353。对n ≥ 3 n \ge 3n≥3计算ans ( n m o d M ) ⋅ ( ( n − 1 ) m o d M ) ⋅ 2 n − 3 m o d M \text{ans} (n \bmod M)\cdot((n-1)\bmod M)\cdot 2^{n-3} \bmod Mans(nmodM)⋅((n−1)modM)⋅2n−3modM指数n − 3 n-3n−3可达10 18 10^{18}1018但快速幂的时间复杂度为O ( log ⁡ n ) O(\log n)O(logn)约60 6060次乘法无需对指数取模即可直接计算由于底数2 22与M MM互质也可将指数对M − 1 M-1M−1取模但非必需。对n 1 n1n1输出0 00n 2 n2n2输出1 11。5. 复杂度分析时间复杂度快速幂O ( log ⁡ n ) O(\log n)O(logn)其余为常数次乘法。n ≤ 10 18 n \le 10^{18}n≤1018运算量极小。空间复杂度O ( 1 ) O(1)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 n1,2n1,2进行特判并确保模数正确为998244353 998244353998244353。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll MOD99824353;llqpow(ll a,ll b){ll res1;while(b0){if(b1)resres*a%MOD;b1;aa*a%MOD;}returnres;}voidsolve(){ll n;cinn;if(n1){cout0endl;}elseif(n2){cout1endl;}else{cout(n%MOD)*((n-1)%MOD)%MOD*qpow(2,n-3)%MODendl;}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll t1;while(t--){solve();}return0;}