![打卡信奥刷题（3415）用C++实现信奥题 P10143 [WC2024] 代码堵塞](images/news1.jpg)
P10143 [WC2024] 代码堵塞题目描述小ℶ\bethℶ为了纪念停办的 codejam准备了一场“代码堵塞纪念赛”。小ℶ\bethℶ的朋友小℧\mho℧也来围观于是小ℶ\bethℶ想预测小℧\mho℧的成绩。比赛共TTT秒有nnn道题。第i(1≤i≤n)i(1 \le i \le n)i(1≤i≤n)题分数为aia_iai小ℶ\bethℶ预测小℧\mho℧需要tit_iti秒完成。题目有两种类型结果可见和结果不可见。结果不可见的题在比赛结束后才能知道评测结果而结果可见的题在提交后立即得到评测结果。小ℶ\bethℶ还没确定每道题的类型。小℧\mho℧由于从不写对拍所以会先按编号从小到大完成所有结果可见的题再按编号从小到大完成所有结果不可见的题。小℧\mho℧会花tit_iti秒完成第iii题当小℧\mho℧花费在第iii题和在第iii题之前完成的所有题的时间总和不超过TTT就会在第iii题产生提交。由于小℧\mho℧提交即 AC所以小ℶ\bethℶ想知道对于所有2n2^n2n种确定nnn道题类型的方案小℧\mho℧所能得到的分数总和的和。由于答案很大你需要将答案对998244353998244353998244353取模。输入格式输入的第一行包含三个整数c,n,Tc, n, Tc,n,T表示测试点编号题数和比赛时间。样例中的ccc表示其满足的限制条件与第ccc个测试点一致。输入的第二行包含nnn个整数a1,a2,⋯ ,ana_1, a_2, \cdots , a_na1,a2,⋯,an分别表示每道题的分数。输入的第三行包含nnn个整数t1,t2,⋯ ,tnt_1, t_2, \cdots , t_nt1,t2,⋯,tn分别表示小℧\mho℧做每道题的时间。输出格式输出一行包含一个整数表示对于所有确定nnn道题类型的方案小℧\mho℧所能得到的分数总和的和对998244353998244353998244353取模。输入输出样例 #1输入 #11 3 3 2 3 4 1 2 2输出 #140说明/提示样例 1 解释我们用长度为333的010101序列表示题目类型111表示结果可见000表示结果不可见。(0,0,0)(1,0,0)(1,1,0)(1,1,1)(0, 0, 0)(1, 0, 0)(1, 1, 0)(1, 1, 1)(0,0,0)(1,0,0)(1,1,0)(1,1,1)四种情况小℧\mho℧按照编号顺序做题前两题产生提交分数和为555(0,1,0)(0, 1, 0)(0,1,0)小℧\mho℧按照213213213的顺序做题前两题产生提交分数和为555(0,0,1)(0, 0, 1)(0,0,1)小℧\mho℧按照312312312的顺序做题第一题和第三题产生提交分数和为666(1,0,1)(1, 0, 1)(1,0,1)小℧\mho℧按照132132132的顺序做题第一题和第三题产生提交分数和为666(0,1,1)(0, 1, 1)(0,1,1)小℧\mho℧按照231231231的顺序做题只有第二题产生提交分数和为333。因此答案为(5×45663) mod 99824435340(5 \times 4 5 6 6 3) \bmod 998244353 40(5×45663)mod99824435340。数据范围对于所有测试数据1≤n≤2001\le n\le 2001≤n≤2001≤T≤3×1051\le T\le 3\times 10^51≤T≤3×105∀1≤i≤n,1≤ai≤3×105\forall 1\le i\le n , 1\le a_i\le 3\times 10^5∀1≤i≤n,1≤ai≤3×105∀1≤i≤n,1≤ti≤T\forall 1\le i\le n, 1\le t_i\le T∀1≤i≤n,1≤ti≤T。测试点编号$n\le $$T\le $特殊性质 A特殊性质 B1∼41\sim 41∼415151510210^2102否否5∼75\sim 75∼72002002003×1053\times 10^53×105是是8,98,98,92002002003×1053\times 10^53×105是否10∼1310\sim 1310∼132002002003×1053\times 10^53×105否是14∼1614\sim 1614∼1650505010310^3103否否17,1817,1817,1810210^210210410^4104否否19,2019,2019,202002002003×1053\times 10^53×105否否特殊性质 A∀1≤i≤n,ai1\forall 1 \le i \le n, a_i 1∀1≤i≤n,ai1。特殊性质 B∀1≤i≤n,ti1\forall 1 \le i \le n, t_i 1∀1≤i≤n,ti1。后记“你们这比赛怎么所有题都结果不可见啊”#includebits/stdc.husingnamespacestd;typedeflonglongll;constintMAXN2e210;constintMAXM3e510;constintmod998244353;intn,m,a[MAXN],t[MAXN];ll dp[MAXM],p2[MAXM],sum[MAXM],ans,tot;intmain(){scanf(%*d%d%d,n,m),*dp*p21;for(inti1;in;i)scanf(%d,a[i]);for(inti1;in;i)scanf(%d,t[i]),sum[i]sum[i-1]t[i];for(inti1;in;i)p2[i]p2[i-1]*2%mod;for(inti1;in;i){tot0;for(intj0;jm-t[i];j)tot(totdp[j])%mod;ans(anstot*p2[n-i]%mod*a[i])%mod;for(intjm;jt[i];j--)dp[j](dp[j]dp[j-t[i]])%mod;}for(inti0;im;i)dp[i]0;*dp1;for(intin;i;i--){tot0;for(intj0;jm-sum[i];j)tot(totdp[j])%mod;ans(anstot*p2[i-1]%mod*a[i])%mod;for(intjm;jt[i];j--)dp[j](dp[j]dp[j-t[i]])%mod;}printf(%lld,ans);}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
打卡信奥刷题（3415）用C++实现信奥题 P10143 [WC2024] 代码堵塞
P10143 [WC2024] 代码堵塞题目描述小ℶ\bethℶ为了纪念停办的 codejam准备了一场“代码堵塞纪念赛”。小ℶ\bethℶ的朋友小℧\mho℧也来围观于是小ℶ\bethℶ想预测小℧\mho℧的成绩。比赛共TTT秒有nnn道题。第i(1≤i≤n)i(1 \le i \le n)i(1≤i≤n)题分数为aia_iai小ℶ\bethℶ预测小℧\mho℧需要tit_iti秒完成。题目有两种类型结果可见和结果不可见。结果不可见的题在比赛结束后才能知道评测结果而结果可见的题在提交后立即得到评测结果。小ℶ\bethℶ还没确定每道题的类型。小℧\mho℧由于从不写对拍所以会先按编号从小到大完成所有结果可见的题再按编号从小到大完成所有结果不可见的题。小℧\mho℧会花tit_iti秒完成第iii题当小℧\mho℧花费在第iii题和在第iii题之前完成的所有题的时间总和不超过TTT就会在第iii题产生提交。由于小℧\mho℧提交即 AC所以小ℶ\bethℶ想知道对于所有2n2^n2n种确定nnn道题类型的方案小℧\mho℧所能得到的分数总和的和。由于答案很大你需要将答案对998244353998244353998244353取模。输入格式输入的第一行包含三个整数c,n,Tc, n, Tc,n,T表示测试点编号题数和比赛时间。样例中的ccc表示其满足的限制条件与第ccc个测试点一致。输入的第二行包含nnn个整数a1,a2,⋯ ,ana_1, a_2, \cdots , a_na1,a2,⋯,an分别表示每道题的分数。输入的第三行包含nnn个整数t1,t2,⋯ ,tnt_1, t_2, \cdots , t_nt1,t2,⋯,tn分别表示小℧\mho℧做每道题的时间。输出格式输出一行包含一个整数表示对于所有确定nnn道题类型的方案小℧\mho℧所能得到的分数总和的和对998244353998244353998244353取模。输入输出样例 #1输入 #11 3 3 2 3 4 1 2 2输出 #140说明/提示样例 1 解释我们用长度为333的010101序列表示题目类型111表示结果可见000表示结果不可见。(0,0,0)(1,0,0)(1,1,0)(1,1,1)(0, 0, 0)(1, 0, 0)(1, 1, 0)(1, 1, 1)(0,0,0)(1,0,0)(1,1,0)(1,1,1)四种情况小℧\mho℧按照编号顺序做题前两题产生提交分数和为555(0,1,0)(0, 1, 0)(0,1,0)小℧\mho℧按照213213213的顺序做题前两题产生提交分数和为555(0,0,1)(0, 0, 1)(0,0,1)小℧\mho℧按照312312312的顺序做题第一题和第三题产生提交分数和为666(1,0,1)(1, 0, 1)(1,0,1)小℧\mho℧按照132132132的顺序做题第一题和第三题产生提交分数和为666(0,1,1)(0, 1, 1)(0,1,1)小℧\mho℧按照231231231的顺序做题只有第二题产生提交分数和为333。因此答案为(5×45663) mod 99824435340(5 \times 4 5 6 6 3) \bmod 998244353 40(5×45663)mod99824435340。数据范围对于所有测试数据1≤n≤2001\le n\le 2001≤n≤2001≤T≤3×1051\le T\le 3\times 10^51≤T≤3×105∀1≤i≤n,1≤ai≤3×105\forall 1\le i\le n , 1\le a_i\le 3\times 10^5∀1≤i≤n,1≤ai≤3×105∀1≤i≤n,1≤ti≤T\forall 1\le i\le n, 1\le t_i\le T∀1≤i≤n,1≤ti≤T。测试点编号$n\le $$T\le $特殊性质 A特殊性质 B1∼41\sim 41∼415151510210^2102否否5∼75\sim 75∼72002002003×1053\times 10^53×105是是8,98,98,92002002003×1053\times 10^53×105是否10∼1310\sim 1310∼132002002003×1053\times 10^53×105否是14∼1614\sim 1614∼1650505010310^3103否否17,1817,1817,1810210^210210410^4104否否19,2019,2019,202002002003×1053\times 10^53×105否否特殊性质 A∀1≤i≤n,ai1\forall 1 \le i \le n, a_i 1∀1≤i≤n,ai1。特殊性质 B∀1≤i≤n,ti1\forall 1 \le i \le n, t_i 1∀1≤i≤n,ti1。后记“你们这比赛怎么所有题都结果不可见啊”#includebits/stdc.husingnamespacestd;typedeflonglongll;constintMAXN2e210;constintMAXM3e510;constintmod998244353;intn,m,a[MAXN],t[MAXN];ll dp[MAXM],p2[MAXM],sum[MAXM],ans,tot;intmain(){scanf(%*d%d%d,n,m),*dp*p21;for(inti1;in;i)scanf(%d,a[i]);for(inti1;in;i)scanf(%d,t[i]),sum[i]sum[i-1]t[i];for(inti1;in;i)p2[i]p2[i-1]*2%mod;for(inti1;in;i){tot0;for(intj0;jm-t[i];j)tot(totdp[j])%mod;ans(anstot*p2[n-i]%mod*a[i])%mod;for(intjm;jt[i];j--)dp[j](dp[j]dp[j-t[i]])%mod;}for(inti0;im;i)dp[i]0;*dp1;for(intin;i;i--){tot0;for(intj0;jm-sum[i];j)tot(totdp[j])%mod;ans(anstot*p2[i-1]%mod*a[i])%mod;for(intjm;jt[i];j--)dp[j](dp[j]dp[j-t[i]])%mod;}printf(%lld,ans);}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
