头像

代码人生




离线:7小时前


最近来访(52)
用户头像
dimoo
用户头像
zww
用户头像
Fireflylight
用户头像
图灵机
用户头像
南岸以南南岸哀
用户头像
学C的萌新
用户头像
୧_428
用户头像
magicat
用户头像
宇宙有边
用户头像
pyqyyds
用户头像
倒悬打Treap
用户头像
wby0124
用户头像
hncsxzx
用户头像
不高兴的兽奶
用户头像
这道题有点难耶
用户头像
jianp
用户头像
甜心还不会算法
用户头像
xiayutao
用户头像
noobs
用户头像
Sunburst7


#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 200010, mod = 1e9 + 7;

int n;
int fact[N], infact[N];

int ksm(int a, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = (LL)res * a % mod;
        a = (LL)a * a % mod;
        k >>= 1;
    }
    return res;
}

void init() {
    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] * ksm(i, mod - 2) % mod;
    }
}

int main() {
    init();
    cin >> n;
    int res = (LL)fact[2 * n] * infact[n] % mod * infact[n] % mod * ksm(n + 1, mod - 2) % mod;
    cout << res << endl;
    return 0;
}



小学奥数

众所周知,拆数使乘积最大有这样一个原则:多拆3,少拆2,不拆1

class Solution {
public:
    int maxProductAfterCutting(int n) {
        if(n == 2) return 1;
        if(n == 3) return 2;
        if(n % 3 == 0){
            return pow(3,n/3);
        }
        if(n % 3 == 1){
            return pow(3,n/3-1) * 4;
        }
        if(n % 3 == 2){
            return pow(3,n/3) * 2;
        }
    }
};


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

#include <iostream>
#include <vector>
using namespace std;
const int N = 5010;
int primes[N],cnt;
bool st[N];
int sum[N];
int a,b;
void Euler_prime(int n){
    for(int i=2;i<=n;i++){
        if(!st[i]) primes[++cnt] = i;
        for(int j=1;primes[j] <= n / i;j++){
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}
int get(int n,int p){
    /*
    define floor下取整
    包含总数 = floor(n/p) + floor(n/p^2) + floor(n/p^3) ...
    */
    int res = 0;
    while(n){
        res += n / p;
        n /= p;
    }
    return res;
}
vector<int> mul(vector<int> a,int b){
    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;
}
int main(){
    scanf("%d %d",&a,&b);
    Euler_prime(a);
    for(int i=1;i<=cnt;i++){
        int p = primes[i];
        sum[i] = get(a,p) - get(b,p) - get(a-b,p);
        /*
        根据组合数原始公式:
        a中包含的p的个数-b中包含的p的个数-(a-b)中包含的p的个数
        */ 
    }
    vector<int> res;
    res.push_back(1);
    for(int i=1;i<=cnt;i++){
        for(int j=0;j<sum[i];j++){
            res = mul(res,primes[i]);
        }
    }
    for(int i=res.size()-1;i>=0;i--) printf("%d",res[i]);
    puts("");
    return 0;
}


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

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int p;
int qmi(int a,int b){
    int res = 1;
    while(b){
        if(b & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        b >>= 1;
    }
    return res;
}
int C(int a,int b){
    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;
    }
    return res;
}
int lucas(LL a,LL b){
    if(a < p && b < p) return C(a,b);
    else return (LL)C(a % p,b % p) * lucas(a / p,b / p) % p;
}
int main(){
    int n;
    cin >> n;
    while(n -- ){
        LL a,b;
        cin >> a >> b >> p;
        cout << lucas(a,b) << endl;
    }
    return 0;
}


活动打卡代码 AcWing 4724. 靓号

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

int n, m;
string str;
int min_cost = 1e8;
string ans;

void work(char x)
{
    string s = str;
    vector<int> p[19];
    for (int i = 0; i < n; i ++ )
        p[s[i] - x + 9].push_back(i);

    int cnt = 0, cost = 0;
    for (int k = 0; cnt < m; k ++ )
    {
        for (int i = 0; i < p[9 + k].size() && cnt < m; i ++ )
        {
            cnt ++ ;
            cost += k;
            s[p[9 + k][i]] = x;
        }

        if (k)
        {
            for (int i = p[9 - k].size() - 1; i >= 0 && cnt < m; i -- )
            {
                cnt ++ ;
                cost += k;
                s[p[9 - k][i]] = x;
            }
        }
    }

    if (cost < min_cost || cost == min_cost && s < ans)
    {
        min_cost = cost;
        ans = s;
    }
}

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

    for (int i = 0; i < 10; i ++ )
        work(i + '0');

    cout << min_cost << endl;
    cout << ans << endl;

    return 0;
}


活动打卡代码 AcWing 4723. 队列

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
//数学方法
int main()
{
    cin >> n;
    int s = 0,k = 5;
    while(s + k < n){
        s += k;
        k *= 2;
    }
    n -= s;
    int len = k / 5;
    int t = (n + len - 1) / len;
    cout << (char)(t - 1 + 'a');
    return 0;
}



#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
//数学方法
int main()
{
    cin >> n;
    int s = 0,k = 5;
    while(s + k < n){
        s += k;
        k *= 2;
    }
    n -= s;
    int len = k / 5;
    int t = (n + len - 1) / len;
    cout << (char)(t - 1 + 'a');
    return 0;
}


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

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 100010,mod = 1e9 + 7;
int fact[N],infact[N];
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 main(){
    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;
    }
    int n;
    scanf("%d",&n);
    while(n -- ){
        int a,b;
        scanf("%d %d",&a,&b);
        printf("%d\n",(LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
    }
    return 0;
}


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

#include <iostream>
using namespace std;
/*
C(a,b)表示从a个里选b个
C(a,b) = C(a-1,b) + C(a-1,b-1)
C(a-1,b)为不选,C(a-1,b-1)为选
两种情况相加
*/
const int N = 2010,mod = 1e9 + 7;
int c[N][N];
void combination(){
    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] + c[i-1][j-1]) % mod;
        }
    }
}
int main(){
    combination();
    int n;
    scanf("%d",&n);
    while(n -- ){
        int a,b;
        scanf("%d %d",&a,&b);
        printf("%d\n",c[a][b]);
    }
    return 0;
}



#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 105;
const double eps = 1e-6;
int n;
double a[N][N];
/*
高斯消元
枚举每一列c:
1.找到绝对值最大的一行
2.将该行移到当前的最上面
3.将该行第一个数变成1
4.将下面所有行的第c列改成0
*/
int gauss(){
    int c,r;
    for(c = 0,r = 0;c < n;c++){
        int t = r;
        for(int i=r;i<n;i++){
            if(fabs(a[i][c]) > fabs(a[t][c])){
                t = i;
            }
        }
        if(fabs(a[t][c]) < eps) continue;
        for(int i=c;i<=n;i++) swap(a[t][i],a[r][i]);
        for(int i=n;i>=c;i--) a[r][i] /= a[r][c];
        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];
                }
            }
        }
        r++;
    }
    if(r < n){
        for(int i=r;i<n;i++){
            if(fabs(a[i][n]) > eps){
                return 2;
            }
        }
        return 1;
    }
    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];
        }
    }
    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 = gauss();
    if(t == 0){
        for(int i=0;i<n;i++){
            if(fabs(a[i][n]) < eps) a[i][n] = 0;
            printf("%.2lf\n",a[i][n]);
        }
    }
    else if(t == 1) puts("Infinite group solutions");
    else puts("No solution");
    return 0;
}