Hey
注意数据范围是否需要开longlong memset 只能设置0和-1 计算过程中会mod，相减之后可能会小于0 ，需要+mod再进行一次mod操作 容斥原理：用全部的方案数减去相反的方案数 重定向，用完记得删除每日一算法备战蓝桥杯。
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
1. 快速幂
可以快速进行乘方运算
时间复杂度：O(logb)
2024-04-04
//a的b次对p取模
int qmi(int a,int b,int p)
{
int res=1;
while(b)
{
if(b&1) res=(ll)res*a%p;
a=(ll)a*a%p;
b>>=1;
}
return res;
}
2. 最大公约数
2024-04-04
int gcd(int a,int b)
{
return b ? gcd(b,a%b) : a;
}
3. 最大公约数分解质因数
一个数的因数中如果是质数，那么就说这个数是这个数的质因数
算术基本定理：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积
时间复杂度：O(sqrt(n))
2024-04-05
void divide(int x)
{
for(int i=2;i<=x/i;i++)
if(x%i==0)
{
int s=0;
while(x%i==0) x/=i,s++;
cout<<i<<' '<<s<<endl;
}
if(x>1) cout<<x<<' '<<1<<endl;
cout<<endl;
}
4. 矩阵乘法
矩阵的n次相乘可以转换成快速幂
时间复杂度：O(sqrt(n))
2024-04-06
斐波那契的迭代可以转换成矩阵乘法
类似的迭代问题AcWing.1217垒骰子
//矩阵乘法
void mul(int a[][2],int b[][2])
{
int c[2][2]={0};
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
c[i][j]=(c[i][j]+a[i][k]*b[k][j])%mod;
memcpy(a,c,sizeof c);
}
//矩阵乘法快速幂
int qmi(int n)
{
int a[2][2]={
{0,1},
{0,0}
};
int f[2][2]={0,1,1,1};
while(n)
{
if(n&1) mul(a,f);
mul(f,f);
n>>=1;
}
return a[0][0];
}
5. 组合计数
2024-04-09
第一种方法：
Cab=(ll)fact[a]infact[b]%modinfact[a-b]%mod
fact[i] 表示i的阶乘
infact[i] 表是i的阶乘的（-1）次
费马小定理：如果p是一个质数，而整数a不是p的倍数，则有a^(p-1)≡1(mod p)
mod是一个质数 fainfa=1 fainfa=fa^(mod-1) infa=fa^(mod-2)
int qmi(int a,int k,int m)
{
int res=1;
while(k)
{
if(k&1) res=(ll)res*a%m;
a=(ll)a*a%m;
k>>=1;
}
return res;
}
//预处理阶乘
fact[0]=infact[0]=1;
for(int i=1;i<=N;i++)
{
fact[i]=(ll)fact[i-1]*i%mod;
infact[i]=qmi(fact[i],mod-2,mod);
//费马小定理
}
第二种方法：
Cab=Ca-1b+Ca-1b-1
对于一个苹果，可以
包含 （从a-1个苹果里选b-1个Ca-1b-1）
不包含 （从a-1个苹果里选b个Ca-1b）
for(int i=0;i<N;i++)
for(int j=0;j<=i;j++)
if(j==0) c[i][j]=1;
else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
