目录

今日知识点：

辗转相减法化下三角求行列式

组合数动态规划打表

约数个数等于质因数的次方+1的乘积

求一个模数

将n个不同的球放入r个不同的盒子：f[i][j]=f[i-1][j-1]+f[i-1][j]*j

将n个不同的球放入r个相同的盒子：a[i][j]=a[i-j][j]+a[i-1][j-1]

行列式 

甜甜花的研究 

约数个数

模数 

数树 

盒子与球 

 数的划分 

---

        

        

        

行列式 

给出一个矩阵求 行列式。

输入：  
1
3
1 -2 -1
0 3 2
3 1 -1

思路：

不能直接乘上上面行的倍数来消除本行对应元素。试试辗转相减法把。

(1,3)减去2倍(0,1)->(1,0)

(5,3)减去0倍(3,5)减去1倍(2,3)减去1倍(1,2)减去2倍(0,1)->(1,0)

然后每次检查上面行的元素是否为0，然后换回来就行了

#include <bits/stdc++.h>
using namespace std;
const int mod=0x1f1f1f1f;
typedef long long ll;
ll t,n,a[10][10];
ll solve(){//计算行列式，化简成下三角型（有点类似辗转相除法）
	ll res=1,w=1;//res是结果，w是符号
	for(int i=1;i<=n;i++){//对[i][i]元素所在的列处理
		for(int j=i+1;j<=n;j++){
//我们每次都让下面的行减去上面行的a[j][i]/a[i][i]倍，然后再让最小的行放到上面判断是不是[i][i]是不是0，如果不是就继续。
			while(a[i][i]){
				ll di=a[j][i]/a[i][i];
				for(int k=i;k<=n;k++){
					a[j][k]=(a[j][k]-di*a[i][k]%mod+mod)%mod;//有负数的话要加一次mod
				}
				swap(a[i],a[j]);
				w=-w;
			}
			swap(a[i],a[j]);
			w=-w;
		}
	}
		for(int i=1;i<=n;i++)
			res=a[i][i]*res%mod;
		res=w*res;
		return (res+mod)%mod;	
}

int main(){
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			cin>>a[i][j];
		cout<<solve()<<'\n';
	}	
}

        

        

甜甜花的研究 

有n个各不相同的甜甜花种子，现在雇佣了m个人，每人能照顾ai个花。问一共多少种分配方法把花分出去。（数据保证种子有剩余）

输入           输出：20（结果对12520取模）
5 2
3 1

思路：

因为种子一定有剩余。那么第一个人可以有C(n,a1)种分法，第二个人有C(n-a1,a2)种分法……

乘起来就完事了。主要是数据很大，直接一个个硬算不划算。直接上公式：

C(n,m)=C(n-1,m-1)+C(n-1,m);

记忆：每个人都有两种状态要么是被选到要么未被选到。C(n-1,m-1)对应被选到的情况数，也就是内定该人然后去选m-1个；C(n-1,m)对应未被选到的情况数，也就是直接忽略该人然后去选m个。

然后利用动态规划打表就会非常快了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,num,ans=1;
ll a[10007][107];

int main(){
	cin>>n>>m;
	a[0][0]=1;
	for(int i=1;i<=10000;i++){//利用动态规划求组合数[i][j]=[i-1][j-1]+[i-1][j]
		a[i][0]=1;
		for(int j=1;j<=100;j++){
			a[i][j]=(a[i-1][j-1]+a[i-1][j])%12520;
		}
	}
	for(int i=1;i<=m;i++){
		cin>>num;
		ans=ans*a[n][num]%12520;
		n-=num;
	}
	cout<<ans;
}

      

        

约数个数

求n的约数个数。

#include <bits/stdc++.h>
using namespace std;
int main(){方法一：直接找就完了，约数一定成对出现，但是相等时候要特判一下
	int n,ans=0;cin>>n;
	for(int i=1;i*i<=n;i++){
		if(n%i==0)ans+=2;
		if(i*i==n)ans--;
	}
	cout<<ans;
}

int main(){ //方法二：约数等于质因数的次方加1的乘积(此方法速度极快)
	int n,ans=1;cin>>n;
	for(int i=2;i*i<=n;i++){
		int tmp=0;
		while(n%i==0){
			tmp++;n/=i;//求质因数的次数
		}
		ans*=(tmp+1);
	}
	if(n!=1)ans*=2;//最后的质因数也不要忘了
	cout<<ans;
}

           

        

模数 

输入a，b问有多少个x使得a%x==b。如果有无穷多个输出infinity，不存在输出0。

思路：

首先分析一下，a%x==b，等价于找a-b的因数（约数）个数。但是先等等：这个因数还必须满足比余数大。

#include <bits/stdc++.h>
using namespace std;

