32 分钟 读完 (大约 4748 个字)

数学

这是课件

课件

组合数学基础

常用公式

$\binom{n}{m} = \frac{n!}{m!(n-m)!}$

$\binom{n}{m} = \binom{n}{n-m}$

$\binom{n}{m} = \binom{n - 1}{m} + \binom{n - 1}{m - 1}$

$\binom{n}{m + 1} = \binom{n}{m} × \frac{n - m}{m + 1}$

二项式定理

$(a + b)^n = \sum_{i=0}^n\binom{n}{i}×a^i×b^{n - i}$

可重组合

$\binom{n + m - 1}{m}$

第$i$种颜色的球有$a_i$个,求排列的方案数

$\frac{(\sum a_i)!}{\prod a_i!}$

从$(0,0)$走到$(n,m)$,不碰到直线$y=x+b$的方案数

$\binom{n + m}{n} - \binom{n + m}{n - b}$

斯特林数

  1. 第一类斯特林数:$n$个人坐$m$张圆桌的方案数 $[m^n] = [{m-1}^{n-1}] + (n - 1)×[_m^{n-1}]$

  2. 第二类斯特林数:$n$个球分成$m$个集合的方案数 ${^n_m} = {_{m-1}^{n-1}} + m×{^{n-1}_m}$

容斥原理
  • +-+-+-+-+-+-+-+-……
应用

  1. zsy和yyb出现至少一人的概率(或方案数等)=zsy出现的概率+yyb出现的概率-两人同时出现的概率。

  2. 更常见的应用:

    zsy和yyb都不出现的概率=1-至少出现一人的概率,然后再容斥算后面那个东西。

  3. 更高级的应用:

    n个zsy全部咕咕的概率=1-至少咕一个的概率+至少咕两个的概率-……=1-至少咕奇数
    个的概率+至少咕偶数个的概率。

错排问题

给定$n$,问有多少个$1$~$n$的排列$p$满足不存在$i$满足$p_i=i$

Ans = n! -（至少有一组pi=i的方案数）+（至少有两组pi=i的方案数）- ……想要好看点就是这样：
$$
Ans = \sum_{i=0}^n(-1)^i×\binom{n}{i}×(n-i)!
$$
即钦定$i$个位置满足$p_i=i$，剩下的随便放。

走路问题

从$(1,1)$走到$(n,m)$,其中有$k$个点$(x,y)$是不能走的,问有多少种方案。

设$f[i]$表示走到第$i$个特殊点（包括$(0,0)$,$(n,m)$以及$k$个障碍点）的方案数，则：
$$
f[i] = \sum j到i的方案数 × (-f[j])
$$
因为这个转移默认了$j$是障碍点（所以要变号），因此需要设$f[1]$（即$(0,0)$对应方案数）$=-1$。

初等数论

扩展欧几里得

用来求形如$ax+by=gcd(a,b)$的方程的整数解。据说用这种方法求出的解满足$|x|+|y|$最小。

1
2
3
4
inline void exgcd(long long a, long long b, long long &gcd, long long &x, long long &y)
{
	!b ? gcd = a, x = 1, y = 0 : (exgcd(b, a % b, gcd, y, x), y -= x * (a / b));
}
欧拉定理

$a^{φ(n)}\equiv1(mod\;n)$

其中$φ(n)$为欧拉函数,即小于等于$n$,且与$n$互质的数的个数, $a,n$互质

$φ(n)=n×\prod(1-\frac{1}{a_i})$

其中$a_i$是$n$的质因子。可以发现,对于质数$n$, $φ(n)=n-1$。

降幂

对于指数很大的情况,可以根据欧拉定理降幂。

如果$n,a$互质:$a^b\equiv a^{b\%φ(n)}(mod\;n)$

否则，根据扩展欧拉定理

  • 当$b < φ(n)$时

    $a^b\equiv a^b(mod\;n)$

  • 当$b >= φ(n)$时

    $a^b\equiv a^{b\%φ(n)+φ(n)}(mod\;n)$

逆元

对于$B\equiv\frac{1}{A}(mod\;p)$称$B$为$A$在模$p$意义下的乘法逆元。

