数学

青蛙旅行
卡特兰数
https://ac.nowcoder.com/acm/contest/8417/I
对于n个数的序列，其出战方案数多少种，设为H(n)。如果序列中第k个数是最后一个出栈的，则k进栈前，其前（k-1）个元素均已出栈，前(k-1)个元素出栈的序列有H(k-1)种，第k个数出栈前，其后(n-k)个元素均已出栈，它们的出栈方案数有H(n-k)种。则第k个元素为最后一个出栈元素对应的出栈方案数为H(k-1)H(n-k)，k又可以取遍1~n，所以可得。H(n) = H(0)H(n-1)+H(1)H(n-2)...H(n-1)H(1)H(n-1)H(0);题目要求第一个进栈的元素，不能第一个出，则在H(n)种方案中，只有A1进A1出和剩余n-1个元素入栈出栈的情况组合是不符合要求的。则答案就是H(n)-H(n-1).H(n)还有这种表方法：H(n) = C(2n,n)/(n+1);由于该题目牵涉到除法，所以还需要求乘法逆元，题目给出的模是素数，则可以用小费马定理求乘法逆元。

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
const int N=1e6+5;
const int mod=998244353;
using namespace std;
ll f[N];
void inif(){
    f[0]=1;
    f[1]=1;
    for(int i=2;i<N;i++){
        f[i]=f[i-1]*i%mod;
    }
}
ll pw(ll x,ll p){
    x=x%mod;
    ll ans=1;
    while(p>0){
        if(p&1)ans=ans*x%mod;
        x=x*x%mod;
        p>>=1;
    }
    return ans;
}
ll catelan(int n){
    ll p1=pw(f[n]*f[n]%mod,mod-2);//组合数不是排列
    ll p2=pw(n+1,mod-2);
    return f[2*n]*p1%mod*p2%mod;
}
int main()
{
    ios;
    inif();
    int t;
    int Case=1;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int t=n-1;
        ll h1=(catelan(n)-catelan(n-1)+mod)%mod;
        printf("Case #%d: %lld\n",Case++,h1);
    }
}

洛谷p2241
https://www.luogu.com.cn/problem/P2241
题目背景
1997年普及组第一题

题目描述
有一个 n \times mn×m 方格的棋盘，求其方格包含多少正方形、长方形（不包含正方形）。

输入格式
一行，两个正整数 n,mn,m（n \leq 5000,m \leq 5000n≤5000,m≤5000）。

输出格式
一行，两个正整数，分别表示方格包含多少正方形、长方形（不包含正方形）。

输入输出样例
输入
2 3
输出
8 10