主要思路
这些 3000+ 题目里做过最小清新的。
首先肯定可以想到,分解质因子之后,对于一个 \(p^c\),把每个元素该质因子的指数拿出来做中位数即为此质因子的贡献。我大概想到这里就断片了。
Continue reading →这些 3000+ 题目里做过最小清新的。
首先肯定可以想到,分解质因子之后,对于一个 \(p^c\),把每个元素该质因子的指数拿出来做中位数即为此质因子的贡献。我大概想到这里就断片了。
Continue reading →好您妈神仙啊。
考虑用 Lucas 把组合数分解:
\[ {n \choose m} = {n / k \choose m / k} {n \mod k \choose m \mod k} \]
真难。
简单来讲,题目要求满足\(\{x_i \mod m \in [1, m – 1]\}\)的\(k\)元组个数。我们可以先把\(x_i\)全部模上一个\(m\),然后令\(A = \sum_{i = 1}^k (x_i \mod m)\)(注意,\(A\)并没有被整体取模,只是各项余数之和),可知\(A \mod m = n \mod m\),且\(A\)的上限就是\(A = k(m – 1)\)(各项上限)。
我们做了这样一个设置之后,问题就可以转换为:对于每一个不同的\(A\),满足\(A \mod m = n \mod m\)且\(A = \sum_{i = 1}^k (x_i \mod m), \forall i, x_i \in [1, m – 1]\)的\(k\)元组方案数。首先,我们可以先枚举每一个\(A\)来缩小问题的范围,根据\(A\)所满足的条件,可以这样遍历\(i\)来获得每一个\(A\):
二项式反演的主要内容就是:
\[ f_n = \sum_{i = 0}^n (-1)^i {n \choose i} g_i \longleftrightarrow g_n = \sum_{i = 0}^n (-1)^i {n \choose i} f_i \]
这个反演的式子非常的优美:在这种形式下,它们是对称的。当然,亦可以写作:
\[ f_n = \sum_{i = 0}^n {n \choose i} g_i \longleftrightarrow g_n = \sum_{i = 0}^n (-1)^{n – i} {n \choose i} f_i \]
真的是玄妙重重。
我们先思考正常的暴力搜索:枚举每一次按下的颜色,然后检查继续更新。考虑用 IDA* 优化这个过程,首先估值函数就是剩下的颜色个数,因为至少需要更新这些颜色才有可能到达最终状态。然后注意控制 BFS 求连通块的个数的优化就行了。很好的一道题。
有一个“显然”的定理:如果满足\(n\&k==k\),那么\(C^k_n\)为奇数。具体感性证明:litble 的证明。所以,直接上代码。
// P3773.cpp #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int MAX_N = 233393, mod = 1000000007; int n, arr[MAX_N], bucket[MAX_N], f[MAX_N], ans; int getMod(int num) { return num >= mod ? num - mod : num; } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &arr[i]), bucket[arr[i]] = i; for (int i = n; i >= 1; i--) { f[i] = 1; for (int j = (arr[i] & (arr[i] - 1)); j; j = arr[i] & (j - 1)) if (bucket[j] > i) f[i] = getMod(f[i] + f[bucket[j]]); ans = getMod(ans + f[i]); } ans = (ans - n + mod) % mod; printf("%d", ans); return 0; }