这部分内容介绍了同余,莫比乌斯函数性质,线性筛,计数初步
其中计数问题只涉及一些普通的模型

计数问题模型初步

隔板模型

choose

组合数公式

  • (nm)=(nnm){n \choose m} = {n \choose n-m}

  • (nm)=(n1m)+(n1m1){n \choose m} = {n-1 \choose m} + {n-1 \choose m-1}

    • proof
      对于第nn 个元素,要么取,要么不取
      对应的在剩下的n1n-1 个元素中取m1m-1 个元素,或者是mm 个元素
  • (n0)+(n1)+(n2)++(nn)=2n{n \choose 0} + {n \choose 1} + {n \choose 2} + \cdots + {n \choose n} = 2^n

    • proof
      每一个元素都有2种可能,取或者不取,一共是2n2^n 种可能
      另外,最后的方案数可能有0,1,2,,n0, 1, 2, \cdots, n 个元素
      根据加法原理,一共有(n0)+(n1)+(n2)++(nn){n \choose 0} + {n \choose 1} + {n \choose 2} + \cdots + {n \choose n} 种不同的方案

UVA10943

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int maxn = 200 + 10;
const int mod = 1e6;
int c[maxn][maxn];
int n, k;

void prework() {
memset(c, 0, sizeof(c));
_for(i, 1, maxn) {
c[i][0] = c[i][i] = 1;
_for(j, 1, i) {
c[i][j] = (c[i-1][j-1] + c[i-1][j]) % mod;
}
}
}

int main() {
freopen("input.txt", "r", stdin);
prework();
while (scanf("%d%d", &n, &k) == 2 && n) {
// init
printf("%d\n", c[n+k-1][k-1]);
}
}

重复元素的全排列

fac

UVA11076
UVA11076

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

const int maxn = 15;
ll fac[maxn], num[maxn];

const ll one[13] = {0,1,11,111,1111,11111,111111,1111111,11111111,111111111,1111111111,11111111111,111111111111};
int n;

void init() {
//
memset(num, 0, sizeof(num));
}

void prework() {
memset(fac, 0, sizeof(fac));
fac[0] = 1, fac[1] = 1;

for(int i = 2; i <= 12; i++) fac[i] = fac[i-1] * 1ll * i;
}

int main() {
/*
string str;
for(int i = 1; i <= 12; i++) {
str.clear();
for(int t = 0; t < i; t++) str += '1';
cout << str << ',';
}
*/

freopen("input.txt", "r", stdin);
prework();

while (scanf("%d", &n) == 1 && n) {
init();

ll sum = 0;
_for(i, 0, n) {
int x;
scanf("%d", &x);
sum += x;
num[x]++;
}

ll ans = sum * fac[n-1];
_rep(i, 0, 9) ans /= fac[num[i]];
ans *= one[n];
printf("%lld\n", ans);
}
}

同余问题

同余类与最小剩余系

mod1
mod2
mod3
mod4
mod5

Euler-Fermat定理求解一次同余式
(a,m)=1(a,m)=1,那么一次同余式

axb(modm)ax \equiv b (\bmod m)

的唯一解由

xbaϕ(m)1(modm)x \equiv ba^{\phi(m)-1} (\bmod m)

给出

HDU2462
xx88 连在一起组成的正整数可以写成

8×10x198 \times \frac{10^x - 1}{9}

求最小的xx,满足9L8(10x1)9L \mid 8(10^x - 1)
let d=gcd(L,8)\textbf{let} \ d = \textbf{gcd}(L, 8)

9Ld(10x1)10x1(mod9Ld)\Longrightarrow \frac{9L}{d} \mid (10^x -1) \Rightarrow 10^x \equiv 1 (\bmod \frac{9L}{d})

