数学总结

数学总结


素数,因子

1.大区间素数

POJ-2689 Prime Distance
题意:题意:求给定区间内的质数距离最小的一对和质数距离最大的一对。(1 <= L,R <= 2.1E9, R-L <= 1e6)

大区间的素数题都是这样做的。筛出不超过R\sqrt{R}R​的所有质数p,然后再去枚举[L,R]区间内p的倍数,将其打上标记,最后区间内剩下的就都是素数了。这对于每个质数是logn的。

在打标记时发现由于数值很大,bitset120M开1e9,所以此题将数组平移L。就只用开1e6.

注意:1需要特判不是素数。

2.反素数思想:枚举因子

ZOJ 2562 More Divisors
题意:给定一个n (1<=n<=10^16),求小于等于n的最大反素数。
反素数:比它小的数的约数个数都小于它。

就是求小于等于n的约数最多的数。有约数个数定理:

X=p1k1p2k2p3k3p4k4...pnknX=p_1^{k_1}*p_2^{k_2}*p_3^{k_3}*p_4^{k_4}...p_n^{k_n}X=p1k1​​∗p2k2​​∗p3k3​​∗p4k4​​...pnkn​​

X的约数个数为:

Y=(1+k1)(1+k2)(1+k3)...(1+kn)Y=(1+k_1)(1+k_2)(1+k_3)...(1+k_n)Y=(1+k1​)(1+k2​)(1+k3​)...(1+kn​)

要约数最多,我们就结合反素数这种思想。dfs搜索每个质因子,对于每个质因子枚举它的指数。

const ll inf = 999999999999999999;
ll pri[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67},best,ans,n;
void dfs(ll dep,ll tmp,ll num){
	if(dep >= 16) return;
	if(best < num) {
		best = num;
		ans = tmp;
	}
	if(best == num) ans = min(ans,tmp);
	for(int i = 1; i <= 63; ++i){
		if(pri[dep] > n / tmp) break;
		dfs(dep + 1,tmp *= pri[dep],num * (i + 1));
	}
}
int main(){
	while(~scanf("%lld",&n)){
		best = 0;
		ans = inf;
		dfs(0,1,1);
		printf("%lld\n",ans);
	}
	return 0;
}

HDU 6216 A Cubic number and A Cubic Number
题意:判断一个素数是否是两个立方数之差,就是验差分。。

只有相邻两立方数之差才可能,因为x3y3=(xy)(x2+xy+y2)x^3-y^3=(x-y)(x^2+xy+y^2)x3−y3=(x−y)(x2+xy+y2),看(x-y),就能很快想到不相邻的立方数之差是不可能是素数的.

然后把y=x+1代入,得:p=3x2+3x+1p=3x^2+3x+1p=3x2+3x+1,所以可得判断条件为:①p-1必须能被3整除;②(p-1)/3必须能表示为两个相邻整数之积。

POJ 3421 X-factor Chains
题目大意:一个数列,起始为1,终止为一给定数X,满足Xi < Xi+1 并且Xi | Xi+1。
求出数列最大长度和该长度下的情况数。

很简单想到将X分解质因数,这样我们每加一个数就是前一个数*其中一个质因数即可。所以长度为质因数个数。

情况数就是这些素因子的排列组合数。需要去重。

同余

1.换模问题

POJ 1845 Sumdiv
在经典不过的数论求约数和的问题。
ABA^B%AB的所有约数和。

$ A = {p_1^{c_1} * p_2^{c_2} * …*p_n^{c_n}}$

$ A^B= {p_1^{c_1B} * p_2^{c_2B} * …p_n^{c_nB}}$

$sum = (p_1^0 + p_1^1 + …+p_1^{c_1B}) * (p_2^0 + p_2^1 + …+p_2^{c_2B}) $

有两种方法:

1.用等比数列求和公式,注意求和时候模的mod是转换后的模值。

2.用分治,分奇偶两种情况。