int run(int a,int b){
	int ans=1;
	for(int i=2;i*i<=a;i++){
		if(i<=b||a/i<=b)continue;
		int tmp=0;
		while(a%i==0){//判断是不是质因数
			tmp++;a/=i;//一边缩小a
		}
		ans*=(tmp+1);
	}
	if(a!=1)ans*=2;
	return ans;
}

int main(){
	int a,b;
	cin>>a>>b;
	if(a==b){
		cout<<"infinity";
		return 0;	
	}
	if(a<b){
		cout<<0;return 0;
	}
	cout<<run(a-b,b);
	
}

         

        

数树 

思路：

反正就是不能出现其他组的倍数这种情况。 可以直接上筛子，提前把不成立给筛掉，不过有点麻烦。

仔细观察不难你会发现：

只要（a，b）的最大公约数不是1，那么就一定不是答案。然后统计就行了

#include <bits/stdc++.h>
using namespace std;
int c,n;

int gcd(int a,int b){//辗转相除法(36,14)(14,8)(8,6)(6,2)(2,0)->2
	return b==0?a:gcd(b,a%b);//(25,14)(14,11)(11,3)(3,2)(2,1)(1,0)->1
}

int main(){
	cin>>c;
	for(int i=1;i<=c;i++){
		cin>>n;
		int ans=0;
		for(int j=1;j<=n;j++)
			for(int k=1;k<=n;k++){
				if(gcd(j,k)==1)ans++;
			}
		cout<<i<<" "<<n<<" "<<ans+2<<'\n';
	}
}
/*
4
2
4
5
231
*/

        

         

盒子与球 

现有r个互不相同的盒子和n个互不相同的球，要将这n个球放入r个盒子中，且不允许有空盒子，一共有多少种放法？

思路：

主要是状态转移式子。f[i][j]=f[i-1][j-1]+f[i-1][j]*j;

（这个公式非常类似组合公式C(n,m)=C(n-1,m-1)+C(n-1,m)，因为两者的原理相同）

我们设置f[i][j]表示i个球j个盒子的放法。那么对于第i个球，要么自己一个盒子f[i-1][j-1]情况数，要么和别人一个盒子但是有j中选择f[i-1][j]*j种情况数。不断递推就行了

#include <bits/stdc++.h>
using namespace std;
int n,r,f[20][20],ans;

int main(){
	cin>>n>>r;
	f[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=min(i,r);j++){
			f[i][j]=f[i-1][j-1]+f[i-1][j]*j;
		}
	}
	ans=f[n][r];
	for(int i=1;i<=r;i++){
		ans*=i;
	}
	cout<<ans;
}
/*
3 2
6*/

        

        

 数的划分 

思路：

两种做法：

第一种：动态规划：

题目可以理解成把n个相同球放入k个相同盒子，然后因为球都是相同的，就不能再对最后一个球进行讨论了。应该对应一类球：

设置a[i][j]表示i个球放入j个盒子的方案数。

第一种情况：有一个盒子只有一个球，那么就对应了a[i-1][j]

第二种情况：每个盒子都至少有两个球，那么就对应看a[i-j][j]

所以：a[i][j]=a[i-j][j]+a[i-1][j-1]

第二种：dfs：

在已经放了i时候，每次可以放1~n-i个，所有dfs(i)有n-i个分支，这个复杂度很高，别着急，只需要把无效分支剔除即可很快。

仔细观察7的拆法：

1 1 5

1 2 4

1 3 3

2 2 3

2 3 2（重复了哟）

所以你发现了，要想不重复 ，就必须后面选的数比前面的大。所以在dfs(i)也就是选了i的时候，后面选的数都必须比i大，那么有了sum+i*(k-cnt)<=n这个分支优化。可以理解成是一共1组，且组内单增即可。

dfs的速度就变快了很多。

#include <bits/stdc++.h>
using namespace std;
int n,k,ans=0,a[205][70];
//int main(){//解法一：动态规划
//	cin>>n>>k;
//	for(int i=1;i<=n;i++)a[i][1]=1;
//	for(int i=2;i<=n;i++)
//		for(int j=2;j<=(i,k);j++){
//			a[i][j]=a[i-1][j-1];
//			if(i>=2*j)a[i][j]+=a[i-j][j];
//		}
//	cout<<a[n][k];
//}
//解法二：dfs+优化
void dfs(int cnt,int up,int sum){//cnt是已选个数，up已选数的最大值，sum是总和
	if(cnt==k){
		if(sum==n)ans++;
		return ;
	}
	for(int i=up;sum+i*(k-cnt)<=n;i++){//下一个点必须比当前点大
		dfs(cnt+1,i,sum+i);//选下一个数
	}
}
int main(){
	cin>>n>>k;
	dfs(0,1,0);
	cout<<ans;
}