ZJOI2019 Day2 游记
不知道会怎么样呢
update: 凉了
update: 进队了...欧是真的欧
不知道会怎么样呢
update: 凉了
update: 进队了...欧是真的欧
给定一个长为 \(n\) 的序列 \(A_1,\dotsc,A_n\)，求一个长为 \(n\) 的不下降序列 \(B_1,\dotsc,B_n\)，使得 \(\sum_{i=1}^n (A_i-B_i)^2\) 最小，只需要输出最小值
以及 \(m\) 次互相独立的修改，每次会更改一个位置的值，要求输出修改后的答案
模 \(998244353\)
\(n,m\le 10^5\)
Codeforces 1090H. Linearization
定义一个长度为 \(n(n=2^k,k\in N)\) 的 01 串 \(s\)（从 0 开始标号）是线性的，当且仅当存在整数 \(x\) 和 二进制数位 \(b\)，使得 \(\forall i\in [0,n),s_i=P(i~{\rm and}~x)~{\rm xor}~b\)，其中 \(P(a)\) 表示 \(a\) 的二进制表示中 \(1\) 的数量的奇偶性
定义一个 01 串的线性化难度为，进行最少的取反一个区间的操作，使之成为线性的操作次数
给定一个长度为 \(m\) 的 01 串 \(t\)，\(q\) 次询问指定一个子串，要求计算其线性化难度
\(m,q\le 2\times 10^5\)
小 R 和小 B 玩了 \(n\) 局游戏，第一局小 R 获胜的概率是 \(p_1\)，对于第 \(i(1<i\le n)\) 局，若第 \(i-1\) 局小 R 获胜，则小 R 获胜的概率为 \(p_i\)，否则为 \(q_i\)
现在已经知道了若干局的胜负情况，求小 R 获胜次数的期望，在 \(m\) 次增加或删除已知条件后都输出答案
\(n,m\le 2\times 10^5\)
后面的游戏结果会影响前面的概率 = =
这么快就到了啊
\[ [d|n]=\frac{1}{d} \sum_{i=0}^{d-1} \omega_d^{i\times n} \]
其中 \(\omega_d\) 是 \(d\) 次单位根
当 \(d|n\)，右边和式中每一项都为 \(1\)
当 \(d\nmid n\)，容易得到右边为 \(0\)
深秋。冷风吹散了最后一丝夏日的暑气，也吹落了榕树脚下灌木丛的叶子。相识数年的 Evan 和 Lyra 再次回到了小时候见面的茂盛榕树之下。小溪依旧，石桥依旧，榕树虽是历经荣枯更迭，依旧亭亭如盖，只是 Evan 和 Lyra 再也不是七八年前不经世事的少年了。
……
有一个没有前导零的 \(n\) 位十进制数 \(S_1 S_2\dotsc S_n\)，\(m\) 条限制，一条限制形如 \(S_{l_1}S_{l_1+1}\dotsc S_{r_2}\) 与 \(S_{l_2}S_{l_2+1}\dotsc S_{r_2}\) 这两个子串需要完全相同
问有多少种合法的方案
模 \(10^9+7\)