void make_prime(ll m){
	for(ll i = 2; i <= m; ++i){
		if(!flg[i]) pri[++cnt] = i;
		for(ll j = 1; j <= cnt && pri[j] <= m / i ; ++j){
			flg[i * pri[j]] = 1;
			if(i % pri[j] == 0) break;
		}
	}
}
ll Mul(ll a,ll b,ll c){
	a %= c;ll ret = 0;
	while(b){
		if(b & 1) ret = (ret + a) % c;
		a = (a + a) % c;
		b >>= 1;
	}
	return ret;
}
ll Power(ll a,ll b,ll c){
	a %= c;ll ret = 1;
	while(b){
		if(b & 1) ret = Mul(ret,a,c) % c;
		a = Mul(a,a,c) % c;
		b >>= 1;
	}
	return ret;
}

int main(){
	make_prime(50000);
	A = read();B = read();
	ll t = sqrt(A) + 1,i = 1;
	while(A > 1 && pri[i] <= t){
		if(A % pri[i] == 0){
			p[++num] = pri[i];
			while(A % pri[i] == 0){
				A /= pri[i];
				a[num]++;
			}
		}
		++i;//!!
	}
	if(A > 1){ // !!
		p[++num] = A;
		a[num] = 1;
	}
	for(ll i = 1; i <= num; ++i){
		ll P = (p[i] - 1) * mod;//!!!!换模!!!!
		ll up = (Power(p[i],a[i] * B + 1,P) - 1 + P) % P;
		sum *= (up / (p[i] - 1)) % mod;
		sum %= mod;
	}
	printf("%lld\n",sum);
	return 0;
}

这道题是单组数据,不需要筛素数表,不管是枚举质数,还是每个可能成为因子的数,分解质因数的时间复杂度都是O(N\sqrt NN​)

但如果是所有数都需要枚举因子,就枚举每个因子,时间复杂度O(nlogn)

HDU 5690 All X
F(x,m)F(x,m)F(x,m) 代表一个全是由数字x组成的m位数字。请计算,以下式子是否成立:
F(x,m)  mod   kcF(x,m) \ \ mod\ \ \ k ≡ cF(x,m)  mod   k≡c
1x91m10100c1≤x≤9,1≤m≤10^10,0≤c1≤x≤9,1≤m≤1010,0≤c

F(x,m)=xx...x=10m19xF(x,m)=xx...x = \frac{10^m-1}{9}*xF(x,m)=xx...x=910m−1​∗x;数据范围太过毒瘤,要快速幂套快速幂。

注意向SUMDIV一样要换模。$\frac{(10^m−1)%9k}{9}∗x%k=c%k $

POJ 2657 Comfort
题意:n个点顺时针围成一圈(编号1~n),初始时在1点,每次可以顺时针移动k点,n个点中有一些点有障碍物,求最小的k使得在不经过任何一个有障碍物的点就可以到达z点

为方便取模,先将所有点编号减一变成0~n-1,从1到z枚举k,对于每个k,如果一元线性同余方程k*x=z(mod n)有解g(此处g为最小正整数解),说明每次跳k步可以到达z点,之后枚举每个障碍物判断是否会经过障碍物,对于某障碍物ob[i],如果有解且最小正整数解y<g,说明会经过这个障碍物,否则不会经过,以此来判断当前k是否满足条件,第一次遇到满足条件的k一定为最小的k.

拓展欧几里得:

hdu 1576 A/B
要求(A/B)%9973,但由于A很大,我们只给出n(n=A%9973).(我们给定的A必能被B整除,且gcd(B,9973) = 1)。
Input
数据的第一行是一个T,表示有T组数据。
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。
Output
对应每组数据输出(A/B)%9973。

$A = 9973 * k + n $

A=tBA = t * BA=t∗B

于是9973k+n=tB9973 * k + n = t * B9973∗k+n=t∗B

左右互换一下:n=tB+9973kn = t * B + 9973 * kn=t∗B+9973∗k

然后就可以用exgcd求tB+9973k=1t * B + 9973 * k = 1t∗B+9973∗k=1

最后输出tnt * nt∗n即可

