头像

kylinn


访客:388

离线:5小时前


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

kylinn
14天前
#include <iostream>
#define ll long long
using namespace std;
const int N = 1e5+5,mod= 1e9+7;
int a,b,t;
ll c[N], inv[N];

ll qpow(ll a,int b){
    ll ans = 1;
    while(b){
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

int main(){
    cin >> t;

    //  求排列数
    c[0] = 1;
    for(int i=1;i<=N;i++) c[i] = c[i-1] * i % mod;
    //  求排列数的逆元
    inv[N-1] = qpow(c[N-1], mod - 2);
    for(int i = N-2;i >= 0;i--)
        inv[i] = inv[i + 1] * (i + 1) % mod;

    while(t--){
        cin >> a >> b;
        cout << c[a] * inv[b] % mod * inv[a-b] % mod << "\n";
        //  逆元使用:
        //  a / b == a * b^(p-2) % mod;
    }
    return 0;
}


活动打卡代码 AcWing 876. 快速幂求逆元

kylinn
14天前
#include <iostream>
using namespace std;
#define ll long long
int t,b,p;
ll gcd(ll b, ll m){
    return !m ? b : gcd(m, b%m);
}

ll qpow(int a,int b,int p){
    ll ans = 1;
    while(b){
        if(b&1) ans = (ll)ans* a % p;
        a = (ll)a * a % p;
        b >>= 1;
    }
    return ans;
}

int main(){
    cin >> t;
    while(t--){
        cin >> b >> p;
        //if(b % p == 0) cout << "impossible\n";
        if(gcd(b,p)!=1)cout << "impossible\n";
        else cout << qpow(b, p-2, p) << "\n";
    }
}


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

kylinn
14天前
#include <iostream>
#define ll long long
using namespace std;
const int N = 1e5+5,mod= 1e9+7;
int a,b,t;
ll c[N], inv[N];

ll qpow(ll a,int b){
    ll ans = 1;
    while(b){
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

int main(){
    cin >> t;

    //  求排列数
    c[0] = 1;
    for(int i=1;i<=N;i++) c[i] = c[i-1] * i % mod;
    //  求排列数的逆元
    inv[N-1] = qpow(c[N-1], mod - 2);
    for(int i = N-2;i >= 0;i--)
        inv[i] = inv[i + 1] * (i + 1) % mod;

    while(t--){
        cin >> a >> b;
        cout << c[a] * inv[b] % mod * inv[a-b] % mod << "\n";
        //  逆元使用:
        //  a / b == a * b^(p-2) % mod;
    }
    return 0;
}



kylinn
14天前

组合数的逆元写法

看别人的没看明白,顺着自己思路写了一下
其实也没什么好讲的,就是公式的写法,打表了 n!,还有对应的逆元inv。

组合的公式: $C^m_n = \frac{n!}{ m!(n-m)!}$
之后把分母换成对应的inv就行了

#include <iostream>
#define ll long long
using namespace std;
const int N = 1e5+5,mod= 1e9+7;
int a,b,t;
ll c[N], inv[N];

ll qpow(ll a,int b){
    ll ans = 1;
    while(b){
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

int main(){
    cin >> t;

    //  求排列数
    c[0] = 1;
    for(int i=1;i<=N;i++) c[i] = c[i-1] * i % mod;
    //  求排列数的逆元
    //  b的逆元就是 b^(mod-2)
    inv[N-1] = qpow(c[N-1], mod - 2);
    for(int i = N-2;i >= 0;i--)
        inv[i] = inv[i + 1] * (i + 1) % mod;

    while(t--){
        cin >> a >> b;
        cout << c[a] * inv[b] % mod * inv[a-b] % mod << "\n";
        //  逆元使用:
        //  a / b  % mod == a * inv[b] % mod;
        //  直接替换了就行
    }
    return 0;
}


活动打卡代码 AcWing 867. 分解质因数

kylinn
14天前
#include <iostream>
#include <map>

using namespace std;
int t,n;

void f(int n){
    map<int, int > p;
    for(int i = 2;i <= n / i; i++){
        while(n % i == 0){
            p[i]++;
            n /= i;
        }
    }
    if(n!=1)p[n]++;

    for(auto a:p)
        cout << a.first << " " << a.second;
}


int main(){
    cin >> t;
    while(t--){
        cin >> n;
        f(n);
        cout << "\n\n";
    }

}


活动打卡代码 AcWing 875. 快速幂

kylinn
14天前
#include <iostream>
using namespace std;
#define ll long long

ll a,b,p;

void qpow(ll a,ll b,ll p){
    ll ans = 1;

    while(b){
        if(b&1){
            ans = (a * ans) % p;       
        }
        a = (a * a) % p; 
        b >>= 1;
    }
    cout << ans << endl;

}
int t;
int main(){
    cin >> t;
    while(t--){
        cin >> a >> b >> p;
        qpow(a,b,p);
    }

}



kylinn
17天前
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int t,n;
int main(){
    cin >> t;
    while(t--){
        cin >> n;
        bool f = 0;
        if(n!=2&&n%2==0||n==1){
            cout << "No\n" ;continue;
        }
        for(int i=3;i<=(int)sqrt(n);i+=2)
            if(n%i==0)f = 1;
        cout << (f? "No\n":"Yes\n"); 

    }
    return 0;
}


活动打卡代码 AcWing 869. 试除法求约数

kylinn
17天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <list>
#include <stack>
#include <vector>
using namespace std;
#define ll long long
typedef long double ld;
#define INF 0x3f3f3f3f
#define ms(a, b) memset((a), (b), sizeof (a))

const int N = 2e5+5;
int a[N];

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

    while(t--){
        cin >> n;
        int R = 0;
        int L = (int)sqrt(n);
        for(int i=1;i<=L;i++)
            if(n%i==0){
                cout << i << " ";
                if(i!=n/i)
                    a[R++] = n / i;
            }
        for(int i=R-1;i>=0;i--){
            cout << a[i] << " ";
        }
        cout << "\n";
    }
}



活动打卡代码 AcWing 868. 筛质数

kylinn
1个月前
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e6+6;
int a[N],n;

int prime(int n){
    int res=0;
    memset(a,0,sizeof a);
    for(int i=2;i<=n;i++){
        if(a[i]!=0)continue;
        res++;
        for(int j=i*2;j<=n;j+=i)
            a[j] = 1;
    }
    return res;
}
int main(){
    scanf("%d",&n);
    int ans = prime(n);
    printf("%d",ans);
}



kylinn
1个月前
#include <iostream>
using namespace std;
const int N = 1e3+3;
int n,a[N],dp[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",a+i);

    for(int i=1;i<=n;i++){
        dp[i] = 1;
        for(int j=1;j<i;j++){
            if(a[j]<a[i])dp[i] = max(dp[i],dp[j]+1);
        }
    }
    int ans = dp[1];
    for(int i=1;i<=n;i++)ans = max(ans,dp[i]);
    printf("%d\n",ans);
    //O(n^2)的写法,还有logn的

}