You are given a sequence named xxx of length nnn and an integer ccc. You will do the following operations to maintain a subset SSS of A={1,2,…
You are given a sequence named xxx of length nnn and an integer ccc. You will do the following operations to maintain a subset SSS of A={1,2,…,n}A=left{1,2,dots,nright}A={1,2,…,n}: 1. Let z=∑i∈Sxiz=sumlimits_{iin S}x_iz=i∈S∑xi, if (z+c) mod 12=0(z+c) text{mod} 12=0(z+c) mod 12=0 , then stop. 2. Choose a random integer iii that i∈Aiin Ai∈A and i∉Sinotin Si∈S with equal probability. 3. Choose a random integer qqq that q∈Bqin Bq∈B with equal probability, and if q=1q=1q=1, choose a random integer in SSS with equal probability and delete it from SSS. 4. Add iii into SSS. 5. Go to the operation 111. Here, we use the following rules to determine BBB: if there's nothing in SSS, then B={0}B=left{0right}B={0}; else if it's possible to stop the procedure ( maybe after doing several operations in the future ) after adding iii into SSS without deleting anything , then B={0,1}B=left{0,1right}B={0,1}; else B={1}B=left{1right}B={1}. You want to know the expected number of times to do the operation 222. Please print the answer in a single line modulo 998244353998244353998244353. It can be proved that the answer is a rational number, or you can never stop doing those operations. Note: If your answer is PQdfrac PQQP, then you need to find a integer RRR such that R×Q≡P(mod998244353)Rtimes Qequiv P pmod{998244353}R×Q≡P(mod998244353). Print this RRR.
标签： HBC244828核弹剑仙 图论 拓扑排序 数据结构 STLDate题解