引理,若(a,n)=1(a, n)=1,则满足ax1(modn)a^x \equiv 1 (\bmod n) 的最小正整数x0x_0,满足
x0ϕ(n)x_0 \mid \phi(n)
proof
反证法,不妨设ϕ(n)=qx0+r(0<r<x0)\phi(n) = qx_0 + r \quad (0 < r < x_0)
ax01(modn)aqx01(modn)a^{x_0} \equiv 1 (\bmod n) \Rightarrow a^{qx_0} \equiv 1(\bmod n)
根据欧拉定理,有aϕ(n)1(modn)a^{\phi(n)} \equiv 1(\bmod n)

{aqx01(modn)aϕ(n)1(modn)ar1(modn)r<x0\begin{cases} a^{qx_0} \equiv 1 (\bmod n) \\ a^{\phi(n)} \equiv 1 (\bmod n) \end{cases} \Rightarrow a^{r} \equiv 1(\bmod n) \Rightarrow r < x_0

矛盾

先重温一下快速幂
ksc

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
ll L;
const ll inf = 1e18;

ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}

ll ksc(ll a, ll b, ll mod) {
ll ans = 0;
for(; b; b >>= 1) {
if (b & 1) ans = (ans + a) % mod;
a = (a * 2) % mod;
}
return ans;
}

ll ksm(ll a, ll b, ll mod) {
ll ans = 1 % mod;
a %= mod;

for(; b; b >>= 1) {
if (b & 1) ans = ksc(ans, a, mod);
a = ksc(a, a, mod);
}

return ans;
}


ll phi(ll n) {
ll ans = n;
for(ll i = 2; i * i <= n; i++) {
if (n % i == 0) {
ans = ans / i * (i - 1);
while (n % i == 0) n /= i;
}
}

if (n > 1) ans = ans / n * (n - 1);
return ans;
}

ll solve() {
ll d = gcd(L, 8ll);
ll mod = 9 * L / d;

if (gcd(mod, 10ll) != 1) return 0;

ll N = phi(mod);
ll res = inf;

for(ll i = 1; i <= sqrt(N); i++) {
if (N % i) continue;
if (ksm(10ll, i, mod) == 1) chmin(res, i);
if (ksm(10ll, N/i, mod) == 1) chmin(res, N/i);
}

return res == inf ? 0 : res;
}

int main() {
freopen("input.txt", "r", stdin);
int kase = 0;
while (cin >> L && L) {
printf("Case %d: ", ++kase);

ll res = solve();
printf("%lld\n", res);
}
}

扩展Euclid算法

Bezout定理
对于任意整数a,ba, b,存在一对整数x,yx,y,满足ax+by=gcd(a,b)ax+by = \textbf{gcd}(a, b)

根据数学归纳法做递归
i) b=0\textbf{i)} \ b = 0,此时存在一对解x=1,y=0x = 1, y = 0
a1+00=gcd(a,0)=a\quad a\cdot 1 + 0 \cdot 0=\textbf{gcd}(a,0)=a
ii) b>0\textbf{ii)} \ b > 0