UVA 12169 不爽的裁判
题意:随机选取x1,a,b,根据公xi=(axi1+b)%10001式xi=(a*xi-1+b)\%10001式xi=(a∗xi−1+b)%10001得到一个长度为2*n的序列,奇数项作为输入,求偶数项,若有多种,随机输出一组答案
即给出已知的x1,x3,x5,x7x2k+1x_{1},x_{3},x_{5},x_{7}……x_{2k+1}x1​,x3​,x5​,x7​……x2k+1​,找出a和b,满足递推式,并输出x2,x4,x6x2kx_{2},x_{4},x_{6}……x_{2k}x2​,x4​,x6​……x2k​ (0<=a,b<=10000)

我们尝试找找x1x_{1}x1​和x3x_{3}x3​的关系。

x2=(ax1+b)%10001x2=(a*x1+b)\%10001x2=(a∗x1+b)%10001

x3=(ax2+b)%10001x3=(a*x2+b)\%10001x3=(a∗x2+b)%10001
带入得,

x3=(a((ax1+b)%10001)+b)%10001x3=(a*((a*x1+b)\%10001)+b)\%10001x3=(a∗((a∗x1+b)%10001)+b)%10001

x3=(a(ax1+b)+b)%10001x3=(a*(a*x1+b)+b)\%10001x3=(a∗(a∗x1+b)+b)%10001

将x3看成a(ax1+b)+ba*(a*x1+b)+ba∗(a∗x1+b)+b除以100011000110001的余数

则有 x3+y10001=aax1+ab+b=aax1+(a+1)bx3+y*10001=a*a*x1+a*b+b=a*a*x1+(a+1)*bx3+y∗10001=a∗a∗x1+a∗b+b=a∗a∗x1+(a+1)∗b

再移项 x3aax1=(a+1)by10001x3-a*a*x1 =(a+1)*b-y*10001x3−a∗a∗x1=(a+1)∗b−y∗10001

所以我们枚举a,解出b,再用其他项验证。

注意不定方程ax+by=cax+by=cax+by=c有解的条件是gcd(a,b)cgcd(a,b)|cgcd(a,b)∣c

UVA 12716 GCD 和 XOR
题意:输入整数n(1<=n<=3*10^7),有多少对整数(a,b)满足:1<=b<=a<=n,且gcd(a,b)=a XOR b。例如:n=7时,有4对:(3,2),(5,4),(6,4),(7,6)

本题的主要想法就是找到一个沟通gcda,bgcd(a,b)gcd(a,b)和a  xor  ba\ \ xor\ \ ba  xor  b的桥梁.

a  xor  baba \ \ xor \ \ b≥a-ba  xor  b≥a−b。假如二进制位上相同,那么都是0,加入二进制位上不同,前者一定是1,后者可能是1(1-0)或-1(0-1)

abgcd(a,b)a-b≥gcd(a,b)a−b≥gcd(a,b)。因为gcd(a,b)=gcd(a,ab)=gcd(b,ab)gcd(a,b)=gcd(a,a-b)=gcd(b,a-b)gcd(a,b)=gcd(a,a−b)=gcd(b,a−b)显然abgcd(a,ab)a-b≥gcd(a,a-b)a−b≥gcd(a,a−b),得证.

我们现在已知gcda,b=a  xor  bgcd(a,b)=a\ \ xor \ \ bgcd(a,b)=a  xor  b,根据夹逼法,a  xor  b=ab=gcd(a,b)=gcd(a,ab)a\ \ xor \ \ b=a-b=gcd(a,b)=gcd(a,a-b)a  xor  b=a−b=gcd(a,b)=gcd(a,a−b)

所以如果a和b是满足题意的二元组,前提是aba-ba−b是aaa的因子

因此我们枚举aba-ba−b,求得它的所有倍数,再判断ab=a  xor  ba-b=a\ \ xor \ \ ba−b=a  xor  b是否成立。

时间复杂度O(N+N/2+N/3++N/N)=O(NlogN)O(N+N/2+N/3+……+N/N)=O(NlogN)O(N+N/2+N/3+……+N/N)=O(NlogN)

