P11617 [PumpkinOI Round 1] 递推题目背景一个简单的问题什么是递推题目描述定义一个数列{a0…an−1}\{a_0 \dots a_{n - 1} \}{a0…an−1}的递推式为满足下式的序列{r0…rm}\{r_0\dots r_m\}{r0…rm}∑j0mrjai−j0,∀i≥m\sum_{j 0} ^ m r_j a_{i - j} 0, \forall i \ge mj0∑mrjai−j0,∀i≥mmmm称为该递推式的阶数。特别地r0≠0r_0\neq 0r00。给你一个无限长的数列{ai}\{a_i\}{ai}的前nnn项以及数列{ai}\{a_i\}{ai}的一个阶数为nnn的递推式{bi}\{b_i\}{bi}。要求求出数列{ai}\{a_i\}{ai}的所有项之和。答案对998244353998244353998244353取模。可以证明对于任意一个模998244353998244353998244353意义下输入都存在实数意义下的一个对应数列的答案是收敛的。输入格式第一行一个正整数nnn。第二行输入nnn个整数表示序列{ai}\{a_i\}{ai}的前nnn项即{a0…an−1}\{a_0 \dots a_{n-1}\}{a0…an−1}在模998244353998244353998244353意义下的值。第三行输入n1n1n1个整数表示递推式{b0…bn}\{b_0\dots b_n\}{b0…bn}在模998244353998244353998244353意义下的值。输出格式输出一行一个整数表示数列{ai}\{a_i\}{ai}的所有项之和对998244353998244353998244353取模的结果。保证答案可以在模998244353998244353998244353意义下表示即如果最终的答案为分数qp\frac qppq可以证明答案肯定是一个有理数保证p≢0(mod998244353)p\not\equiv0\pmod {998244353}p≡0(mod998244353)。输入输出样例 #1输入 #11 1 1 499122176输出 #12输入输出样例 #2输入 #22 1 1 1 199648870 99824435输出 #214输入输出样例 #3输入 #31 1 1 499122177输出 #3665496236说明/提示样例解释 #1499122176≡−12(mod998244353)499122176\equiv -\frac12\pmod {998244353}499122176≡−21(mod998244353)。∀i≥n,ai−12×ai−10\forall i\ge n,a_i-\frac12\times a_{i-1}0∀i≥n,ai−21×ai−10即ai12×ai−1a_i\frac12\times a_{i-1}ai21×ai−1即数列{ai}\{a_i\}{ai}是等比数列1,12,14,…1,\frac12,\frac14,\dots1,21,41,…。其和收敛于222。样例解释 #2199648870≡−0.6(mod998244353),99824435≡−0.3(mod998244353)199648870\equiv -0.6\pmod {998244353},99824435\equiv -0.3\pmod {998244353}199648870≡−0.6(mod998244353),99824435≡−0.3(mod998244353)。∀i≥n,ai−0.6×ai−1−0.3×ai−20\forall i\ge n,a_i-0.6\times a_{i-1}-0.3\times a_{i-2}0∀i≥n,ai−0.6×ai−1−0.3×ai−20即ai0.6×ai−10.3×ai−2a_i0.6\times a_{i-1}0.3\times a_{i-2}ai0.6×ai−10.3×ai−2。经计算其和收敛于141414。本题使用子任务捆绑/依赖对于所有子任务1≤n≤5×1031\le n\le5\times 10^31≤n≤5×1030≤ai,bi9982443530\le a_i,b_i 9982443530≤ai,bi998244353。特别地b0≠0b_0\neq 0b00。子任务编号分值n≤n\len≤依赖111303030111无2223030302221113334040405×1035\times 10^35×1031,21,21,2C实现#includebits/stdc.h#defineintlonglongconstintmod998244353;constintMAXN5e310;usingnamespacestd;inlineintread(void){intres0;boolflagtrue;charcgetchar();while(c0||c9){flag^(c-);cgetchar();}while(c0c9){res(res3)(res1)(c^48);cgetchar();}returnflag?res:-res;}intqpow(inta,intk){intans1;while(k){if(k1)ansans*a%mod;aa*a%mod;k1;}returnans;}intn,a[MAXN],r[MAXN];signedmain(void){nread();for(inti0;in;i)a[i]read();intsum0,res0,sum20;for(inti0;in;i)r[i]read();for(intin;i0;i--){sum2(sum2r[i])%mod;sum(sumres*r[i])%mod;res(resa[n-i])%mod;}printf(%lld\n,sum*qpow(sum2,mod-2)%mod);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
打卡信奥刷题（3595）用C++实现信奥题 P11617 [PumpkinOI Round 1] 递推
P11617 [PumpkinOI Round 1] 递推题目背景一个简单的问题什么是递推题目描述定义一个数列{a0…an−1}\{a_0 \dots a_{n - 1} \}{a0…an−1}的递推式为满足下式的序列{r0…rm}\{r_0\dots r_m\}{r0…rm}∑j0mrjai−j0,∀i≥m\sum_{j 0} ^ m r_j a_{i - j} 0, \forall i \ge mj0∑mrjai−j0,∀i≥mmmm称为该递推式的阶数。特别地r0≠0r_0\neq 0r00。给你一个无限长的数列{ai}\{a_i\}{ai}的前nnn项以及数列{ai}\{a_i\}{ai}的一个阶数为nnn的递推式{bi}\{b_i\}{bi}。要求求出数列{ai}\{a_i\}{ai}的所有项之和。答案对998244353998244353998244353取模。可以证明对于任意一个模998244353998244353998244353意义下输入都存在实数意义下的一个对应数列的答案是收敛的。输入格式第一行一个正整数nnn。第二行输入nnn个整数表示序列{ai}\{a_i\}{ai}的前nnn项即{a0…an−1}\{a_0 \dots a_{n-1}\}{a0…an−1}在模998244353998244353998244353意义下的值。第三行输入n1n1n1个整数表示递推式{b0…bn}\{b_0\dots b_n\}{b0…bn}在模998244353998244353998244353意义下的值。输出格式输出一行一个整数表示数列{ai}\{a_i\}{ai}的所有项之和对998244353998244353998244353取模的结果。保证答案可以在模998244353998244353998244353意义下表示即如果最终的答案为分数qp\frac qppq可以证明答案肯定是一个有理数保证p≢0(mod998244353)p\not\equiv0\pmod {998244353}p≡0(mod998244353)。输入输出样例 #1输入 #11 1 1 499122176输出 #12输入输出样例 #2输入 #22 1 1 1 199648870 99824435输出 #214输入输出样例 #3输入 #31 1 1 499122177输出 #3665496236说明/提示样例解释 #1499122176≡−12(mod998244353)499122176\equiv -\frac12\pmod {998244353}499122176≡−21(mod998244353)。∀i≥n,ai−12×ai−10\forall i\ge n,a_i-\frac12\times a_{i-1}0∀i≥n,ai−21×ai−10即ai12×ai−1a_i\frac12\times a_{i-1}ai21×ai−1即数列{ai}\{a_i\}{ai}是等比数列1,12,14,…1,\frac12,\frac14,\dots1,21,41,…。其和收敛于222。样例解释 #2199648870≡−0.6(mod998244353),99824435≡−0.3(mod998244353)199648870\equiv -0.6\pmod {998244353},99824435\equiv -0.3\pmod {998244353}199648870≡−0.6(mod998244353),99824435≡−0.3(mod998244353)。∀i≥n,ai−0.6×ai−1−0.3×ai−20\forall i\ge n,a_i-0.6\times a_{i-1}-0.3\times a_{i-2}0∀i≥n,ai−0.6×ai−1−0.3×ai−20即ai0.6×ai−10.3×ai−2a_i0.6\times a_{i-1}0.3\times a_{i-2}ai0.6×ai−10.3×ai−2。经计算其和收敛于141414。本题使用子任务捆绑/依赖对于所有子任务1≤n≤5×1031\le n\le5\times 10^31≤n≤5×1030≤ai,bi9982443530\le a_i,b_i 9982443530≤ai,bi998244353。特别地b0≠0b_0\neq 0b00。子任务编号分值n≤n\len≤依赖111303030111无2223030302221113334040405×1035\times 10^35×1031,21,21,2C实现#includebits/stdc.h#defineintlonglongconstintmod998244353;constintMAXN5e310;usingnamespacestd;inlineintread(void){intres0;boolflagtrue;charcgetchar();while(c0||c9){flag^(c-);cgetchar();}while(c0c9){res(res3)(res1)(c^48);cgetchar();}returnflag?res:-res;}intqpow(inta,intk){intans1;while(k){if(k1)ansans*a%mod;aa*a%mod;k1;}returnans;}intn,a[MAXN],r[MAXN];signedmain(void){nread();for(inti0;in;i)a[i]read();intsum0,res0,sum20;for(inti0;in;i)r[i]read();for(intin;i0;i--){sum2(sum2r[i])%mod;sum(sumres*r[i])%mod;res(resa[n-i])%mod;}printf(%lld\n,sum*qpow(sum2,mod-2)%mod);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
