组合计数及补充

方法 1.递推 2.隔板 3.加法原理 乘法原理 4.组合数和排列数 5.lucas 6.catalan数列

---

1.车的放置

信息学奥赛一本通（C++版）在线评测系统

由于这题的不规则图形很难求 所以尝试把它划分成两个规则的矩形 这样就会好求一些

对于一个n行m列的矩形 放k个车 那么就是在n行中选k行(C(k,n))放并且不能在同一列那么就是m*m-1*.....就是A(k,m)

然后还不知道两个矩形放多少个车 那么就可以枚举一下 并且一定要选放上半部分 因为放下部分的话对选的列影响不固定 上半部分就不会产生这样的效果 那么就可以知道最后结果

 

#include
using namespace std;
typedef long long ll;
const int N=2010,mod=1e5+3;
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 C(int a,int b)//C(a,b)
{
    if(areturn 0;
    return (ll)fact[a]*infact[a-b]%mod*infact[b]%mod;
}
int A(int a,int b)//A(a,b)
{
    if(areturn 0;
    return (ll)fact[a]%mod*infact[a-b]%mod;
}
void init(int n)//预处理出来所有阶层和阶层逆元
{
    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]%mod*qmi(i,mod-2,mod)%mod;
    }
}
int main()
{
    init(N-1);//预处理处理所有的阶层
    int a,b,c,d,k;
    cin>>a>>b>>c>>d>>k;
    int res=0;
    for(int i=0;i<=k;i++)//枚举所有情况
       res=(res+(ll)C(b,i)*A(a,i)%mod*C(d,k-i)%mod*A(a+c-i,k-i))%mod;
    cout<
    return 0;
}

2.数三角形

信息学奥赛一本通（C++版）在线评测系统

这题是一个补集的思想

n*m的格点中选三个点 - 斜率为0的点(m个点)有n行 - 斜率为无穷的点n个点有m列 - 斜率大于0 用dp去求 - 斜率小于0（和斜率大于0对称 数量相同）

斜率大于0的求法

用集合的思想去划分直线上的左下角的点是哪个点 那么就有(1,1),(1,2)......,(n,m)的点

然后看一下(i,j)右上角有那么点 那么就是(m-i,n-i)个点可以选择成为第二个点 现在就差第三个的点没有找到 中间的点就是这条直线的整数点 可以用gcd(i,j)-1求得

 

#include
using namespace std;
typedef long long ll;
int n,m;
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
ll C(int n)
{
    return (ll)n*(n-1)*(n-2)/6;
}
int main()
{
    cin>>m>>n;
    m++,n++;//格子n m个 但是点数就有 n+1 m+1个
    ll res=C(n*m)-(ll)n*C(m)-(ll)m*C(n);//算斜率不存在跟为0情况
    for(int i=1;i<=n;i++)//枚举左下角的点
        for(int j=1;j<=m;j++)
          res-=2ll*(gcd(i,j)-1)*(n-i)*(m-j);//减去不满足的也即在一条直线上的
   cout<
    return 0;
}

   3.序列统计

信息学奥赛一本通（C++版）在线评测系统

这样转换完就可以用隔板法了

 

#include
using namespace std;
typedef long long ll;
const int p=1e6+3;
int n,l,r;
int qmi(int a,int k)//快速幂求逆元
{
    int res=1;
    while(k)
    {
        if(k&1) res=(ll)res*a%p;
        a=(ll)a*a%p;
        k>>=1;
    }
    return res;
}
int C(int a,int b)//求C(a,b)
{
    if(areturn 0;
    int down=1,up=1;
    for(int i=a,j=1;j<=b;i--,j++)
    {
        up=(ll)up*i%p;
        down=(ll)down*j%p;
    }
    return (ll)up*qmi(down,p-2)%p;//除以他的阶层相当于乘以他的逆元
}
int Lucas(int a,int b)//Lucas定理
{
    if(areturn C(a,b);
    return (ll)Lucas(a/p,b/p)*C(a%p,b%p)%p;
}
void solve()
{
    cin>>n>>l>>r;
    cout<<(Lucas(r-l+n+1,r-l+1)-1+p)%p<//输出分析的答案
}
int main()
{
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

 4.网络

信息学奥赛一本通（C++版）在线评测系统

卡特兰数的小变形

下面介绍来自百度 

卡特兰数是组合数学中一个常出现于各种计数问题中的数列。以中国蒙古族数学家明安图和比利时的数学家欧仁·查理·卡特兰的名字来命名，其前几项为（从第0项开始）：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...

满足

方法一

方法二 

 则答案就是C(n+m,m)-C(n+m,n+1)，因为答案非常大，所以得用高精度来写 

#include
using namespace std;
typedef long long ll;
const int N=100010;
int primes[N],cnt;
bool st[N];
int a[N],b[N];
void init(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)//获取n!中p的次方s
{
    int s=0;
    while(n) s+=n/p,n/=p;
    return s;
}
void mul(int r[],int &len,int x)//高精度乘法
{
    int t=0;
    for(int i=0;i
    {
        t+=r[i]*x;
        r[i]=t%10;
        t/=10;
    }
    while(t) r[len++]=t%10,t/=10;
}
int C(int x,int y,int r[N])//求C(x,y)存在r中，C(x,y)=x!/(y!*(x-y)!)
{
     int len=1;
     r[0]=1;
     for(int i=0;i//枚举所有质因数
     {
         int p=primes[i];//获取当前质数
         int s=get(x,p)-get(y,p)-get(x-y,p);//每个阶层减去p这个质数，s是剩下p的次方
         while(s--) mul(r,len, p);//高精度乘法，求p^s次方
     }
     return len;
}
void sub(int a[],int al,int b[],int bl)//高精度减法
{
    for(int i=0,t=0;i
    {
        a[i]-=t+b[i];
        if(a[i]<0) a[i]+=10,t=1;//假如不够，则借位
        else t=0;
    }
}
int main()
{
    init(N-1);
    int n,m;
    cin>>n>>m;
    int al=C(n+m,m,a);//al是a数组的长度，C(n+m,m)
    int bl=C(n+m,n+1,b);//bl是b数组的长度，C(n+m,n+1)
    sub(a,al,b,bl);//高精度减法 a=a-b
    int k=al-1;
    while(k>0&&!a[k]) k--;//删除前导0
    while(k>=0) printf("%d",a[k--]);//输出答案
    return 0;
}