头像

zhangxuming




离线:31分钟前


最近来访(48)
用户头像
MangataTS
用户头像
usingnamespace
用户头像
tsrigo
用户头像
翩竹
用户头像
jimmy2021
用户头像
求求了不要WA
用户头像
Milchstraße_2
用户头像
DPH
用户头像
VegeDog
用户头像
Tequila
用户头像
ballyang
用户头像
zhanzejian
用户头像
ggins
用户头像
RyanMoriarty
用户头像
Oier12138
用户头像
坠落的余晖
用户头像
曙阳
用户头像
13569840960
用户头像
WangShuo
用户头像
ホ追逐繁星的孩子

活动打卡代码 AcWing 888. 求组合数 IV

组合数4(时间复杂度暂不明确,为高精度数)

超出int用这个(不模数的时候)

用到了一个结论:!n中,质因数的个数=n/p+n/p^2+....。

注意如果直接用分解质因数的方法会超时。

#include<iostream>
#include<vector>
using namespace std;
const int N =5e3+10;
int prime[N],cnt;
bool st[N];
int sum[N];
void get_prime(int x){
    for(int i=2;i<=x;i++){//线性筛筛质因数
        if(!st[i])prime[cnt++]=i;
        for(int j =0;prime[j]*i<=x;j++){
            st[prime[j]*i]=true;
            if(i%prime[j]==0)break;
        }
    }
}
int get(int a,int p){//求质因数p的个数
    int res =0;
    while(a){
        res+=a/p;
        a/=p;
    }
    return res;
}
vector<int> mul(vector<int>&a,int p){
    vector<int> c;
    int t =0;
    for(int i=0;i<a.size();i++){
        t+=a[i]*p;
        c.push_back(t%10);
        t/=10;
    }
    while(t){
        c.push_back(t%10);
        t/=10;
    }
    return c;
}
int main(){

    int a,b;
    cin>>a>>b;
     get_prime(a);
     for(int i =0;i<cnt;i++){
         sum[i]=get(a,prime[i])-get(a-b,prime[i])-get(b,prime[i]);
     }
     vector<int>res;
     res.push_back(1);
    for(int i =0;i<cnt;i++)
        for(int j =0;j<sum[i];j++){
            res=mul(res,prime[i]);
        }
    for(int i =res.size()-1;i>=0;i--){
        cout<<res[i];
    }

    return 0;
}


活动打卡代码 AcWing 887. 求组合数 III

求组合数3(对于每一个所求的数,时间复杂度是plogpNlogp,因为logpN和logp不可能同时取得最大,所以近似为p*logpN,p是阶乘处的复杂度,logpN是lucas处)

Lucas定理:对于非负整数a,b,质数p,有Cab%p=Ca/pb/p*Ca%pb%p %p(即同余于)

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;


int qmi(int a, int k, int p)//快速幂求质数的逆元
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}


int C(int a, int b, int p)//直接利用组合数定义求组合数
{
    if (b > a) return 0;//注意特判为0情况

    int res = 1;
    for (int i = 1, j = a; i <= b; i ++, j -- )
    {
        res = (LL)res * j % p;
        res = (LL)res * qmi(i, p - 2, p) % p;
    }
    return res;
}


int lucas(LL a, LL b, int p)
{
    if (a < p && b < p) return C(a, b, p);//当a和b小于p,必然存在逆元
    return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;//否则一直递归,直到if成立
}


int main()
{
    int n;
    cin >> n;

    while (n -- )
    {
        LL a, b;
        int p;
        cin >> a >> b >> p;
        cout << lucas(a, b, p) << endl;
    }

    return 0;
}




活动打卡代码 AcWing 886. 求组合数 II

组合数:用阶乘求。(Nlogmod)N为a,b范围,mod为给出的模数。

