class Solution {
    public int[] sortedSquares(int[] nums) {
        for(int i = 0; i < nums.length; i ++){
            nums[i]=nums[i]*nums[i];
        }
        Arrays.sort(nums);
        return nums;
    }
}

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int n = nums.length ;
        int [] sum = new int [n + 1] ;
        for (int i = 1;  i <= n ; ++i) {
            sum[i] = (sum[i - 1] + nums[i - 1])  ;
        }
        HashMap<Integer,Integer> hash = new HashMap<>();
        hash.put(0, 1) ;
        int res = 0 ;
        for (int i = 1 ;i <= n ; ++i) {
            sum[i] = (sum[i] % k + k ) % k ;                          
        }

        for (int i = 1 ; i <= n ; ++i) {
            int t = sum[i] % k ;
            if (hash.containsKey(t)) {
                res += hash.get(t) ;
            }            
            int cnt = hash.getOrDefault(sum[i] % k ,0) + 1 ;
            hash.put(sum[i] % k , cnt) ;
        }
        return res;
    }
}

class Solution {
    public int repeatedNTimes(int[] nums) {
        Map<Integer,Integer> map = new HashMap();
        for(int i = 0; i < nums.length; i ++){
            if(map.containsKey(nums[i])==false){
                map.put(nums[i],1);
            }else{
                map.put(nums[i],map.get(nums[i])+1);
            }
        }
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(entry.getValue()==nums.length/2){
                return entry.getKey();
            }
        }
        return -1;
    }
}

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        List<Integer> res = new ArrayList<Integer>();
        int n = num.length;
        for (int i = n - 1; i >= 0; --i) {
            int sum = num[i] + k % 10;
            k /= 10;
            if (sum >= 10) {
                k++;
                sum -= 10;
            }
            res.add(sum);
        }
        for (; k > 0; k /= 10) {
            res.add(k % 10);
        }
        Collections.reverse(res);
        return res;
    }
}

class Solution {
    public int[] sumEvenAfterQueries(int[] nums, int[][] queries) {
        int[] ans = new int[10010];
        for(int i = 0; i < queries.length; i ++){
            int val = queries[i][0];
            int idx = queries[i][1];
            nums[idx]+=val;
            int tot = 0;
            for(int j = 0; j < nums.length; j ++){
                if((nums[j]&1)==0) tot += nums[j];
            }
            ans[i] = tot;
        }
        return Arrays.copyOfRange(ans,0,nums.length);
    }
}

class Solution {
    public String strWithout3a3b(int a, int b) {
        StringBuilder ans = new StringBuilder();
        if(a >= b){
            while(a > 0 || b > 0){
                if(a > b){
                     ans.append("aab");
                     a-=2;b--;
                }
                else{
                     ans.append("ab");
                     a--;b--;
                }
            }
        }else{
            while(a > 0 || b > 0){
                if(b > a){
                    ans.append("bba");
                    b-=2;a--;
                } 
                else{
                    ans.append("ba");
                    a--;b--;
                } 
            }
        }
        return ans.substring(0,ans.length()-Math.abs(a+b));
    }
}

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        Map<Integer,Integer> map = new HashMap<>();
        int[] a = new int[200010];
        int t = sc.nextInt();
        while(t-->0){
            int n = sc.nextInt();
            for(int i = 1; i <= n; i ++){
                a[i]=sc.nextInt();
                if(map.containsKey(a[i])==false) map.put(a[i],1);
                else map.put(a[i],map.get(a[i])+1);
            }
            int Min=0x3f3f3f3f,idx=0;
            for(int i = 1; i <= n; i ++){
                if(map.get(a[i])==1&&a[i]<Min){
                    Min = a[i];
                    idx = i;
                }
            }
            if(Min==0x3f3f3f3f) System.out.println(-1);
            else System.out.println(idx);
            map.clear();
        }
    }
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 45000, M = 50;
int primes[N], cnt;
bool st[N];
PII factor[M];
int cntf;
int divider[N], cntd;

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

inline int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

void dfs(int u, int p)
{
    if (u > cntf)
    {
        divider[cntd ++ ] = p;
        return;
    }
    for (int i = 0; i <= factor[u].second; i ++ )
    {
        dfs(u + 1, p);
        p *= factor[u].first;
    }
}

int main()
{
    get_primes(N);

    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int a0, a1, b0, b1;
        scanf("%d%d%d%d", &a0, &a1, &b0, &b1);
        int d = b1;
        cntf = 0;
        for (int i = 0; primes[i] <= d / primes[i]; i ++ )
        {
            int p = primes[i];
            if (d % p == 0)
            {
                int s = 0;
                while (d % p == 0) s ++, d /= p;
                factor[ ++ cntf] = {p, s};
            }
        }
        if (d > 1) factor[ ++ cntf] = {d, 1};

        cntd = 0;
        dfs(1, 1);

        int res = 0;
        for (int i = 0; i < cntd; i ++ )
        {
            int x = divider[i];
            if (gcd(x, a0) == a1 && (LL)x * b0 / gcd(x, b0) == b1)
            {
                res ++ ;
            }
        }
        printf("%d\n", res);
    }
    return 0;
}

卡特兰数

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010, mod = 1e9 + 7;
int n;
int fact[N], infact[N];
typedef long long LL;

int qmi(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] * qmi(i, mod - 2) % mod;
    }
}

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

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010,mod = 1e9+7;
typedef long long LL;
int fact[N],infact[N];//阶乘，阶乘逆元

int qmi(int a, int k, int p)  // 求a^k mod 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;
    int n;cin>>n;
    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;
        scanf("%d%d",&a,&b);
        int res = (LL)((LL)fact[a]*infact[b]%mod)*infact[a-b]%mod;
        cout<<res<<endl;
    }

    return 0;
}