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$

没有思维能力了

Codeforces 1034C

题意

给你一棵 $n$ 个点的树，有点权$a_1,..,a_n$，整棵树是一个1级区域

• 除非 $i$ 是最后一个等级，否则每一个i级区域都要被分成至少两个i+1级区域

• 每个点必须恰好属于一个每种等级的区域

• 一个区域必须是连通的

• 每个相同等级的区域必须拥有相同的点权和

求有多少种不同的划分方案，模 $10^9+7$

$n\le 10^6,a_i\le 10^9$

NOIP2018 唯一没做出来的题

要是写完两题后直接去打暴力大概也不止50分吧

反正确实跪在这题了

Luogu P5023

题意

你有一个 $n$ 行 $m$ 列的矩阵，左上角为 $(0,0)$

每一个位置有一个数字 $0/1$

你需要从 $(0,0)$ 走到 $(n-1,m-1)$，只能向右或向下走 $(R/D)$，一共 $n+m-2$ 步，这会形成一条路径

把方向记下来可以得到同样长度的只包含 $R/D$ 的字符串 $w(P)$

并且经过的 $n+m-1$ 个位置的数字连起来可以得到一个 $01$ 串 $s(P)$

你需要求出有多少种填数的方案，使得对于任意两条路径 $P_1,P_2$，若 $w(P_1)>w(P_2)$，那么 $s(P_1)\le s(P_2)$

模 $10^9+7$

$n\le 8,m\le 10^6$