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\)
没有思维能力了
给你一棵 \(n\) 个点的树，有点权\(a_1,..,a_n\)，整棵树是一个1级区域
除非 \(i\)
是最后一个等级，否则每一个i级区域都要被分成至少两个i+1级区域
每个点必须恰好属于一个每种等级的区域
一个区域必须是连通的
每个相同等级的区域必须拥有相同的点权和
求有多少种不同的划分方案，模 \(10^9+7\)
\(n\le 10^6,a_i\le 10^9\)
NOIP2018 唯一没做出来的题
要是写完两题后直接去打暴力大概也不止50分吧
反正确实跪在这题了
你有一个 \(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\)