MlKE带飞了。
该死的windows更新，把笔记带走了
可重集的排列
错排
对于长度为$n$的排列，问满足$\forall a_i \neq i$的排列个数。
前置知识：容斥
简单介绍一下，容斥满足：
- 并集形式：$|A_1 \cup A_2 \cup …A_n| = \sum_{1 \le i \le n}|A_i|-\sum_{1 \le i \le j \le n}|A_i\cap A_j| +….(-1)^{n+1}|A_1 \cap A_2 \cap … A_n$
- 交集形式：$| C_S^{\cap_{i=1}^n A_i}| = |C_S^{\cup_{i=1}^n A_i}| = |S| - |\cup_{i= 1}^n A_i| = |S| - \sum|A_i| + \sum |A_i \cap A_j| - …+(-1) ^ n| \cap_{i = 1}^n A_i|$
理解
首先我们定义$n$个集合，每个集合$A_i$代表满足$a_i=i$的合法方案那么我们的最终方案就是：$C_S^{\cap_{i=1}^n A_i}$。
对此我们直接用第二个式子暴力展开然后我们惊讶的发现：$ans = |n!| - |C_n^1 (n-1)!| + |C_n^2 (n-2)!| …+(-1)^n|C_n^n1!|$。
这个东西我们完全可以搞。
多重集的组合数
$n$种数，从中选$m$个数，问不同的方案数。
先记结论：$C_{n+m-1}^m$。
这个东西比上面那个东西好证。
首先我们设选出来的数的种类满足：$1 \le a_1 \le a2 … \le a_m \le n$。
凭着信息学竞赛的直觉（考场上孤注一掷的暴力来看），这东西根本没法搞。
为什么没法搞呢？因为这些数可以取等，组合数搞不了，再考虑构造。
对于所有的数，我们加上自身的下标$-1$，令其为$b_i$。
然后就满足：$1 \le b_1 \le b_2…\le b_m \le n + m - 1$。
这就是组合数板子了，套公式就解决了。
卡特兰数
斐波拉契数列的循环节
性质：在模$p$意义下斐波拉契的循环节不超过$6p$。
如何求出循环节
下面给出两种做法：
随机法
考虑在$10^{10}$左右的级别随机出一个数，将其的值和下一个值与第一个值和第二个值进行比对，如果相同，这说明我们找到一个可行的循环节，将其分解质因数，每次检验其因数是否可行即可。
考虑这样最多会随机多少次，根据生日悖论，期望随机的个数在$\sqrt {6p}$左右。
贴下代码：
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| #include<bits/stdc++.h>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
res = 0; bool flag = 0;
char c = getchar();
while('0' > c || c > '9') { if(c == '-') flag = 1; c = getchar();}
while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
if(flag) res = -res;
}
template <class T, class ...Arg>
inline void read(T &res, Arg &...com){ read(res), read(com...);}
template <class T>
void out(T res)
{
if(res > 9) out(res / 10);
putchar(res % 10 + '0');
}
template <class T>
inline void write(T res)
{
if(res < 0) putchar('-'), res = -res;
out(res), putchar('\n');
}
const int N = 3e7 + 5;
int mod;
struct Node{
LL a[3][3];
Node operator* (Node b)
{
Node c;
memset(c.a, 0, sizeof(c.a));
for(int i = 1;i <= 2;i ++)
for(int j = 1;j <= 2;j ++)
for(int k = 1;k <= 2;k ++)
c.a[i][j] = (c.a[i][j] + 1ll * a[i][k] * b.a[k][j] % mod) % mod;
return c;
}
}o;
LL n, len, p = 1e11, cnt = 0;
mt19937_64 rnd(114514);
std::map<std::pair<int, int>, LL> mp;
inline Node qpow(Node x, LL k)
{
Node res = x;
k --;
while(k)
{
if(k & 1) res = res * x;
x = x * x;
k >>= 1;
}
return res;
}
inline bool check()
{
LL ed = rnd() % p + 10;
o.a[1][1] = 1, o.a[1][2] = 1;
o.a[2][1] = 1, o.a[2][2] = 0;
o = qpow(o, ed - 2);
LL x = (o.a[1][1] + o.a[2][1]) % mod, y = o.a[1][1] % mod;
if (mp[{x, y}] && mp[{x, y}] != ed) return len = std::abs(mp[{x, y}] - ed), true;
mp[{x, y}] = ed;
return false;
}
LL minn;
inline LL query(LL limit)
{
if (limit <= 2) return false;
o.a[1][1] = 1, o.a[1][2] = 1;
o.a[2][1] = 1, o.a[2][2] = 0;
o = qpow(o, limit - 2);
LL x = (o.a[1][1] + o.a[2][1]) % mod, y = o.a[1][1] % mod;
return x;
}
char c[N];
int main()
{
scanf("%s", c + 1), read(mod);
if(mod == 1) return puts("0"), 0;
while(!check());
n = strlen(c + 1);
if(len == 0) return puts("0"), 0;
for(int i = 1;i <= n;i ++)
minn = (minn * 10 + c[i] - '0') % len;
if(minn == 0) return puts("0"), 0;
if(minn <= 2) return puts("1"), 0;
write(query(minn));
return 0;
}
|
BSGS
考虑怎么用$BSGS$计算，一般来说题目中的模数都是质数，我们联想到上一个算法中矩阵快速幂，决定在这上面下文章，设转移矩阵为$A$，则我们的式子为：
$$
A^x \equiv I \pmod{p}
$$
$I$是单位矩阵，当$A$在模$p$意义下有逆矩阵时，我们就可以用$BSGS$愉快的求解了。
其他的一些相关性质
根据网上一些巨佬的博客：
设其循环节长度为$len$
若$5$是模$p$意义下的二次剩余：$len | p-1$
若$5$不是模$p$意义下的二次剩余：$len|2p+2$