注意:这类题是不可能一个一个枚举因子的.时间复杂度O(NO(\sqrt N)O(N​)

它只可能利用上式O(N+N/2+N/3++N/N)=O(NlogN)O(N+N/2+N/3+……+N/N)=O(NlogN)O(N+N/2+N/3+……+N/N)=O(NlogN)枚举所有的倍数或因子。

逆元

HDU 5976 Detachment
题意:给一个数N(N<=10^9),让你把它拆成若干各不相同的数Ai,ΣAi=NΣAi=NΣAi=N,要求ΠAiΠAiΠAi(累乘)最大。

在简单枚举后发现ai应该从2开始,并且取连续的自然数。但是我们拆到最后可能会剩下一个数x。我们把x从后均摊到每一个ai上。然后就是一个阶乘加上逆元就能搞定的事。

欧拉函数

HDU 4983 Goffi and GCD
题目大意:给你N和K,问有多少个数对满足gcd(N-A,N)*gcd(N-B,N)=N^K。

题解:由于 gcd(a, N) <= N,于是 K>2 就无解。

K=2 只有一个解 A=B=N。

K=1的话我们枚举gcd(A,N)=ggcd(A,N)=ggcd(A,N)=g,那么gcd(B,N)=N/ggcd(B,N)=N/ggcd(B,N)=N/g。问题转化为统计满足gcd(A,N)=ggcd(A,N)=ggcd(A,N)=g的A的个数。这个答案就是 φ(N/g)φ(N/g)φ(N/g)。答案是Σφ(N/g)φ(g)(gN)Σφ(N/g)*φ(g)(g|N)Σφ(N/g)∗φ(g)(g∣N)。

HDU 2588 GCD
题意:输入 N 和 M (2<=N<=1000000000, 1<=M<=N),找出所有的X满足1<=X<=N 且 gcd(X,N)>=M.

思路:枚举N的大于等于M的公约数g[i],结果为所有φng[i]\sumφ\frac{n}{g[i]}∑φg[i]n​的欧拉函数的值的和

排列组合

HDU 5894
题意:m个人需要坐在有n个座位的圆桌上,使得任意两个人之间距离至少为k,座位都不相同,人可以看做相同,求方案数。

可以想象成每一个人后面至少跟着k个座位

当一个人的位置确定以后,就变成了sum = C(n - 1 - m * k ,m - 1)

因为第一个人选取的位置可能是任意一个座位,所以sum * n

因为可能所有人都成为第一个人,所以ans = sum * n / m

题目大意:
在一个 n x m 的矩阵中插入任意数字,使得每一行每一列数的乘积为 k,其中 k要么是 1 要么是 -1. 我们注意到插入的数只可能是 1 或 -1.

我们只考虑 -1 的数目。当 k=-1 时,每行每列有奇数个 -1,其他的为 1;当 k=1 时,每行每列有偶数个 -1,其他的为 1. 但是你添入一个数会同时影响到一行和一列,又因为数据范围比较大,直接模拟肯定是行不通的,应该存在某个公式。

换种思维考虑,现在把最后一行和最后一列空出来,其他的空无论添任何值,我们都可以通过在最后一行和最后一列添加 1 或 -1 使得满足题意,因为这样我们可以控制 -1 的奇偶。所以有$ (n-1)(m-1)$ 个值是可以任添的,每个空有 2 种选择,所以结果是$ 2^{(n-1)(m-1)} $,直接做会超时,可以用快速幂取模。

注意,当 k=-1 时,如果行列的奇偶性质不同,则怎么填都会有冲突,所以这个时候答案是 0,需要特判。

CodeForces 888D Almost Identity Permutations
给出n和k计算满足至少有(n-k)个位置的值a[i]==i的1~n的全排列的个数。k<=4

观察题目数据范围,发现k的取值范围只有1~4,故考虑能否直接分类讨论找出数学公式。

当k=1时,显然无法做到只有一个位置a[i]!=i,即只有一种全排列。

当k=2时,我们先去考虑有且只有两个位置a[i]!=i的数目,显然我们需要从1~n中取出一个二元组 < i , j > (其中i < j),然后将他们每个二元组交换顺序即可,容易发现二元组数目为C(n,2),答案加上k = 1的情况即可。

当k=3时,我们先去考虑有且只有三个位置a[i]!=i的数目,显然我们需要从1~ n中取出一个三元组<i,j,k>(其中i<j<k),然后将他们每个三元组交换顺序且每个数都不在原来的位置上,容易发现三元组的数目为C(n,3),且对于每个二元组满足条件的排列数为2.

比如对于<1,2,3>来说,满足的交换顺序有<2,3,1>,❤️,1,2>。
所以答案为三元组数目2*2∗2+(k=2的数目)+(k=1的数目)

当k=4时,同上面的分析可知,四元组的数目为C(n,4).然后对于每个四元组,满足的排列数为9.
所以答案为四元组数目9*9∗9+(k=3的数目)+(k=2的数目)+(k=1的数目)

UVA 10375 选择与除法
计算C(p,q)/C(r,s)。输出保证不超过10^8,保留5位小数.

就直接算组合数了。

int main(){
	double a,b,c,d;
	while(~scanf("%lf%lf%lf%lf",&a,&b,&c,&d)){
		double ans=1.0;
		b=min(a-b,b);d=min(c-d,d);
		for(int i=1;i<=max(b,d);++i){
			if(i<=b&&i<=d) ans*=(a-i+1)/(c-i+1);
			else {
				if(i<=b) ans=ans*(a-i+1)/i;
				if(i<=d) ans=ans*i/(c-i+1);
			}
		}
		printf("%.5lf\n",ans);
	}
	return 0;
}

母函数

HDU 1028
题意: 给定整数n,求n有多少种划分方式。(对于4来说,1+3和3+1是同一种划分方式)
分析:以前是用dp做的,现在发现可以用母函数来做,对于整数n,可令Gx=(1+x+x2+x3+...+xn)(1+x2+x4+...)(1+x3+x6...)...1+x+x2+x3+...+xnG(x)=(1+x+x^2+x^3+...+x^n)(1+x^2+x^4+...)(1+x^3+x^6...)...,1+x+x^2+x^3+...+x^nG(x)=(1+x+x2+x3+...+xn)(1+x2+x4+...)(1+x3+x6...)...,1+x+x2+x3+...+xn的第i位xix^ixi表示1取i次的情况,(1+x2+x4+...)(1+x^2+x^4+...)(1+x2+x4+...)的第i位表示2取i次的情况,依次类推,最后多项式xnx^nxn的系数就是答案。(类似于邮票问题:有邮票1,2,3,4四张每张邮票,邮票的数量无限多,求出一个数方案的个数。)

int main(){
	for(int i = 0; i <= maxn; ++i) a[i] = 1;
	for(int i = 2; i <= maxn; ++i){
		for(int j = 0; j <= maxn; j += i)
			for(int k = 0; j + k <= maxn; ++k)
				b[j + k] += a[k];
		for(int k = 0; k <= maxn; ++k) a[k] = b[k],b[k] = 0;
	}
	while(~scanf("%d",&n)) printf("%d\n",a[n]);
	return 0;
}

思维

CodeForces 711D Directed Roads
题意:给一个图,n个点n条边,每条边可以反方向,问有多少种方案使得图中没有环。

只要找出图中的环,任意改变(大于等于1小于n)条边,都可以使得一个环不是环。一个环的方案数就是C(1,n)+C(2,n)+C(3,n)+…C(n-1,n),这个组合数的和为2的n次方减2.

每个连通量必然有一个环,dfs的时候算出每个连通块中点的个数y,算出连通块中环中的点的个数x,所以这个连通块不成环的答案是2yx(2x2)2^{y - x} * (2^x - 2)2y−x∗(2x−2)。

最后每个连通块的答案相乘即可。

CodeForces 689E Mike and Geometry Problem
题意:给出n个线段[li,ri],求任意k个线段所共同覆盖的点的总和。

对于每一条线段,区间[li,ri]加一,如果一个位置的值为m,那么最后的结果ans += C(m,k);

如果只是离散化端点的话,没法求得中间部分被覆盖的点,所以在离散化时保证相邻两点中间留出一个1,对于中间的点,求出当前的值*(相邻两点实际距离-1)即是结果。

错排

f(1)=0,f(2)=1,f(n)=(n-1)*[f(n-1)+f(n-2)]

矩阵乘法

POJ 3070 Fibonacci
题意:就是让你求斐波拉切数列的第n项的后面四位。

分析:矩阵快速幂优化dp。

注意E是(i,i)=1,其他为0.

UVA10870 Recurrences
题意:计算f(n) = a1 f(n - 1) + a2 f(n - 2) + a3 f(n - 3) + … + ad f(n - d). d<=15
在上题的基础上变成了多个。构造转移矩阵。

POJ 3233 Matrix Power Series
给定矩阵A,求A + A^2 + A^3 + … + A^k的结果(两个矩阵相加就是对应位置分别相加)。输出的数据mod m。k<=10^9。

矩阵的逆(类似数的逆元)我不会。就只能分治了。

struct matrix{
	int a[maxn][maxn];
	matrix(){memset(a,0,sizeof(a));	}
	void print(){
		for(int i = 1; i <= n; ++i)	{
			for(int j = 1; j <= n; ++j) printf("%d ",a[i][j]);
			printf("\n");
		}
	}
}e;
inline matrix add(matrix A,matrix B){
	matrix C;
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)
			C.a[i][j] = (A.a[i][j] + B.a[i][j])% mod;
	return C;
}
inline matrix mul2(matrix A,matrix B){
	matrix C;
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)
			for(int k = 1; k <= n; ++k)
				C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j]) % mod;
	return C;
}
inline matrix mul1(matrix A,int k){
	matrix ret = e;
	while(k){
		if(k & 1) ret = mul2(A,ret);
		A = mul2(A,A);
		k >>= 1;
	}
	return ret;
}
inline matrix solve(matrix A,int b){
	matrix C;
	if(b == 1) return A;
	if(b % 2 == 1) return add(mul1(A,b),mul2(add(mul1(A,b / 2),e),solve(A,b / 2)));
	return mul2(add(mul1(A,b/2),e),solve(A,b / 2));
}
int main(){
	scanf("%d%d%d",&n,&k,&mod);
	matrix A;	for(int i = 1; i <= n; ++i) e.a[i][i] = 1;
	for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) scanf("%d",&A.a[i][j]);
	solve(A,k).print();
	return 0;
}

