打卡信奥刷题（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

输入 #1

1 3 3 2 3 4 1 2 2

输出 #1

说明/提示

样例 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×4+5+6+6+3) mod 998244353=40(5 \times 4 + 5 + 6 + 6 + 3) \bmod 998244353 = 40(5×4+5+6+6+3)mod998244353=40。

数据范围

对于所有测试数据：

1≤n≤2001\le n\le 2001≤n≤200，
1≤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	特殊性质 B
1∼41\sim 41∼4	151515	10210^2102	否	否
5∼75\sim 75∼7	200200200	3×1053\times 10^53×105	是	是
8,98,98,9	200200200	3×1053\times 10^53×105	是	否
10∼1310\sim 1310∼13	200200200	3×1053\times 10^53×105	否	是
14∼1614\sim 1614∼16	505050	10310^3103	否	否
17,1817,1817,18	10210^2102	10410^4104	否	否
19,2019,2019,20	200200200	3×1053\times 10^53×105	否	否

特殊性质 A：∀1≤i≤n,ai=1\forall 1 \le i \le n, a_i = 1∀1≤i≤n,ai=1。
特殊性质 B：∀1≤i≤n,ti=1\forall 1 \le i \le n, t_i = 1∀1≤i≤n,ti=1。

后记

“你们这比赛怎么所有题都结果不可见啊？”

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintMAXN=2e2+10;constintMAXM=3e5+10;constintmod=998244353;intn,m,a[MAXN],t[MAXN];ll dp[MAXM],p2[MAXM],sum[MAXM],ans,tot;intmain(){scanf("%*d%d%d",&n,&m),*dp=*p2=1;for(inti=1;i<=n;i++)scanf("%d",&a[i]);for(inti=1;i<=n;i++)scanf("%d",&t[i]),sum[i]=sum[i-1]+t[i];for(inti=1;i<=n;i++)p2[i]=p2[i-1]*2%mod;for(inti=1;i<=n;i++){tot=0;for(intj=0;j<=m-t[i];j++)tot=(tot+dp[j])%mod;ans=(ans+tot*p2[n-i]%mod*a[i])%mod;for(intj=m;j>=t[i];j--)dp[j]=(dp[j]+dp[j-t[i]])%mod;}for(inti=0;i<=m;i++)dp[i]=0;*dp=1;for(inti=n;i;i--){tot=0;for(intj=0;j<=m-sum[i];j++)tot=(tot+dp[j])%mod;ans=(ans+tot*p2[i-1]%mod*a[i])%mod;for(intj=m;j>=t[i];j--)dp[j]=(dp[j]+dp[j-t[i]])%mod;}printf("%lld",ans);}