{ax+by=gcd(a,b)gcd(a,b)=gcd(b,amodb)bx+(amodb)y=gcd(b,amodb)\begin{cases} ax+by = \textbf{gcd}(a, b) && \textbf{gcd}(a, b) = \textbf{gcd}(b, a \bmod b) \\ bx + (a \bmod b) y = \textbf{gcd}(b, a \bmod b) \end{cases}

bx+(amodb)y=bx+(aa/bb)y=ay+b(xa/by)bx+(a \bmod b)y = bx+(a- \lfloor a/b \rfloor b) y = ay + b(x - \lfloor a/b\rfloor y)

xyx' \leftarrow y
yxa/byy' \leftarrow x - \lfloor a/b\rfloor y
ax+by=gcd(a,b)ax'+by' = \textbf{gcd}(a, b)

1
2
3
4
5
6
7
8
9
10
int exgcd(int a, int b, int& x, int& y) {
if (b == 0) {
x = 1, y = 0;
return a;
}

int d = exgcd(b, a % b, x, y);
int z = x; x = y; y = z - (a/b) * y;
return d;
}

对于一般方程ax+by=cax+by = c,可以先求出最大公约数(a,b)=d(a, b) = d
有解当且仅当dcd \mid c

调用

1
exgcd(a, b, x0, y0)

求出方程的一组特解x0,y0x_0, y_0,原方程的一组特解就是

cdx0,cdy0\frac{c}{d} \cdot x_0, \quad \frac{c}{d} \cdot y_0

通解是

x=cdx0+kbd,y=cdy0kad(kZ)x = \frac{c}{d} x_0 + k \frac{b}{d}, \quad y = \frac{c}{d} y_0 - k \frac{a}{d} \quad (k \in \mathbb{Z})

乘法逆元

a1bax(modm)a \cdot \frac{1}{b} \equiv a \cdot x (\bmod m)

其中ba, gcd(b,m)=1b \mid a, \ \textbf{gcd}(b,m) = 1

xxbbmodm\bmod m 乘法逆元
记为b1(modm)b^{-1} (\bmod m)

a/bab1a/bbb1(modm)a/b \equiv a \cdot b^{-1} \equiv a/b \cdot b \cdot b^{-1} (\bmod m)
bb11(modm)\Rightarrow b \cdot b^{-1} \equiv 1 (\bmod m)

如果mm 是素数,并且b<pb < p,有bp11(modp)bbp21(modm)b^{p-1} \equiv 1 (\bmod p) \Leftrightarrow b \cdot b^{p-2} \equiv 1(\bmod m)
pp 为质数的时候,bp2b^{p-2} 即为bb 的乘法逆元

如果(b,m)=1(b,m)=1,乘法逆元可以通过求解线性同余方程得到
bx1(modm)b \cdot x \equiv 1 (\bmod m)

乘法逆元在计算中的应用

abaamodp, bbmodp\frac{a}{b} \Longrightarrow {a \leftarrow a \bmod p}, \ {b \leftarrow b \bmod p}

ab1modpa \cdot b^{-1} \bmod p 作为最终结果
当然前提是必须保证(b,p)=1(b,p)=1也就是说bb 不是pp 的倍数

POJ1845

Si=piBci+11pi1S_i = \frac{p_i^{B \cdot c_i + 1} - 1}{p_i - 1}

AB=i[1,n]Si,M=9901A^B = \prod_{i \in [1,n]} S_i, M = 9901

algorithm\textbf{algorithm}

  • (piBci+11)modM,(pi1)modM(p_i^{B \cdot c_i + 1} - 1 ) \bmod M, \quad (p_i - 1) \bmod M

  • 如果pi1p_i - 1 不是MM 的倍数,那么这个数的乘法逆元
    inv=(pi1)M2inv = (p_i - 1)^{M-2},用×inv\times inv 代替除法

    如果pi1=kMp_i - 1 = kM,那么pi1(modM)p_i \equiv 1 (\bmod M)
    1+pi+pi2++piBci1+1+Bci+1(modM)1 + p_i + p_i^{2} + \cdots + p_i^{B\cdot c_i} \equiv 1 + 1+ \cdots \equiv B \cdot c_i + 1(\bmod M)

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

const int mod = 9901;
ll a, b;

class A {
public:
int p, c;
A() = default;
A(int p) : p(p) {
c = 0;
}
};

vector<A> P;

void divide(ll n) {
P.clear();
for(ll i = 2; i * i <= n; i++) {
if (n % i == 0) {
P.push_back(A(i));
while (n % i == 0) n /= i, P.back().c++;
}
}
if (n > 1) P.push_back(n), P.back().c = 1;
}

void solve() {
ll ans = 1;
divide(a);

_for(i, 0, P.size()) {
if ((P[i].p - 1) % mod == 0) {
ans = (b * P[i].c + 1) % mod * ans % mod;
continue;
}

ll x = ksm(P[i].p, b*P[i].c+1, mod);
x = (x - 1 + mod) % mod;

ll y = P[i].p - 1;
y = ksm(y, mod - 2, mod);
ans = ans * x % mod * y % mod;
}

cout << ans << endl;
}

void init() {
//
}

int main() {
freopen("input.txt", "r", stdin);
cin >> a >> b;
init();

// then solve
solve();
}