#include<iostream>
using namespace std;
const int N=1e5+10;
const int mod =1e9+7;
int fact[N],infact[N];
typedef long long LL;
int qmi(int a,int b,int p){
    int res=1;
    while(b){
        if(b&1)res=(LL)res*a%mod;
        a=(LL)a*a%mod;
        b>>=1;
    }
    return res;
}
int main(){
    int n;
    cin>>n;
    fact[0]=infact[0]=1;
    for(int i=1;i<=N;i++){
        fact[i]=(LL)fact[i-1]*i%mod;
        infact[i]=(LL)infact[i-1]*qmi(i,mod-2,mod)%mod;

    }
    while(n--){
        int a,b;
        cin>>a>>b;
        cout<<(LL)fact[a]*infact[a-b]%mod*infact[b]%mod<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 885. 求组合数 I

复杂度n^2

利用公式Cab=Ca-1b-1+Ca-1b;在a,b很小的时候用

#include<iostream>
using namespace std;
const int N =2e3+10;
int c[N][N];
const int mod =1e9+7;
void init(){

    for(int i=0;i<N;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 main(){
    int n;
    cin>>n;
    init();
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        cout<<c[a][b]<<endl;
    }



    return 0;
}



题目在链接

dfs

把握关键要素:1.递归出口 2. 递归函数所要解决的子问题

#include<iostream>
#include<cmath>
using namespace std;
const int N = 10;
int s[N];
int n;
double res;
void dfs(int d,int x ,int y ,int z) {//解决的子问题:每一边为它加上或者不加数
    if (d >= n) {
        double p = (double)(x + y + z) / 2;
        if (p - x > 0 && p - y > 0 && p - z > 0)
        {
            res = max(res, sqrt(p * (p - x) * (p - y) * (p - z)));//海伦公式
        }
        return ;
    }

        dfs(d + 1, x + s[d], y, z);//x加上s【d】木棍
        dfs(d + 1, x, y + s[d], z);
        dfs(d + 1, x, y, z + s[d]);
        dfs(d + 1, x, y, z);//不加木棍
}
int main() {

    cin >> n;
    dfs(0,0,0,0);
    printf("%.2f", res);


    return 0;
}






对拍程序模板

屏幕截图 2022-01-14 164411.png

注意对拍程序不能用cin.tie(0)加速,坑掉了我一个下午QAQ




如题

高斯消元步骤:枚举列,1.找到该列最大数所在的行,2.把该行移到上面(不是最上面),3.把该列系数化为1,

4.把下面每一行的该列变成0.5.最后再从最下面一列开始,回带xi。

#include<iostream>
#include<cmath>
using namespace std;
const int  N = 1e3;
const double  eps = 1e-8;
double a[N][N];
int n;
int gause()
{
    int c, r;
    for (r = 0, c = 0; c < n; c++)
    {
        int t = r;
        for (int i = r; i < n; i++)
            if (fabs(a[t][c]) <fabs(a[i][c]) )//绝对值最大的一行
                t = i;
        if (fabs(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; i >= c; i--)
            a[r][i] /= a[r][c];//系数化为1
        for (int i = r + 1; i < n; i++)
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; j--)
                    a[i][j] -= a[r][j] * a[i][c];//把下面每一行的该列变为0
        r++;
    }

    if (r < n)//出现过一列全为0的情况
    {
        for (int i = r; i < n; i++)//注意:从r开始的行,一定是所有项都被消除,否则无解。
            if (fabs(a[i][n]) > eps)//出现一个数=0的情况
                return 1;//无解
        return 2;//有无数个解

    }
    for (int i = n - 1; i >= 0; i--)
        for (int j = i + 1; j < n; j++)
        {
            a[i][n] -= a[i][j] * a[j][n];//从最底下开始,每一行减去前n项,余下的就是该行所表示的x。

        }

    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 t = gause();
    if (t == 1)cout << "No solution";
    else if (t == 2)cout << "Infinite group solutions";
    else {
        for (int i = 0; i < n; i++)
        {
            if (fabs(a[i][n]) < eps)cout << "0.00" << endl;//由于精度问题,可能出现-0.00的情况。这一步舍去这种情况。
            else printf("%.2f\n", a[i][n]);
        }

    }

}



中国剩余定理+扩展中国剩余定理

求x,使得x模ai同余于mi。(i从1~n),即解该方程组。中国剩余定理:要求m之间两两互质;拓展;不要求m之间两两互质。

中国剩余定理:令Ai=(a1a2an)/ai,Ai^-1为Ai%ai的逆元,则x=m1A1A1^-1+....+mnAn*An^-1.

拓展中国剩余定理:原式可以写成:x=aiki+mi(i从1~n),第一二项把x消掉,就成了k1a1-k2a2=m2-m1,再用exgcd求出k1.如果k1不存在,那么无解。然后x=k1a1+m1;k1可以写成k1+k*a2/d,即x=ka1a2/d+k1a1+m1,即x=x0+ka的形式,继续往下做就是答案

本题条件:答案在long long范围内(所以全开long long);

本题要求:答案为最小非负整数。

#include<iostream>
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;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;

}
int main() {
    int n;
    cin >> n;
    LL a1, m1;
    cin >> a1 >> m1;
    LL x = 0;
    for (int i = 0; i < n - 1; i++) {
        LL a2, m2;
        LL k1, k2;
        cin >> a2 >> m2;
        LL d = exgcd(a1, a2, k1, k2);
        if ((m2 - m1) % d)
        {
            x = -1;
            break;
        }
        else {
            k1 *= (m2 - m1) / d;
            k1 = (k1 % (a2 / d) + a2 / d) % (a2 / d);//把k1限制在a2/d的范围内,防止溢出
            m1 = k1 * a1 + m1;
            a1 = abs(a1 / d * a2);//abs可不加

        }


    }
    if (x == -1)cout << x;
    else cout << (m1 % a1 + a1) % a1;//最后即求x模a1同余于m1了,而所求x为最小非负整数,最小,所以取模;非负,所以这样算。这样算是取余运算,余数只能为正数。而直接m1%a1是取模运算,结果可能为负数(c++中)




    return 0;
}


活动打卡代码 AcWing 878. 线性同余方程

线性同余方程

给定a,b,m,求x使得ax同余于b,即(ax-b)%m==0,记作a=(三杠)b(modm)。这个方程等价于:ax=b+my,这种形式就和拓展欧几里得算法很像了。再把my移项,让y=-y得到ax+my=b。而若式子成立。b就一定是a%b的倍数。所以用拓展欧几里得算出x0,再乘以相应的倍数,就是答案了。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int exgcd(int a, int b, int& x, int& y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a%b, y, x);
    y -= a / b * x;

    return d;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int  n;
    cin >> n;
    while (n--) {

        int a, b, m;
        cin >> a >> b >> m;
        int x, y;
        int d = exgcd(a, m, x, y);
        if (!(b % d))cout << (long long )x*b/d%m << endl;
        else cout << "impossible" << endl;
    }





    return 0;
 }



拓展欧几里得算法:给定a,b,求x,y满足ax+by=(a,b)。(欧几里得算法时间复杂度:logb)

根据by+(a%b)x=d(此时已经交换过),且a%b=a-a/b*b,把式子化为带a与b的两项,对照求得两个式子xy关系,然后递归解决

并且,x与y有无限组解。在用拓展欧几里得算法求得一组特解后,y=y0+a/dk,x=x0-b/dk,k为非零整数。

#include <iostream>
#include <algorithm>

using namespace std;

int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1, y = 0;//边界条件:当b=0时,a=d,所以x=1,y=0。(y可以取任何数,习惯上取0,为一组解)
        return a;
    }
    int d = exgcd(b, a % b, y, x);//反着传,这样x就不用变了。也可正着传,但代码没这个简洁
    y -= a / b * x;
    return d;
}

int main()
{
    int n;
    scanf("%d", &n);

    while (n -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        int x, y;
        exgcd(a, b, x, y);
        printf("%d %d\n", x, y);
    }

    return 0;
}