求乘法逆元有以下几种方法:

  1. 根据欧拉定理,快速幂求出:$B=A^{p-2}\%p$

  2. 解方程$px+Ay=1$,则$Ay=1-px,y\equiv\frac{1}{A}(mod\;p)$

  3. 递推求逆元:

    $inv[i] = p-([\frac{p}{i}]×inv[p\;mod\;i])\;mod\;p$

筛法求质数

复杂度$O(n)$的筛法:

1
2
3
4
5
6
7
8
9
for(RG int i = 2; i <= n; i++)
{
    if(!not_prime[i]) prime[++cnt] = i;
    for(RG int j = 1; j <= cnt && i * prime[j] <= n; j++)
    {
        not_prime[i * prime[j]] = 1;
        if(!(i % prime[j])) break;
    }
}
BSGS

北上广深算法

用来求形如$a^x\equiv b(mod\;p)$的方程的解。

所以这东西怎么做呢？

取$k=\lceil\sqrt{p}\rceil$，令$x=ky+z$，则
$$
a^{ky} \times a^z \equiv b (mod\;p),\;a^{ky} \equiv \frac{b}{a^z} (mod\;p)
$$
预处理出所有的$\frac{b}{a^z}$并哈希存储，枚举$y$后判断是否有满足条件的即可。

数列

几个公式
  1. 平方和公式$\sum_{i=1}^ni^2=\frac{n(n+1)(2n+1)}{6}$
  2. 立方和公式$\sum_{i=1}^ni^3=(\frac{n(n+1)}{2})^2$
  3. 等比数列求和公式$S_n=\frac{a_1(1-p^n)}{1-p}$

矩阵与方程

矩阵乘法

矩阵乘法满足结合律,所以可以用类似数的快速幂的方式实现矩阵快速幂。

矩阵快速幂有什么用呢?我们考虑一个$1×n$的矩阵$a$和一个$n×n$的矩阵$b$相乘。

可以发现,对于得出的$1×n$的矩阵的第$i$个数$c_i$,满足:
$$
c_i=\sum b_{j,i}×a_j
$$

所以,我们可以用矩阵乘法来表示线性递推

高斯消元

其实这里介绍的是高斯-约旦消元法。相对于传统的高斯消元,这种方法的精度更好, 代码更简单。(据说常数比较大,不过实测还是跑得蛮快的。。。)

大致思路如下对于每一步:

  1. 选择一个尚未被选过的未知数作为主元,选择一个包含这个主元的方程

  2. 将这个方程主元的系数化为1

  3. 通过加减消元,消掉其它方程中的这个未知数。

如果用一个$n×(n+1)$的矩阵表示方程组,消到最后,方程组会变成这样:
$$
\left[
\begin{matrix}
1 & 0 & … & 0 & 0 & c_1 \
0 & 1 & … & 0 & 0 & c_2 \
… & … & … & … & … & … \
0 & 0 & … & 1 & 0 & c_{n-1} \
0 & 0 & … & 0 & 1 & c_n
\end{matrix}
\right]
$$

同余类最短路

当数论与图论相结合,又会发生什么有意思的事呢?

不知道

概率与期望

期望的线性性

期望的线性性最大的好处就是,它不要求那被分别计算的若干种期望是不相关的。

所以,只要是和乘法没什么关系的期望题,我们都应该首先考虑期望的线性性。

例题

组合数学基础

洛谷P2822 组合数问题

可以通过组合数的递推公式快速算出$i,j<=2000$的组合数，从而算出其中$\%k=0$的有多少。可以通过二维前缀和将询问优化至$O(1)$。

需要注意的是，组合数$C(n,m)$随着n的增大是呈指数级增大的，所以需要边计算，边取模，以免爆精度。

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
#include<bits/stdc++.h>
#define RG register
using namespace std;

inline int read()
{
	int data=0,w=1;
	char ch=0;
	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
	if(ch=='-') w=-1,ch=getchar();
	while(ch>='0'&&ch<='9') data=data*10+ch-'0',ch=getchar();
	return data*w;
}

int c[2010][2010], b[2010][2010];
int n,m,t,k;