HDU 4965 Fast Matrix Calculation
题意:给出NKN*KN∗K的矩阵A和KNK*NK∗N的B,求(AB)NN(AB)^{N*N}(AB)N∗N结果矩阵中各元素模6 之和。(n<=1000,k<=6)

ABA*BA∗B的矩阵是NNN*NN∗N的矩阵,快速幂会超时,用乘法结合律ANNBNNA^{N*N} * B^{N*N}AN∗N∗BN∗N分别计算。

POJ 3150 Cellular Automaton
题目大意:给定n(1<=n<=500)个数字和一个数字m,这n个数字组成一个环(a0,a1…an-1)。如果对ai进行一次d-step操作,那么ai的值变为与ai的距离小于d的所有数字之和模m。求对此环进行K次d-step(K<=10000000)后这个环的数字会变为多少。

拿样例来说:

a矩阵:

a = 1 2 2 1 2

构造转移矩阵:

b =

1 1 0 0 1

1 1 1 0 0

0 1 1 1 0

0 0 1 1 1

1 0 0 1 1

POJ 3734_Blocks
题意:用红,绿,蓝,黄,四种颜色对一序列n个方块涂色,求出绿和红色方块数同时为偶数的染色方案数。mod=10007

dp+矩阵快速幂

首先明确有三种状态:

红和绿均为偶数

红和绿只有一个为奇数

红和绿均为奇数

设前三种方案数分别为aia_iai​,bib_ibi​,cic_ici​,则可以得到以下递推式:

ai+1=2ai+bia_{i+1}=2∗a_i+b_iai+1​=2∗ai​+bi​

bi+1=2ai+2bi+2cib_{i+1}=2∗a_i+2∗b_i+2∗c_ibi+1​=2∗ai​+2∗bi​+2∗ci​

ci+1=2cic_{i+1}=2∗c_ici+1​=2∗ci​

HDU 2604 Queuing
题意:给你n个人,排成一个长度是n的队伍,人只有两类f,m,问可以有多少种排法使度列中不出现fff,fmf这样的子串。

用f(n)表示n个人满足条件的结果,那么如果最后一个人是m的话,那么前n-1个满足条件即可,就是f(n-1);

如果最后一个是f那么这个还无法推出结果,那么往前再考虑一位:那么后三位可能是:mmf, fmf, mff, fff,

其中fff和fmf不满足题意所以我们不考虑,

如果是 mmf的话那么前n-3可以找满足条件的即:f(n-3);

如果是mff的话,再往前考虑一位的话只有mmff满足条件即:f(n-4)

所以f(n)=f(n-1)+f(n-3)+f(n-4)

