AcWing基础算法课Level-2 第四讲 数学知识
【摘要】
AcWing基础算法课Level-2 第四讲 数学知识
您将学会以下数学名词 质数，试除法，埃式筛法，线性筛，辗转相除，算术基本定理，质因数分解，欧拉函数，快速幂，费马小定理，逆元，拓展欧几里得，...
AcWing基础算法课Level-2 第四讲 数学知识
您将学会以下数学名词
质数，试除法，埃式筛法，线性筛，辗转相除，算术基本定理，质因数分解，欧拉函数，快速幂，费马小定理，逆元，拓展欧几里得，一次同余方程，同余方程组，中国剩余定理，线性方程组，高斯消元，组合数，卢卡斯定理，卡特兰数，容斥原理，博弈论，NIM游戏, SG函数, Mex运算。
质数
AcWing 866. 试除法判定质数2425人打卡
AcWing 867. 分解质因数2276人打卡
AcWing 868. 筛质数2204人打卡
约数
AcWing 869. 试除法求约数2050人打卡
AcWing 870. 约数个数1849人打卡
AcWing 871. 约数之和1771人打卡
AcWing 872. 最大公约数1946人打卡
欧拉函数
AcWing 873. 欧拉函数1662人打卡
AcWing 874. 筛法求欧拉函数1452人打卡
快速幂
AcWing 875. 快速幂1916人打卡
AcWing 876. 快速幂求逆元1523人打卡
扩展欧几里得算法
AcWing 877. 扩展欧几里得算法1388人打卡
AcWing 878. 线性同余方程1254人打卡
中国剩余定理
AcWing 204. 表达整数的奇怪方式724人打卡
高斯消元
AcWing 883. 高斯消元解线性方程组916人打卡
AcWing 884. 高斯消元解异或线性方程组649人打卡
求组合数
AcWing 885. 求组合数 I1324人打卡
AcWing 886. 求组合数 II1134人打卡
AcWing 887. 求组合数 III976人打卡
AcWing 888. 求组合数 IV846人打卡
AcWing 889. 满足条件的01序列895人打卡
容斥原理
AcWing 890. 能被整除的数970人打卡
博弈论
AcWing 891. Nim游戏1134人打卡
AcWing 892. 台阶-Nim游戏890人打卡
AcWing 893. 集合-Nim游戏875人打卡
AcWing 894. 拆分-Nim游戏717人打卡
代码
AcWing 866. 试除法判定质数
//试除法：枚举到根号n一定能枚举出结果，因为因数是成对出现的
//i<=x/i是比起i*i<=x更好的写法，因为2^30会爆int
#include<bits/stdc++.h>
using namespace std;
bool isprime(int n){
if(n<2)return false;
for(int i = 2; i <= n/i; i++){
if(n%i==0)return false;
}
return true;
}
int main(){
int n; cin>>n;
for(int i = 1; i <= n; i++){
int x; cin>>x;
if(isprime(x))cout<<"Yes\n";
else cout<<"No\n";
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
AcWing 867. 分解质因数
//试除法分解质因数，枚举到因数的时候不断除掉就行
#include<bits/stdc++.h>
using namespace std;
int main(){
int T; cin>>T;
while(T--){
int x; cin>>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<<"\n";
}
}
if(x>1)cout<<x<<" "<<1<<"\n";
cout<<"\n";
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
AcWing 868. 筛质数
#include<iostream>
#define maxn 10000010
using namespace std;
int pri[maxn];
int main(){
int n, cnt=0; cin>>n;
pri[1] = 1;
for(int i = 2; i <= n; i++){
if(!pri[i]){
cnt++;
for(int j = 2*i; j <= n; j += i)
pri[j] = 1;
}
}
cout<<cnt<<"\n";
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
AcWing 869. 试除法求约数
//试除法求约数，枚举到因数就加入答案
#include<bits/stdc++.h>
using namespace std;
int main(){
int T; cin>>T;
while(T--){
int x; cin>>x;
vector<int>ans;
for(int i = 1; i <= x/i; i++){
if(x%i==0){
ans.push_back(i);
if(i!=x/i)ans.push_back(x/i);//i*i==n时只放一次
}
}
sort(ans.begin(),ans.end());
for(int t: ans)cout<<t<<" "; cout<<"\n";
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
AcWing 870. 约数个数
//n=p1^a1+p2^a2+p3^a3...pk^nk; p1^a1有(a1+1)个约数，p2^a2有(a2+1)个，所以n的约数就是他们乘起来
//然后所以试除法求约数个数乘起来
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int main(){
int T; cin>>T;
unordered_map<int,int>prime;
while(T--){
int x; cin>>x;
for(int i = 2; i <= x/i; i++){
while(x%i==0){
prime[i]++;
x /= i;
}
}
if(x>1)prime[x]++;
}
long long ans = 1;
for(auto t:prime)ans =ans*(t.second+1)%mod;
cout<<ans<<"\n";
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
AcWing 871. 约数之和
//n=p1^c1*p2^c2*...*pk^ck
//约数个数：(c1+1)*(c2+1)*...*(ck+1)
//约数之和：(p1^0+p1^1+…+p1^c1)*...*(pk^0+pk^1+…+pk^ck)
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=1e9+7;
int main(){
int T; cin>>T;
unordered_map<int,int>prime;
while(T--){
int x; cin>>x;
for(int i = 2; i <= x/i; i++){
while(x%i==0){
prime[i]++;
x /= i;
}
}
if(x>1)prime[x]++;
}
LL ans = 1;
for(auto t:prime){
int p=t.first, cnt = t.second;
LL sum = 1;
while(cnt--)sum = (sum*p+1)%mod;
ans = ans*sum%mod;
}
cout<<ans<<"\n";
return 0;
}
- 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
AcWing 872. 最大公约数
//gcd(a,b)==gcd(b,r), r=a%b;
#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b){return !b?a:gcd(b,a%b);}
int main(){
int T; cin>>T;
while(T--){
int a, b; cin>>a>>b;
cout<<gcd(a,b)<<"\n";
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
AcWing 873. 欧拉函数
//欧拉函数：给定一个正整数n,求1-n中与n互质的数的个数，记作f(n)。
//由算数基本定理得公式：N=(p1^a1)*(p2^a2)…(pm^am), N × (p1−1)/p1 × (p2−1)/p2 × … × (pm−1)/pm
#include<bits/stdc++.h>
using namespace std;
using namespace std;
typedef long long LL;
int main(){
int n; cin>>n;
for(int i = 1; i <= n; i++){
int x; cin>>x;
int t = x;
for(int i = 2; i <= x/i; i++){
if(x%i==0){
while(x%i==0)x/=i;
t = t/i*(i-1);
}
}
if(x>1)t=t/x*(x-1);
cout<<t<<"\n";
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
AcWing 874. 筛法求欧拉函数
//题意：给定一个正整数n，求1~n中每个数的欧拉函数之和。
//根据欧拉函数的2个性质，imodp==0,则phi(i*p)==phi(i)*p等来获得值
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e6+10;
int vis[maxn], prime[maxn], cnt;
int euler[maxn];
int main(){
int n; cin>>n;
euler[1] = 1;
for(int i = 2; i <= n; i++){
if(!vis[i]){
prime[cnt++] = i;
euler[i] = i-1;//质数与前面都互质，所以为i-1
}
for(int j = 0; prime[j] <= n/i; j++){
vis[prime[j]*i] = 1;
if(i%prime[j]==0){
//pj是i的最小质因子，i的分解质因数中，已经有pj
euler[prime[j]*i] = euler[i]*prime[j];
break;
}
//pj是i*pj的最小质因子，i的分解质因数中，没有pj
euler[prime[j]*i] = euler[i]*(prime[j]-1);
}
}
LL ans = 0;
for(int i = 1; i <= n; i++)
ans += euler[i];
cout<<ans<<"\n";
return 0;
}
- 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
AcWing 875. 快速幂
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL pows(LL a, LL x, LL p) {
if(x==0)return 1;
LL t = pows(a, x>>1,p);
if(x%2==0)return t*t%p;
return t*t%p*a%p;
}
int main(){
int T; cin>>T;
while(T--){
int a, b, p; cin>>a>>b>>p;
cout<<pows(a,b,p)<<"\n";
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
AcWing 876. 快速幂求逆元
//逆元定义：逆元素是指一个可以取消另一给定元素运算的元素, 比如一个数和其倒数互为乘法逆元ax=1,x=1/a，一个数和其相反数互为加法逆元等等a+x=0,x=-a。
//模意义下的逆元：因为任何数与1的乘积均为其本身，所以a%p意义下的乘法逆元为x满足ax%p==1。
/*
求a%p的乘法逆元
当p为质数时，可用快速幂求逆元，当p不是质数时，可用拓展欧几里得求。
a / b ≡ a * x (mod p)
两边同乘b可得 a ≡ a * b * x (mod p)
即 1 ≡ b * x (mod p)
同 b * x ≡ 1 (mod p)
由费马小定理可知，当n为质数时
b ^ (p - 1) ≡ 1 (mod p)
拆一个b出来可得 b * b ^ (p - 2) ≡ 1 (mod p)
故当p为质数时，b的乘法逆元 x = b ^ (p - 2)
*/
#include<bits/stdc++.h>
using namespace std;
using namespace std;
typedef long long LL;
LL pows(LL a, LL x, LL p) {
if(x==0)return 1;
LL t = pows(a, x>>1,p);
if(x%2==0)return t*t%p;
return t*t%p*a%p;
}
int main(){
int n; cin>>n;
for(int i = 1; i <= n; i++){
int a, p; cin>>a>>p;
if(a%p==0)cout<<"impossible\n";
else cout<<pows(a,p-2,p)<<"\n";
}
return 0;
}
- 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
AcWing 877. 扩展欧几里得算法
//题意：给出(a,b)，求一组可行(x,y)满足ax+by==gcd(a,b)
/*拓展欧几里得：
因为gcd(a,b)=gcd(b,a%b)，所以bx′+(a%b)y′=gcd(b,a%b)，且ax+by=gcd(a,b)
所以作差得ay′+b(x′−⌊a/b⌋∗y′)=gcd(b,a%b)，ay′+b(x′−⌊a/b⌋∗y′)=gcd(b,a%b)=gcd(a,b)
所以x=y′,y=x′−⌊a/b⌋∗y′，所以可以用递归算法，先求出下一层的x′和y′再利用上述公式回代
边界为：b=0 时 ax+by=a 此时x=1,y=0
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e6+10;
LL exgcd(LL a, LL b, LL &x, LL &y){
if(!b){
x = 1, y = 0;
return a;
}
LL r = exgcd(b, a%b, x, y);//gcd(a,b)==gcd(b,a%b)
LL t = x;
x = y; //x=y'
y = t-a/b*y; //y=x'-[a/b]*y';
return r;
}
int main(){
int n; cin>>n;
for(int i = 1; i <= n; i++){
int a, b; cin>>a>>b;
LL x, y; exgcd(a,b,x,y);
cout<<x<<" "<<y<<"\n";
}
return 0;
}
- 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
AcWing 878. 线性同余方程
//题意：给出(a,b,m)，求满足一次同余方程a∗x≡b(mod m)的x解(ps. b==1且a,m互质时x为逆元)
//思路：原式等价于a∗x−b是m的倍数，等价于a∗x+m∗y=b，所以有解当且仅当gcd(a,m)|b，此时用扩展欧几里得算法求出一组(x,y),ans=x∗b/gcd(a,m)%m
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e6+10;
LL exgcd(LL a, LL b, LL &x, LL &y){
if(!b){
x = 1, y = 0;
return a;//r==gcd(a,b);
}
LL r = exgcd(b, a%b, x, y);//gcd(a,b)==gcd(b,a%b)
LL t = x;
x = y; //x=y'
y = t-a/b*y; //y=x'-[a/b]*y';
return r;
}
int main(){
int n; cin>>n;
for(int i = 1; i <= n; i++){
int a, b, m; cin>>a>>b>>m;
LL x, y; LL r = exgcd(a,m,x,y);
if(b%r!=0)cout<<"impossible\n";
else cout<<(x*b/r%m)<<"\n";
}
return 0;
}
- 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
AcWing 204. 表达整数的奇怪方式
//数论：质数，约数，欧拉函数。逆元，同余方程，同余方程组
//题意：求解同余方程组，x满足一系列x≡mi(%ai)
/*
1. 解2个方程同余
x≡m1(%a1)推出x=k1∗a1+m1, (m2,a2)同理
联立2个得到k1∗a1+m1=k2∗a2+m2推出方程k1∗a1+k2∗(−a2)=m2−m1
exgcd解二元一次方程得(k1,k2)特解
注意有解需满足gcd(a1,-a2)|(m2-m1), d=gcd(a1,-a2)
2. 推广合并
已知性质k1=k1+k*a2/d,k2=k2+k*a1/d, k为任意倍数, a2/d和a1/d互质
此时方程通解为k1=k1∗(m2−m1)/d+k∗a2/d,k2=k2∗(m2−m1)/d+k∗a1/d, k为任意整数
由通解(k1,k2)和原方程解x=k1*a1+m1得x=(k1+k*a2/d)∗a1+m1=k1∗a1+m1+k∗lcm(a1,a2)
然后设a0=lcm(a1,a2),m0=k1∗a1+m1, 获得x=a0*k0+m0，再次与下一组联立
直到合并n个式子得到一个最终的式子，此时x=k*a+m算出的解即为答案
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL &x, LL &y){
if(!b){
x = 1, y = 0;
return a;//r==gcd(a,b);
}
LL r = exgcd(b, a%b, x, y);//gcd(a,b)==gcd(b,a%b)
LL t = x;
x = y; //x=y'
y = t-a/b*y; //y=x'-[a/b]*y';
return r;
}
LL mod(LL a, LL b){return ((a%b)+b)%b;}
int main(){
ios::sync_with_stdio(false);
int n; cin>>n;
LL a1, m1; cin>>a1>>m1;
for(int i = 2; i <= n; i++){
LL a2, m2; cin>>a2>>m2;
LL k1, k2, d= exgcd(a1,-a2,k1,k2);//求特解
if((m2-m1)%d!=0){cout<<"-1\n"; return 0;}//无解
k1 = mod(k1*(m2-m1)/d, abs(a2/d));//求通解
m1 = k1*a1+m1;//代入循环
a1 = abs(a1/d*a2);//lcm(a1,a2)
}
cout<<m1<<"\n";//最后一遍的解
return 0;
}
- 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
AcWing 883. 高斯消元解线性方程组
//题意：高斯消元求解线性方程组
//首先我们用第一列中（所有的x中）系数最大的来消其他两个式子。我们将这个选中的系数置为1。(由于最多也只能用double型存储，所以必然会有精度误差。但如果我们每次都选用最大系数的来消掉其他系数，就可以最大程度地来减小误差。）
//在置为1之后，我们用这个式子去消其他的式子。那么在最后，我们只需要将这个矩阵的最右下角（也就是最后一个元的实际值）不断回带即可。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 110;
const double eps=1e-7;
int n; double a[maxn][maxn], ans[maxn];
int Gauss(){
int r, c;//当前行和列
for(r=1,c=1; c <= n; c++){//列++
//第c列中系数最大的式子并交换
int t = r;
for(int i=r; i<=n; i++)
if(abs(a[t][c])<abs(a[i][c]))t=i;
if(abs(a[t][c])<eps)continue;//是0就跳过
for(int i=c; i<=n+1; i++)swap(a[t][i],a[r][i]);
//用这个式子去消自己和其他的式子
for(int i=n+1; i>=c; i--)a[r][i]/=a[r][c];
for(int i=r+1; i<=n; i++){
if(abs(a[i][c])>eps)
for(int j=n+1; j>=c; j--)
a[i][j] -= a[i][c]*a[r][j];
}
r++;
}//r==n+1
if(r<=n){
for(int i=r; i<= n; i++)
if(abs(a[i][n+1])>eps)return 2;
return 1;
}
for(int i = n; i >= 1; i--)
for(int j = i+1; j <= n; j++)
a[i][n+1] -= a[j][n+1]*a[i][j];
return 0;
}
int main(){
cin>>n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n+1; j++)
cin>>a[i][j];
int ok = Gauss();
if(ok==0){
for(int i = 1; i <= n; i++)
printf("%.2lf\n",a[i][n+1]);
}else if(ok==1){
printf("Infinite group solutions\n");
}else{
printf("No solution\n");
}
return 0;
}
- 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
AcWing 884. 高斯消元解异或线性方程组
#include <bits/stdc++.h>
using namespace std;
int n, a[220][220];
int Gauss(){
int c, r;
for(c=0,r=0; c < n; c++){
//找主元并交换
int t=-1;
for(int i=r; i < n; i++)
if(a[i][c]){t=i; break;}
if(t==-1)continue;
for(int i=c; i < n+1; i++)swap(a[r][i],a[t][i]);
//消元左下角
for(int i=r+1; i < n; i++)
if(a[i][c])//消掉1
for(int j=n; j >= c; j--)
a[i][j] ^= a[r][j];
r++;
}
if(r<n){
for(int i= r; i < n; i++)
if(a[i][n])return 2;
return 1;
}
for(int i=n-1; i >= 0; i--)
for(int j=i+1; j < n; j++)
if(a[i][j])a[i][n] ^= a[j][n];
return 0;
}
int main(){
cin>>n;
for(int i = 0; i < n; i++)
for(int j = 0; j < n+1; j++)
cin>>a[i][j];
int ok = Gauss();
if(ok==0){
for(int i = 0; i < n; i++)
cout<<a[i][n]<<"\n";
}else if(ok==1){
printf("Multiple sets of solutions\n");
}else{
printf("No solution\n");
}
return 0;
}
- 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
AcWing 885. 求组合数 I
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2e3+10;
const int mod = 1e9+7;
LL C[maxn][maxn];
int main(){
for(int i=0; i <= 2000; i++){
for(int j=0; j <= i; j++){
if(!j)C[i][j] = 1;
else C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
}
int T; cin>>T;
while(T--){
int a,b; cin>>a>>b;
cout<<C[a][b]<<"\n";
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
AcWing 886. 求组合数 II
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
const int mod = 1e9+7;
LL fac[maxn], inv[maxn];
LL mpow(LL a, LL x){
if(x==0)return 1;
LL t = mpow(a, x>>1);
if(x%2==0)return t*t%mod;
return t*t%mod*a%mod;
}
LL init(){
fac[0]=inv[0]=1;
for(int i = 1; i < maxn; i++){
fac[i]=fac[i-1]*i%mod; inv[i]=mpow(fac[i],mod-2);
}return 0;
}
LL C(int x, int y) {
if(y<0 || y>x)return 0;
return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int main(){
init();
int T; cin>>T;
while(T--){
int a,b; cin>>a>>b;
cout<<C(a,b)<<"\n";
}
return 0;
}
- 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
AcWing 887. 求组合数 III
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
const int mod = 1e9+7;
LL mpow(LL a, LL b, LL p){
LL res = 1;
while(b){
if(b&1)res=res*a%p;
a = a*a%p;
b >>= 1;
}
return res;
}
LL C(LL a, LL b, LL p){
LL res = 1; //res*=(j/i), res=res*j*inv[i]
for(int i=1,j=a; i<=b; i++,j--){
res = res*j%p;
res = res*mpow(i,p-2,p)%p;
}
return res%p;
}
LL lucas(LL a, LL b, LL p){
if(a<p && b<p)return C(a,b,p);
return C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}
int main(){
int T; cin>>T;
while(T--){
LL a,b,p; cin>>a>>b>>p;
cout<<lucas(a,b,p)<<"\n";
}
return 0;
}
- 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
AcWing 888. 求组合数 IV
/*求组合数
1.T<1e4,nm<1e3,p=1e9+7
+ 组数较多，考虑预处理。
+ n^2复杂度,可用组合性质C(b,a)=C(b-1,a-1)+C(b,a-1)来推,边界C(i,0)=1
2.T<1e4,nm<1e5,p=1e9+7
+ 组数较多，考虑预处理，因为nm二维空间开不下
+ 所以直接公式C(b,a)=a!b!/(a-b)!=a!*(b!^-1)*((a-b)!^-1), -1为逆元
+ 预处理逆元和阶乘，用费马小定理求阶乘逆元inv[x]=x^(p-2),p为素数
3.T<20,nm<1e18,p=cin
+ 卢卡斯定理：C(b,a)≡C(b%p,a%p)*C(b/p,a/p)(modp)
+ 求C的方法：C(b,a)=a!/(a-b)!*b!=a(a-1)(a-2)*…(a-b+1)/b!,因此可以递推的每次乘a然后除以b,一共b次
4.T=1,nm<5e3,p=1
+ a,b<5000, 不用取模，所以数据很大，需要高精度。
+ 对C(b,a)=a!b!/(a-b)!, 分解质因数得到p1^a1*p2^a2-...pn^an。
+ 对于强行分解质因数：p1,p2,,,pn都是素数，所以可以筛法预处理。a1,a2表示质数p在a中出现的次数，可以枚举得到cnt=a/(p^1)+a/(p^2)+a/(p^3)+…a/(p^k)。
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 5050;
//线性筛
int vis[maxn], primes[maxn], cnt;
void get_primes(int n){
for(int i = 2; i <= n; i++){
if(!vis[i])primes[++cnt]=i;
for(int j = 1; primes[j] <= n/i; j++){
vis[primes[j]*i] = 1;
if(i%primes[j]==0)break;
}
}
}
//高精乘
vector<int>mul(vector<int>a, int b){//0是低位
vector<int>c;
int t = 0;
for(int i = 0; i < a.size(); i++){
t += a[i]*b;
c.push_back(t%10);
t /= 10;
}
while(t){
c.push_back(t%10);
t /= 10;
}
return c;
}
//n!中素数p的个数
int sum[maxn];
int get(int n,int p){
int ans = 0;
while(n){
ans += n/p;
n /= p;
}
return ans;
}
int main(){
int a, b; cin>>a>>b;
//计算C(a,b)中每个素数及出现的次数(分解质因数)
get_primes(a);
for(int i = 1; i <= cnt; i++){
int p = primes[i];
sum[i] = get(a,p)-get(a-b,p)-get(b,p);
}
//ans *= pi^ai
vector<int>ans;
ans.push_back(1);
for(int i = 1; i <= cnt; i++){
for(int j = 1; j <= sum[i]; j++){
ans = mul(ans,primes[i]);
}
}
for(int i = ans.size()-1; i >= 0; i--)
cout<<ans[i];
return 0;
}
- 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
AcWing 889. 满足条件的01序列
//题意：n个0,n个1排成长为2n的序列，满足任意前缀的cnt(0)>cnt(1),求序列个数mod(1e9+7)
//思路：置于坐标轴中，0往右，1往上，当且仅当路径在y=x以下是合法的。那么对于到达(n,n)的不合法路径,必定经过(n+1,n-1),答案减去这些路径。答案是卡特兰数, C(n,2n)/(n+1)。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn = 1e5+10;
const LL mod = 1e9+7;
LL mpow(LL a, LL b, LL p){
LL res = 1;
while(b){
if(b&1)res=res*a%p;
a = a*a%p;
b >>= 1;
}
return res;
}
LL C(LL a, LL b, LL p){
LL res = 1; //res*=(j/i), res=res*j*inv[i]
for(LL i=1,j=a; i<=b; i++,j--){
res = res*j%p;
res = res*mpow(i,p-2,p)%p;
}
return res%p;
}
LL lucas(LL a, LL b, LL p){
if(a<p && b<p)return C(a,b,p);
return C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}
int main(){
LL n; cin>>n;
cout<<lucas(2*n,n,mod)*mpow(n+1,mod-2,mod)%mod<<"\n";
return 0;
}
- 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
AcWing 890. 能被整除的数
//题意：给出整数n个m个素数pi，求1-n中能被pi中至少一个数整除的数的个数,n<1e9,m<16
/*
思路：
+ 显而易见1-n中能被pi整除的数的个数为n/pi，然后容斥原理一下，枚举集合两两间的并集的时候，暴力枚举每一个可能的排列C(m,1)+C(m,1)+C(m,2)+...+C(m,m)次,dfs时每次换一下符号
+ dfs的时候第一个数选(1-n),第二个选(i,n),第k个选(j,n)，随便选几个，包含了所有的可能集合，第一次选就是+，第二次就是-，直接反复。对于并集，把集合中所有数乘起来/n就是集合中能整除的个数
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, m, p[20];
LL ans;
void dfs(int cur, LL sum, int opt){
if(sum > n)return ;
if(cur)ans += n/sum*opt;
opt = -opt;
for(int i=cur+1; i <= m; i++){
dfs(i,sum*p[i],opt);
}
}
int main(){
cin>>n>>m;
for(int i = 1; i <= m; i++)
cin>>p[i];
dfs(0,1,-1);
cout<<ans<<"\n";
return 0;
}
- 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
AcWing 891. Nim游戏
//题意：n堆石头, 两人轮流操作，每次可以从一堆中拿走任意数量，可以拿完但是不能不拿，没石头拿的人输。两人都采取最优策略，求是否先手必胜。
//思路：结论a1^a2^a3^...^an!=0先手必胜，否则先手必败。（先手必胜，先手进行某一个操作，留给后手是一个必败状态。先手必败，先手无论如何操作，留给后手都是一个必胜状态。）
#include<bits/stdc++.h>
using namespace std;
int main(){
int n; cin>>n;
int ans = 0;
for(int i = 1; i <= n; i++){
int x; cin>>x; ans ^= x;
}
if(ans!=0)cout<<"Yes\n";
else cout<<"No\n";
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
AcWing 892. 台阶-Nim游戏
//题意：n级台阶，每级上有ai个石头。两位玩家每次可以从任意级拿任意个放到下一级（不能不拿，拿到地面的不能再拿），无法操作是为失败，求是否先手必胜。
//思路：结论，如果先手时奇数台阶上的值的异或值为1，则先手必胜，反之必败
#include<bits/stdc++.h>
using namespace std;
int main(){
int n; cin>>n;
int ans = 0;
for(int i = 1; i <= n; i++){
int x; cin>>x;
if(i%2==1)ans ^= x;
}
if(ans!=0)cout<<"Yes\n";
else cout<<"No\n";
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
AcWing 893. 集合-Nim游戏
//题意：n堆石头和1个集合S，每次可以从任何一堆拿石子，拿的数量必须包含于S，无法操作为失败，求是否先手必胜。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+10;
int m, s[maxn], f[maxn];
//3.SG函数:有向图游戏G(子游戏)的SG函数值, 被定义为有向图游戏**起点s**的SG函数值，NIM的SG(x)==x
int SG(int x){
if(f[x]!=-1)return f[x];//4.记忆化,f[x]表示x的SG值
set<int>se;
//5.每次可以选择集合中小于x的路径走过去
for(int i = 1; i <= m; i++){
int sum = s[i];
if(x>=sum)se.insert(SG(x-sum));
}
//6.Mex运算:求出不属于集合se的最小非负整数
//7.SG(x)=mex(S),其中S是x后继状态的SG函数值的集合
for(int i = 0; ;i++)
if(!se.count(i))
return f[x]=i;
}
int main(){
cin>>m;
for(int i = 1; i <= m; i++)
cin>>s[i];
int n; cin>>n;
//1.有向图游戏的和:有向图游戏的和的SG函数值, 等于它包含的各个子游戏(各个起点)SG函数的异或和
int ans = 0;
memset(f,-1,sizeof(f));
for(int i = 1; i <= n; i++){
int x; cin>>x; ans^=SG(x);
}
//2.定理：如果SG(G)!=0,则先手必胜,反之必败。
if(ans!=0)cout<<"Yes\n";
else cout<<"No\n";
return 0;
}
- 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
AcWing 894. 拆分-Nim游戏
//题意：n堆石头，每次可以取出一堆，放入两堆规模更小的石头(可以为0)，无法操作为失败，求是否先手必胜。
//思路：相比于NIM，这里的每一堆可以变成不大于原来那堆的任意大小的两堆，相当于一个局面拆分成了两个局面，然后作为局面拆分来处理。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+10;
int n, f[maxn];
int SG(int x){
if(f[x]!=-1)return f[x];
set<int>se;
//1. 局面拆分: 相当于一个局面拆分成了两个局面,由SG函数理论,多个独立局面的SG值,等于这些局面SG值的异或和.
for(int i = 0; i < x; i++)
for(int j = 0; j <= i; j++)//j<=i是避免重复枚举
se.insert(SG(i)^SG(j));
for(int i = 0; ;i++)
if(!se.count(i))
return f[x]=i;
}
int main(){
cin>>n;
int ans = 0;
memset(f,-1,sizeof(f));
for(int i = 1; i <= n; i++){
int x; cin>>x; ans^=SG(x);
}
if(ans!=0)cout<<"Yes\n";
else cout<<"No\n";
return 0;
}
- 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
文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。
原文链接：gwj1314.blog.csdn.net/article/details/115607222
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）