C++(g++ 7.5.0) 解法, 执行用时: 11ms, 内存消耗: 604K, 提交时间: 2022-08-09 23:53:12

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 100010;
int a[N], b[N];
int primes[N], cnt;
bool st[N];

void get_prime(int n) {
    for (int i = 2; i <= n; i++) {
        if(!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] * i <= n; j++) {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int get(int n, int p) {
    int s = 0;
    while (n) {
        s += n / p;
        n /= p;
    }
    return s;
}

void mul(int a[], int b, int &len) {
    int t = 0;
    for (int i = 1; i <= len; i++) {
        t += a[i] * b;
        a[i] = t % 10;
        t /= 10;
    }
    while (t) {
        a[++len] = t % 10;
        t /= 10;
    }
}

void sub(int a[], int b[], int &len) {
    for (int i = 1, t = 0; i <= len; i++) {
        a[i] -= t + b[i];
        if(a[i] < 0) {
            a[i] += 10, t = 1;
        } else {
            t = 0;
        }
    }
    while (len > 1 && !a[len]) len--;
}

int C(int n, int m, int c[]) {
    c[1] = 1;
    int len = 1;

    for (int i = 0; i < cnt; i++) {
        int p = primes[i];
        int s = get(n, p) - get(m, p) - get(n - m, p);
        while (s--) mul(c, p, len);
    }

    return len;
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    get_prime(N - 1);
    
    int n, m;
    cin >> n >> m;
    int al = C(n + m, m, a);
    int bl = C(n + m, n + 1, b);

    sub(a, b, al);

    for (int i = al; i >= 1; i--) {
        cout << a[i];
    }

    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 12ms, 内存消耗: 476K, 提交时间: 2020-10-15 21:02:23

#include<bits/stdc++.h>
#define hh ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i )
#define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i )
int N, M;
int a[1000005], na, b[1000005], nb;
int s[10005];
void Mul(int* a, int& n, int x) {
    fp(i, 1, n) a[i] *= x;
    fp(i, 1, n) {
        a[i + 1] += a[i] / 10;
        a[i] %= 10;
    } while (a[n + 1]) ++n, a[n + 1] += a[n] / 10, a[n] %= 10;
}
void C(int* a, int& n, int x, int y) {
    memset(s, 0, sizeof s);
    fp(i, y + 1, x) ++s[i];
    fp(i, 1, x - y) --s[i];
    fd(i, x, 2) {
        int t(i);
        for (int j = 2; j * j <= t; ++j)
            while (t % j == 0) s[j] += s[i], t /= j;
        if (t == i) while (s[i]--) Mul(a, n, i);
        else if (t > 1) s[t] += s[i];
    }
}
int main() {
    hh
    cin >> N >> M;
    a[na = 1] = b[nb = 1] = 1;
    C(a, na, N + M, M);
    C(b, nb, N + M, M - 1);
    fp(i, 1, na) {
        a[i] -= b[i];
        if (a[i] < 0) a[i] += 10, --a[i + 1];
    } while (!a[na]) --na;
    fd(i, na, 1) printf("%d", a[i]); printf("\n");
    return 0;
}

Java 解法, 执行用时: 449ms, 内存消耗: 15352K, 提交时间: 2022-12-09 16:08:23

import javax.swing.*;
import java.io.*;
import java.math.BigInteger;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {
    static BigInteger func(BigInteger a,BigInteger b){
        BigInteger s = new BigInteger("1");
        BigInteger i = a,j = new BigInteger("1");
        for(;j.compareTo(b)<=0;s=s.multiply(i),j=j.add(new BigInteger("1")),
                i=i.subtract(new BigInteger("1")));
        for(;new BigInteger("0").compareTo(b)<0;s=s.divide(b),
                b=b.subtract(new BigInteger("1")));
        return s;
    }
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        BigInteger a = sc.nextBigInteger(),b = sc.nextBigInteger();
        System.out.println(func(a.add(b),b).subtract(func(a.add(b)
                ,b.subtract(new BigInteger("1")))));
    }
}

Python3 解法, 执行用时: 171ms, 内存消耗: 6860K, 提交时间: 2021-06-05 22:56:30

def f(a,b):
    s=1
    i=a
    j=1
    while j<=b:
        s*=i
        j+=1
        i-=1
    while b>0:
        s//=b
        b-=1
    return s
n,m=map(int,input().split(' '))
print((f(n+m,m)-f(n+m,m-1)))