BZOJ 1297 SCOI2009 迷路
题目大意:有向图里10个点,点与点之间距离不超过9,问从1刚好走过T距离到达n的方案数。

当时看到这题就想到了某道奶牛题(在图论在总结里)。

这两道题的区别就是奶牛题问的是走T条边,这道题是每条边都有一个边权求走过T边权的方案数。

所以可以看成奶牛题相当于这一题里的边权为1的情况。首先边权为1就把奶牛题的floyd那段改成矩乘就可以了.

那么接下来考虑边权不为1的情况,因为边权最多为9,我们就可以把每个点拆成9个点,x[1]~x[9]为x拆完的点,x[i]和x[i+1]连一条边权为1的边,然后x到y有一条边权为z的边,那么就把x的第z个点往y的第1个点连一条边.

然后跑矩乘就可以辣。

HDU 2254 奥运
题意:指定v1,v2,要求计算出在t1,t2天内从v1->v2的走法

思路:可以知道由矩阵求,即将其建图A,求矩阵At1+......+At2A^{t_1} + ...... + A^{t_2}At1​+......+At2​. AnA^nAn后,A.t[v1][v2]即是从v1到v2要n步
所以先预处理出A1A10000A^1 -A^{10000}A1−A10000的情况,后面再注意下细节,计算即可.

循环

UVA 11582 巨大的斐波那契数
输入两个非负整数a、b和正整数n(0<=a,b<2^64,1<=n<=1000),你的任务是计算f(ab)f(a^b)f(ab)除以n的余数,f(0)=0f(0) = 0f(0)=0, f(1)=1f(1) = 1f(1)=1,且对于所有非负整数i,f(i+2)=f(i+1)+f(i)f(i + 2) = f(i + 1) + f(i)f(i+2)=f(i+1)+f(i)。

观察发现此题上面什么都很大,只有n很小。就可以求出f[]关于n的循环节。再用aba^bab关于循环节取模即可。

康托展开

UVA 1262 密码
给出两个6行5列的字母矩阵,一个密码满足:密码的第i个字母在两个字母矩阵的第i列均出现。
然后找出字典序为k的密码,如果不存在输出NO。(k≤7777)

字典序为K。康托展开。

先把每个位置能填的数全部预处理出来,以样例为例:{ACDW}、{BOP}、{GMOX}、{AP}、{GSU}

一共43423=288种

逆展开:比如k=197。

197÷(342*3)=2……53 所以第一位选D

53÷(423)=2……5 所以第二位选P

5÷(2*3)=0……5 所以第三位选G

5÷(3)=1……2 所以第四位选P

2÷(1)=2……0 所以第五位选U

与康托展开略有不同的是可选的字母是固定的,不会因为之前选的而导致名次的改变。

上一篇:一种在程序中求两直线交点的简单数学方法


下一篇:DP&图论 DAY 7 上午