## 密码
#枚举 #字典树
首先密码中的每一位要求属于该位的尝试列表，否则永远试不出正确代码。然后对于 $k$ 个已经试过的密码，先给它们去重，然后判断是否每一位均属于尝试列表，如果是就对答案减一即可。时间复杂度 $\mathcal O(nk)$。
```cpp
#include <fstream>
#include <unordered_set>
#include <string>
using namespace std;
using LL = long long;
const LL kMaxN = 1e4 + 5;
ifstream cin("password.in");
ofstream cout("password.out");
LL n, k, sum = 1;
string s[kMaxN], a, t;
unordered_set<string> st;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k >> a;
a = " " + a;
for (LL i = 1, x; i <= n; i++) {
cin >> x >> s[i];
sum *= x;
if (s[i].find(a[i]) == string::npos) {
cout << "-1\n";
return 0;
}
}
for (LL i = 1; i <= k; i++) {
cin >> t;
t = " " + t;
if (st.count(t)) {
continue;
}
st.insert(t);
bool b = 1;
for (LL j = 1; j <= n && b; j++) {
b &= s[j].find(t[j]) != string::npos;
}
if (b) {
sum--;
}
}
cout << sum << '\n';
return 0;
}
```
## 矩阵游戏
#等比数列求和 #快速幂 #乘法逆元
令 $f(x)=ax+b,g(x)=cx+d$，若每一行的第一个元素为 $x$（第一行为 $1$）那么每一行的最后一个元素等于 $f^{m-1}(x)$（迭代 $m-1$ 次），而下一行的第一个元素为 $g(f^{m-1}(x))$。对于同一个一次函数的嵌套 $f^n(x)$，暴力拆开得到等于
$
a^n+b\sum_{i=0}^{n-1}a^i
$
通过等比数列求和公式计算。算出 ${} g(f^{m-1}(x)) {}$ 的系数之后再对其进行 $n-1$ 次迭代，得到第 $n$ 行的第一个元素，然后再带入 $f(x)$ 进行 $m-1$ 次迭代即可。
注意本题 $\log(n/m)$ 达到 $10^6$，所以直接跑十进制的快速幂即可。等比数列求和注意系数为一的特殊情况。
```cpp
#include <fstream>
#include <utility>
#include <string>
using namespace std;
using LL = long long;
const LL kMod = 1e9 + 7;
ifstream cin("matrix.in");
ofstream cout("matrix.out");
LL a, b, c, d;
string n, m;
LL pow(LL a, LL b) {
LL res = 1;
for (; b; b /= 2) {
b % 2 && (res = res * a % kMod);
a = a * a % kMod;
}
return res;
}
LL pow(LL a, string n) {
LL b = a, res = 1;
for (; n.size(); n.pop_back()) {
if (n.back() != '0') {
res = res * pow(b, n.back() - '0') % kMod;
}
b = pow(b, 10);
}
return res;
}
LL num(const string &n) {
LL res = 0;
for (char c : n) {
res = (res * 10 + c - '0') % kMod;
}
return res;
}
pair<LL, LL> calc(const string &n, LL a, LL b) {
if (a == 1) {
return {1, num(n) * b % kMod};
}
return {pow(a, n), (pow(a, n) - 1 + kMod) % kMod * pow(a - 1, kMod - 2) % kMod * b % kMod};
}
void sub(string &s) {
s.back()--;
for (LL i = s.size() - 1; i >= 0; i--) {
if (s[i] < '0') {
s[i] += 10, s[i - 1]--;
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> a >> b >> c >> d;
sub(n), sub(m);
auto p1 = calc(m, a, b);
auto p2 = calc(n, p1.first * c % kMod, (p1.second * c % kMod + d) % kMod);
cout << (p1.first * (p2.first + p2.second) % kMod + p1.second) % kMod << '\n';
return 0;
}
```
## 兴趣排列
#数学
首先可以简单地写出 $\mathcal O(n^2)$ 的 DP。
先判无解，对于 $a_1\ne 0$ 是无解的，$a_i<a_{i-1}$ 也是，其次有 $a_i<n$。
设 $[l,r]$ 表示前 $i$ 个元素的值域区间，那么有 $r-l=i$。如果 $a_i=a_{i-1}$，那么对于任意 $[l,r]$ 区间都不变，只需要在区间内选择一个没选过的即可；否则对于 $[l,r]$ 均可以像两边的任意一边拓展。
所以只需要先让 $ans\gets 1$，然后对于 $i\ge 2$，有
$
ans\gets\begin{cases}
ans\times [(a_i+1)-(i-1)] & \text{if}~a_i=a_{i-1} \\
ans\times 2 & \text{if}~a_i>a_{i-1}
\end{cases}
$
时间复杂度 $\mathcal O(n)$。
```cpp
#include <fstream>
using namespace std;
using LL = long long;
const LL kMaxN = 2e6 + 5, kMod = 1e9 + 7;
ifstream cin("perm.in");
ofstream cout("perm.out");
LL a[kMaxN], dp[kMaxN], f[kMaxN], t, n;
int main() {
cin.tie(0)->sync_with_stdio(0);
for (cin >> t; t; t--) {
cin >> n;
for (LL i = 1; i <= n; i++) {
cin >> a[i];
}
if (a[1]) {
cout << "0\n";
continue;
}
bool b = 1;
for (LL i = 2; i <= n && b; i++) {
b &= a[i] >= a[i - 1];
b &= a[i] <= n - 1;
}
if (!b) {
cout << "0\n";
continue;
}
LL ans = 1;
for (LL i = 2; i <= n; i++) {
if (a[i] == a[i - 1]) {
ans = ((a[i] + 1) - (i - 1) + kMod) % kMod * ans % kMod;
} else {
ans = ans * 2 % kMod;
}
}
cout << ans << '\n';
}
return 0;
}
```
## 交换礼物
#离散化 #序列dp
首先考虑对于一个已有的序列，如何计算最多能让多少位选手开心，等价于最小化不开心的选手数量。不难发现若其出现次数最多的数的出现次数 $x$ 小于等于 $n/2$ 时，每个选手按照手上礼物编号排一排再递给往后的 $x$ 个人，那么不会有人礼物编号重复；否则若其它类型的礼物数量为 $y=n-x$，那么会有 $x-y$ 个人不开心。
所以我们并不需要构造最终的序列，只需要搞清楚哪种礼物有多少人拥有即可。这是典型的计数问题。设 $dp_i$ 表示第 $i$ 个序列需要计入到最终序列 $dp_i$ 次，那么首先 $dp_n$ 为 $1$。从前往后按照下标拓扑序遍历，然后对于所有由两个序列拼起来的序列，让 $dp_x\gets dp_x+dp_i,dp_y\gets dp_y+dp_i$。最后统计到 map（也可以像我一样离散化），求出众数和总数即可。
时间复杂度 $\mathcal O(n+k\log_2 k)$。
```cpp
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
using LL = long long;
const LL kMaxN = 1e6 + 5;
ifstream cin("gifts.in");
ofstream cout("gifts.out");
struct Node {
LL o, x, y;
vector<LL> v;
} a[kMaxN];
LL dp[kMaxN], f[kMaxN], val[kMaxN], t, n, m;
int main() {
cin.tie(0)->sync_with_stdio(0);
for (cin >> t; t; t--) {
cin >> n;
m = 0;
for (LL i = 1, k; i <= n; i++) {
cin >> a[i].o;
if (a[i].o == 1) {
cin >> k;
a[i].v.resize(k);
for (LL &j : a[i].v) {
cin >> j;
val[++m] = j;
}
} else {
cin >> a[i].x >> a[i].y;
a[i].v.clear();
}
}
sort(val + 1, val + m + 1);
m = unique(val + 1, val + m + 1) - val - 1;
fill(f + 1, f + m + 1, 0);
fill(dp + 1, dp + n + 1, 0);
dp[n] = 1;
for (LL i = n; i >= 1; i--) {
if (a[i].o == 2) {
dp[a[i].x] += dp[i];
dp[a[i].y] += dp[i];
}
}
for (LL i = 1; i <= n; i++) {
if (a[i].o == 1) {
for (LL j : a[i].v) {
f[lower_bound(val + 1, val + m + 1, j) - val] += dp[i];
}
}
}
LL sum = 0, mx = 0;
for (LL i = 1; i <= m; i++) {
sum += f[i];
mx = max(mx, f[i]);
}
LL other = sum - mx;
if (mx <= other) {
cout << sum << '\n';
} else {
cout << sum - (mx - other) << '\n';
}
}
return 0;
}
```