[[容斥]] [[字符串]]
前情提要 洛谷 P1316
标准题解实在是过于复杂，但是这道题可以用容斥来做。由于很少做容斥的题，题解看了一个下午才看懂，于是便准备讲一个更清楚的（新手向，如十分累赘，请大佬勿喷）。
题目分析 总的情况数已知，这道题实际上相当于求解每个字符串的不同子串的个数和。
那么这道题为什么能用容斥呢？我们考虑一个确定的字符串，长度为再次学习小学奥数访问 oi wiki 。
但是一个一个枚举子串是不可能的，我们发现，有一些子串性质是一样的。就比如一种出现方式在很多子串中都有贡献，那此时我们就有了新的思路，我们先枚举子串的长度
那么有多少种子串能像这样的格式重复出现呢？我们发现在文章中这样的子串可能会有重叠，于是我们使用一个并查集来维护子串中每一位是否应该与另一位上的字符相同，相同的就连在一起了，统计一个子串中能自由选择的有
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 #include <bits/stdc++.h> #define mod 1000000007ll using namespace std;using ll = long long ;int n;ll m; ll qp (ll x, ll y) { ll ans = 1 ; while (y) { if (y & 1 ) ans = ans * x % mod; y >>= 1 ; x = x * x % mod; } return ans; } ll ans; int fa[25 ];int getfa (int x) return x == fa[x] ? x : fa[x] = getfa (fa[x]); } void sol (int x) int a = (1 << (n - x + 1 )), b = (1 << x) - 1 ; for (int i = 1 ; i < a; ++i) { int c = 0 , tot = 0 ; for (int j = 0 ; j < x; ++j) fa[j] = j; for (int j = 0 ; j < n; ++j) { c = (c << 1 ) | ((i >> j) & 1 ); c &= b; if (!c) { ++tot; } else { int t = c - (c & -c), tmp = getfa (__builtin_ctz(c)); while (t) { fa[getfa (__builtin_ctz(t))] = tmp; t -= t & -t; } } } for (int j = 0 ; j < x; ++j) tot += (j == fa[j]); ll tmp = qp (m, tot); if (__builtin_parity(i)) { ans = (ans + tmp) % mod; } else { ans = (ans - tmp + mod) % mod; } } } int main () scanf ("%d%lld" , &n, &m); for (int i = 1 ; i <= n; ++i) sol (i); printf ("%lld" , ans * qp (qp (m, n), mod - 2 ) % mod); return 0 ; }
后记 这个容斥应该算是很经典的，非常适合像我一样的组合蒟蒻食用。