int main()
{
	t=read(); k=read();
	for(RG int i=0;i<=2009;i++)
	{
		c[i][0]=1;
		b[i][0]=bool(c[i][0])^1;
		for(RG int j=1;j<=i;j++)
		{
			c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
			b[i][j]=bool(c[i][j])^1;
		}
	}
	for(RG int i=0;i<=2009;i++)
		for(RG int j=1;j<=2009;j++)
			b[i][j]+=b[i][j-1];
	for(RG int i=1;i<=2009;i++)
		for(RG int j=0;j<=2009;j++)
			b[i][j]+=b[i-1][j];
	while(t--)
	{
		n=read(); m=read();
		printf("%d\n",b[n][m]);
	}
	return 0;
}
洛谷P4609 [FJOI2016]建筑师

高度为n的zsy无论如何都能从左右两侧看到。剩下的部分，从左边看到的是前缀max，从右侧看到的是后缀max。大概像这样：

对于被框住的$A+B-1$个部分，只有第一个能作为前、后缀$max$被看到。可以认为是把数分成$A+B-1$个圆排列，其中有一个仅包含$n$。剩下的$A+B-2$个，先决定放在$n$的左边还是右边。然后，将每个圆排列的将最大值钦定为所在方向(左或右)上的第一个，并以此为关键字将圆排列排序后放置。

所以对于一组询问，答案就是：
$$
[_{A + B - 2}^{n-1}] \times \binom{A + B - 2}{A - 1}
$$

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
#include<bits/stdc++.h>
#define RG register
#define clear(x, y) memset(x, y, sizeof(x));
using namespace std;

inline int read()
{
	int data=0, w=1;
	char ch=getchar();
	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
	if(ch=='-') w=-1, ch=getchar();
	while(ch>='0'&&ch<='9') data=data*10+(ch^48), ch=getchar();
	return data*w;
}

const int mod(1e9 + 7), maxn(50010), maxk(210), K(201);
int T, n, A, B, C[maxk][maxk], S[maxn][maxk];

