河北邯郸网站建设公司,博罗网站设计,松江企业做网站,中企动力重庆分公司目录
今日知识点#xff1a;
辗转相减法化下三角求行列式
组合数动态规划打表
约数个数等于质因数的次方1的乘积
求一个模数
将n个不同的球放入r个不同的盒子#xff1a;f[i][j]f[i-1][j-1]f[i-1][j]*j
将n个不同的球放入r个相同的盒子#xff1a;a[i][j]a[i-j][j]a[… 目录
今日知识点
辗转相减法化下三角求行列式
组合数动态规划打表
约数个数等于质因数的次方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 mod0x1f1f1f1f;
typedef long long ll;
ll t,n,a[10][10];
ll solve(){//计算行列式化简成下三角型有点类似辗转相除法ll res1,w1;//res是结果w是符号for(int i1;in;i){//对[i][i]元素所在的列处理for(int ji1;jn;j){
//我们每次都让下面的行减去上面行的a[j][i]/a[i][i]倍然后再让最小的行放到上面判断是不是[i][i]是不是0如果不是就继续。while(a[i][i]){ll dia[j][i]/a[i][i];for(int ki;kn;k){a[j][k](a[j][k]-di*a[i][k]%modmod)%mod;//有负数的话要加一次mod}swap(a[i],a[j]);w-w;}swap(a[i],a[j]);w-w;}}for(int i1;in;i)resa[i][i]*res%mod;resw*res;return (resmod)%mod;
}int main(){cint;while(t--){cinn;for(int i1;in;i)for(int j1;jn;j)cina[i][j];coutsolve()\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,ans1;
ll a[10007][107];int main(){cinnm;a[0][0]1;for(int i1;i10000;i){//利用动态规划求组合数[i][j][i-1][j-1][i-1][j]a[i][0]1;for(int j1;j100;j){a[i][j](a[i-1][j-1]a[i-1][j])%12520;}}for(int i1;im;i){cinnum;ansans*a[n][num]%12520;n-num;}coutans;
} 约数个数
求n的约数个数。 #include bits/stdc.h
using namespace std;
int main(){方法一直接找就完了约数一定成对出现但是相等时候要特判一下int n,ans0;cinn;for(int i1;i*in;i){if(n%i0)ans2;if(i*in)ans--;}coutans;
}int main(){ //方法二约数等于质因数的次方加1的乘积(此方法速度极快)int n,ans1;cinn;for(int i2;i*in;i){int tmp0;while(n%i0){tmp;n/i;//求质因数的次数}ans*(tmp1);}if(n!1)ans*2;//最后的质因数也不要忘了coutans;
} 模数
输入ab问有多少个x使得a%xb。如果有无穷多个输出infinity不存在输出0。
思路
首先分析一下a%xb等价于找a-b的因数约数个数。但是先等等这个因数还必须满足比余数大。
#include bits/stdc.h
using namespace std;int run(int a,int b){int ans1;for(int i2;i*ia;i){if(ib||a/ib)continue;int tmp0;while(a%i0){//判断是不是质因数tmp;a/i;//一边缩小a}ans*(tmp1);}if(a!1)ans*2;return ans;
}int main(){int a,b;cinab;if(ab){coutinfinity;return 0; }if(ab){cout0;return 0;}coutrun(a-b,b);} 数树 思路
反正就是不能出现其他组的倍数这种情况。 可以直接上筛子提前把不成立给筛掉不过有点麻烦。
仔细观察不难你会发现
只要ab的最大公约数不是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)-2return b0?a:gcd(b,a%b);//(25,14)(14,11)(11,3)(3,2)(2,1)(1,0)-1
}int main(){cinc;for(int i1;ic;i){cinn;int ans0;for(int j1;jn;j)for(int k1;kn;k){if(gcd(j,k)1)ans;}couti n ans2\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(){cinnr;f[0][0]1;for(int i1;in;i){for(int j1;jmin(i,r);j){f[i][j]f[i-1][j-1]f[i-1][j]*j;}}ansf[n][r];for(int i1;ir;i){ans*i;}coutans;
}
/*
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大那么有了sumi*(k-cnt)n这个分支优化。可以理解成是一共1组且组内单增即可。
dfs的速度就变快了很多。
#include bits/stdc.h
using namespace std;
int n,k,ans0,a[205][70];
//int main(){//解法一动态规划
// cinnk;
// for(int i1;in;i)a[i][1]1;
// for(int i2;in;i)
// for(int j2;j(i,k);j){
// a[i][j]a[i-1][j-1];
// if(i2*j)a[i][j]a[i-j][j];
// }
// couta[n][k];
//}
//解法二dfs优化
void dfs(int cnt,int up,int sum){//cnt是已选个数up已选数的最大值sum是总和if(cntk){if(sumn)ans;return ;}for(int iup;sumi*(k-cnt)n;i){//下一个点必须比当前点大dfs(cnt1,i,sumi);//选下一个数}
}
int main(){cinnk;dfs(0,1,0);coutans;
}