inline void Init()
{
	C[0][0] = 1;
	for(RG int i = 1; i <= K; i++)
	{
		C[i][0] = C[i][i] = 1;
		for(RG int j = 1; j < i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
	}
	for(RG int i = 0; i <= K; i++) S[i][i] = 1;
	for(RG int i = 2; i <= maxn - 10; i++)
		for(RG int j = 1; j < i && j <= K; j++)
			S[i][j] = (1ll * (i - 1) * S[i - 1][j] % mod + S[i - 1][j - 1]) % mod;
}

int main()
{
	T = read(); Init();
	while(T--)
	{
		n = read(); A = read(); B = read();
		if(A + B > n + 1) { puts("0"); continue; }
		printf("%lld\n", 1ll * C[A + B - 2][A - 1] * S[n - 1][A + B - 2] % mod);
	}
	return 0;
}
洛谷P1450 [HAOI2008]硬币购物

预处理$f[i]$表示在不限制硬币数量的情况下购买价值为i的物品的方案数。跑一个完全背包就好了。

对于硬币个数的限制，考虑容斥：钦定若干种硬币使用$d_i+1$次，也就是钦定它超过限制。设被钦定的总费用为$x$，方案数就是$f[s-x]$。容斥一下，偶加奇减就可以了。

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
#include<bits/stdc++.h>
#define RG register
#define clear(x, y) memset(x, y, sizeof(x));
using namespace std;

inline int read()
{
	int data = 0, w = 1;
	char ch = getchar();
	while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
	if(ch == '-') w = -1, ch = getchar();
	while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
	return data*w;
}

const int maxn(100010);
long long f[maxn], c[4], d[4], s;
inline long long Cost(int i) { return c[i] * (d[i] + 1); }
int T;

int main()
{
	for(RG int i = 0; i < 4; i++) c[i] = read();
	f[0] = 1;
	for(RG int i = 0; i < 4; i++)
		for(RG int j = c[i]; j <= maxn - 10; j++)
			f[j] += f[j - c[i]];
	T = read();
	while(T--)
	{
		for(RG int i = 0; i < 4; i++) d[i] = read();
		s = read();
		long long ans = 0;
		for(RG int i = 0; i < 16; i++)
		{
			long long tot = 0; int pop_cnt = 0;
			for(RG int j = 0; j < 4; j++)
				if(i & (1 << j)) tot += Cost(j), ++pop_cnt;
			if(s >= tot)
				if(pop_cnt & 1) ans -= f[s - tot];
				else ans += f[s - tot];
		}
		printf("%lld\n", ans);
	}
	return 0;
}

中国剩余定理

CJOJ1272 韩信点兵

中国剩余定理板子题。

设$M=\prod P_i,\;m_i=\frac{M}{p_i},\;t_im_i\equiv1\;(mod\;P_i)$

可以发现$a_it_im_i\equiv0(mod\;m_i),\;a_it_im_i\equiv a_i(mod\;P_i)$

所以答案就是$\sum a_it_im_i\;mod\;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
#include<bits/stdc++.h>
#define RG register
#define clear(x, y) memset(x, y, sizeof(x));
using namespace std;

inline __int128 read()
{
	__int128 data = 0, w = 1;
	char ch = getchar();
	while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
	if(ch == '-') w = -1, ch = getchar();
	while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
	return data*w;
}

const int maxn(20);
__int128 p[maxn], a[maxn], M, m[maxn], ans, n, k;

inline void exgcd(__int128 a, __int128 b, __int128 &gcd, __int128 &x, __int128 &y)
{
	!b ? (gcd = a, x = 1, y = 0) : (exgcd(b, a % b, gcd, y, x), y -= x * (a / b));
}

inline void CRT()
{
	static __int128 x, y, g;
	for(RG int i = 1; i <= k; i++)
	{
		m[i] = M / p[i];
		exgcd(m[i], p[i], g, x, y);
		if(a[i] % g) { ans = -1; return; }
		x *= a[i] / g; ans = (ans + (x + M) % M * m[i] % M) % M;
	}
	if(n < ans) ans = -1;
	else ans = (n - ans) % M;
}

int main()
{
	n = read(); k = read(); M = 1;
	for(RG int i = 1; i <= k; i++)
		M *= (p[i] = read()), a[i] = read();
	CRT(); printf("%lld\n", ans);
	return 0;
}

BSGS

洛谷P2485 [SDOI2011]计算器
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
93
94
#include<bits/stdc++.h>
#define RG register
#define cant "Orz, I cannot find x!"
using namespace std;

inline int read()
{
	int data=0, w=1;
	char ch=getchar();
	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
	if(ch=='-') w=-1, ch=getchar();
	while(ch>='0'&&ch<='9') data=(data<<3)+(data<<1)+(ch^48), ch=getchar();
	return data*w;
}

template<int MOD, int MAXN>
class hash
{
	private:
		struct link { int next, key, val; } e[MAXN];
		int head[MOD], e_num;
		inline void Add(int pos, int key, int val) { e[++e_num]=(link){head[pos], key, val}; head[pos]=e_num; }
	public:
		hash() { clear(); }
		inline void clear() { memset(head, 0, sizeof(head)); e_num=0; }
		inline void insert(int x, int v) { Add(x%MOD, x, v); }
		inline int operator[] (int x)
		{
			for(RG int i=head[x%MOD];i;i=e[i].next)
				if(e[i].key==x) return e[i].val;
			return -1;
		}
};

hash<100007, 1000000> get;
int fastpow(RG int x, RG int y, RG int mod)
{
	int base=x%mod, ans=1;
	while(y)
	{
		if(y&1) ans=(1ll*ans*base)%mod;
		base=(1ll*base*base)%mod;
		y>>=1;
	}
	return ans;
}

int T, L;

inline int gcd(RG int x, RG int y)
{
	while(y) y^=x^=y^=x%=y;
	return x;
}

inline void BSGS(int a, int b, int p)
{
	if(!a%p) { puts(cant); return; }
	bool tag=true; get.clear();
	int m=ceil(sqrt(p)), ans=b%p;
	get.insert(ans, 0);
	for(RG int i=1;i<=m;i++)
	{
		ans=1ll*ans*a%p;
		get.insert(ans, i);
	}
	RG int t=fastpow(a, m, p); ans=t;
	for(RG int i=1; i<=m; i++, ans=1ll*ans*t%p)
		if(~get[ans])
		{
			RG int k=i*m-get[ans]; k=(k%p+p)%p;
			printf("%d\n", k);
			tag=false; break;
		}
	if(tag) puts(cant);
}

int main()
{
	T=read(); L=read();
	while(T--)
	{
		RG int y=read(), z=read(), p=read();
		if(L==1) printf("%d\n", fastpow(y, z, p));
		else if(L==2)
		{
			int e=gcd(y, p);
			if(z%e) puts(cant);
			else printf("%lld\n", ((z%p)*1ll*fastpow(y, p-2, p))%p);
		}
		else BSGS(y%p, z%p, p);
	}
	return 0;
}

矩阵乘法

洛谷P1939 【模板】矩阵加速（数列）

设$f[0],f[1],f[2]$表示当前项、前一项和前两项，设转移一步之后为$g[0],g[1],g[2],$则：

$g[0]=f[0]+f[2],g[1]=f[0],g[2]=f[1]$，可以推出转移矩阵：
$$
\left[
\begin{matrix}
1 & 1 & 0 \
0 & 0 & 1 \
1 & 0 & 0
\end{matrix}
\right]
$$

矩阵快速幂即可。

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
#include<iostream>
#include<cstdio>
#include<cstring>
#define RI register int
using namespace std;
typedef long long ll;
const int mo=1e9+7;

struct Matrix{
	private:
		int a[110][110];
		int n, MOD;
	public:
		Matrix(int mod, int an) :n(an) { MOD=mod; memset(a, 0, sizeof(a)); }
		inline int* operator [](int x) { return a[x]; }
		inline Matrix operator *(Matrix &b)
		{
			Matrix c(MOD,n);
			for(RI i=0;i<n;i++)
				for(RI j=0;j<n;j++)
					for(RI k=0;k<n;k++)
						c[i][k]=(c[i][k]+1ll*a[i][j]*b[j][k])%MOD;
			return c;
		}
		inline Matrix operator ^(ll k)
		{
			Matrix base=*this;
			Matrix ans(MOD,n);
			for(RI i=0;i<n;i++) ans[i][i]=1;
			while(k)
			{
				if(k&1) ans=ans*base;
				base=base*base;
				k>>=1;
			}
			return ans;
		}
};

inline ll read()
{
	ll data=0,w=1; char ch=0;
	while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
	if(ch=='-') w=-1,ch=getchar();
	while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();
	return data*w;
}
ll n,t;

int main()
{
	t=read();
	Matrix S(mo,3);
	Matrix T(mo,3);
	while(t--)
	{
		n=read();
		if(n==1||n==2||n==3) { puts("1"); continue; }
		T[0][0]=T[2][0]=T[0][1]=T[1][2]=1;
		S[0][0]=S[0][1]=S[0][2]=1;
		Matrix &&ans=(T^(n-3));
		Matrix &&ans2=S*ans;
		printf("%d\n",ans2[0][0]);
	}
	return 0;
}

高斯消元

洛谷P4035 [JSOI2008]球形空间产生器

我们学过一个公式：

$(x-a)^2+(y-b)^2=r^2$，其中$(x,y)$是圆上的一点，$(a,b)$为圆心，$r$为半径。
$$
\Rightarrow x^2-2xa+a^2+y^2-2yb+b^2=r^2 \
\Rightarrow -2xa-2yb+(a^2+b^2-r^2)=-x^2-y^2
$$
我们可以令$x_1=a,x_2=b,x_3=(a^2+b^2-r^2)$，这样一来，我们就能得到$n+1$个形如$ax_1+bx_2+cx_3+…+x_{n+1}=k$的方程。
$n$维坐标$+1$个常量，共$n+1$个未知数，有$n+1$个方程，用高斯-约旦消元法解方程即可。

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
#include<bits/stdc++.h>
#define RG register
#define clear(x, y) memset(x, y, sizeof(x));
using namespace std;

inline int read()
{
	int data = 0, w = 1;
	char ch = getchar();
	while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
	if(ch == '-') w = -1, ch = getchar();
	while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
	return data*w;
}

int n;
double a[20][20];
inline void Gauss()
{
	for(RG int i = 1, k = i; i <= n; i++, k = i)
	{
		for(RG int j = k + 1; j <= n; j++) if(fabs(a[k][i]) < fabs(a[j][i])) k = j;
		swap(a[i], a[k]);
		for(RG int j = i + 1; j <= n + 1; j++) a[i][j] /= a[i][i];
		a[i][i] = 1.;
		for(RG int j = 1; j <= n; j++)
		{
			if(i == j) continue;
			for(k = i + 1; k <= n + 1; k++) a[j][k] -= a[j][i] * a[i][k];
			a[j][i] = 0;
		}
	}
}

#define sqr(x) ((x) * (x))

int main()
{
	n = read() + 1;
	for(RG int i = 1; i <= n; i++)
	{
		for(RG int j = 1; j < n; j++)
			scanf("%lf", &a[i][j]), a[i][n + 1] -= sqr(a[i][j]), a[i][j] *= -2.;
		a[i][n] = 1;
	}
	Gauss();
	for(RG int i = 1; i < n; i++) printf("%.3lf ", a[i][n + 1]);
	return 0;
}
洛谷P2973 [USACO10HOL]赶小猪

设$f[i]$表示炸弹在第$i$个点爆炸的概率，显然$f[1]+…+f[n]=1$。

可以发现炸弹在$i$号点爆炸的概率正比于$i$号点的期望经过次数。所以有：
$$
f[i] = \sum\frac{f[j]×(1-\frac{p}{q})}{deg[j]}
$$
其中$i,j$间有边，$deg[j]$表示$j$的度数，$i>1$。高斯消元即可。

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
#include<bits/stdc++.h>
#define RG register
#define clear(x, y) memset(x, y, sizeof(x));
using namespace std;

inline int read()
{
	int data = 0, w = 1;
	char ch = getchar();
	while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
	if(ch == '-') w = -1, ch = getchar();
	while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
	return data*w;
}

const int maxn(310);
const long double eps(1e-15);
int n, m, p, q, deg[maxn], g[maxn][maxn];
long double P, a[maxn][maxn];

inline void Gauss()
{
	for(RG int i = 1, k = i; i <= n; i++, k = i)
	{
		for(RG int j = k + 1; j <= n; j++) if(fabs(a[k][i]) + eps < fabs(a[j][i])) k = j;
		swap(a[i], a[k]);
		for(RG int j = i + 1; j <= n + 1; j++) a[i][j] /= a[i][i];
		a[i][i] = 1.;
		for(RG int j = 1; j <= n; j++)
		{
			if(i == j) continue;
			for(RG int k = i + 1; k <= n + 1; k++) a[j][k] -= a[j][i] * a[i][k];
			a[j][i] = 0.;
		}
	}
}

int main()
{
	n = read(); m = read(); p = read(); q = read(); P = (long double)p / q;
	for(RG int i = 1, x, y; i <= m; i++) x = read(), y = read(), g[x][y] = g[y][x] = 1, ++deg[x], ++deg[y];
	for(RG int i = 1; i <= n; i++) a[i][i] = 1;
	for(RG int i = 1; i <= n; i++) for(RG int j = 1; j <= n; j++) if(g[i][j]) a[i][j] -= (1. - P) / deg[j];
	a[1][n + 1] = 1; Gauss();
	for(RG int i = 1; i <= n; i++) printf("%.9Lf\n", a[i][n + 1] * P);
	return 0;
}

同余类最短路

洛谷P2662 牛场围栏

可以先求出哪些长度的木板是可以使用的。然后。。。然后怎么做？

设$s$是最短的可以使用的木板，如果我们能拼出长度为$g$的木板，我们就能拼出长度为$g,g+s,g+2×s…$的所有木板。

可以这样：设$f[i]$表示能拼出的、长度$\%s=i$的最短木板，显然$f[i],f[i]+s…$都可以被拼出。所以答案就是$max(f[0…s-1])$。$f$数组可以用类似最短路的方法求出。

有没有一种似曾相识的感觉？

给定$a,b$，问最大的$x$使得$x$不能被非负整数个$a,b$表示出来。

小凯的疑惑？

运用同余类最短路的思想，我们可以方便地证明小凯的疑惑中的结论：钦定$a<b$，则$f[((a-b)\%a+a)\%a]=a\times b-b$。所以$a\times b-a-b$是最后一个不能被拼出的数。

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
#include<bits/stdc++.h>
#define RG register
#define clear(x, y) memset(x, y, sizeof(x));
using namespace std;

inline int read()
{
	int data = 0, w = 1;
	char ch = getchar();
	while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
	if(ch == '-') w = -1, ch = getchar();
	while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
	return data*w;
}

const int maxn(5010);
int n, m, len[maxn], cnt, dis[maxn];
bool vis[maxn], h[maxn];

inline int gcd(int x, int y)
{
	while(y) y ^= x ^= y ^= x %= y;
	return x;
}

inline int Dijkstra()
{
	clear(dis, 0x7f); dis[0] = 0;
	for(RG int i = 2; i <= maxn - 10; i++)
		if(h[i]) len[++cnt] = i;
	int mod = len[1];
	for(RG int T = 1; T <= mod; T++)
	{
		int x = -1;
		for(RG int i = 0; i < mod; i++)
			if(!vis[i] && (x == -1 || dis[i] < dis[x])) x = i;
		if(x == -1) break;
		vis[x] = true;
		for(RG int i = 2, to; i <= cnt; i++)
			if(!vis[to = (x + len[i]) % mod]) dis[to] = min(dis[to], dis[x] + len[i]);
	}
	for(RG int i = 1; i < mod; i++) dis[i] -= mod;
	return *max_element(dis + 1, dis + mod);
}

int main()
{
	n = read(); m = read(); int g = 0;
	for(RG int i = 1, l; i <= n; i++)
	{
		l = read();
		for(RG int j = 0; j <= m; j++) h[l - j] = 1, g = gcd(l - j, g);
	}
	if(h[1] || g > 1) return puts("-1") & 0;
	else return printf("%d\n", Dijkstra()) & 0;
}
POJ3539 Elevator

钦定$a=min(a,b,c)$，按照之前的方法求出$f[0],…,f[a-1]$，答案就是：

$$
h-\sum_{i=0}^{a-1}\left{
\begin{array}
\lfloor \frac{h}{a} \rfloor + [i \leq h \% a],\;f[i] \geq h \
\lfloor \frac{f[i]}{a} \rfloor,\;f[i] < h
\end{array}
\right.
$$

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
#include<cstdio>
#include<cstring>
#include<queue>
#define RG register
#define clear(x, y) memset(x, y, sizeof(x));
using namespace std;

template<typename T>
inline T read()
{
	T data = 0, w = 1;
	char ch = getchar();
	while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
	if(ch == '-') w = -1, ch = getchar();
	while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
	return data*w;
}

const int maxn(1e5 + 10);
long long h, ans, dis[maxn];
struct edge { int next, to, dis; } e[maxn << 1];
int head[maxn], e_num, a, b, c, vis[maxn];
inline void add_edge(int from, int to, int dis)
{
	e[++e_num].next = head[from]; e[e_num].to = to;
	e[e_num].dis = dis; head[from] = e_num;
}

priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > q;
inline void Dijkstra()
{
	clear(dis, 0x3f); dis[1 % a] = 1; q.push(make_pair(1, 1 % a));
	while(!q.empty())
	{
		int x = q.top().second; q.pop();
		if(vis[x]) continue;
		vis[x] = 1;
		for(RG int i = head[x]; i; i = e[i].next)
		{
			int to = e[i].to;
			if(dis[to] > dis[x] + e[i].dis)
			{
				dis[to] = dis[x] + e[i].dis;
				q.push(make_pair(dis[to], to));
			}
		}
	}
}

int main()
{
	h = read<long long>(); a = read<int>(); b = read<int>(); c = read<int>();
	if(a > b) swap(a, b); if(a > c) swap(a, c);
	for(RG int i = 0; i < a; i++) add_edge(i, (i + b) % a, b), add_edge(i, (i + c) % a, c);
	Dijkstra();
	for(RG int i = 0; i < a; i++)
		if(dis[i] <= h)
			ans += 1ll * (h - dis[i]) / a + 1;
	printf("%lld\n", ans);
	return 0;
}
Source --- 数学, 数学方法 --- 数论, 数学方法 --- 概率论, 数学方法 --- 组合数学
【NOIP2012】疫情控制
2018-09-30考试
关注我

标签

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×