组合计数3以及高斯消元

组合计数

卡特兰数满足的性质：

1.递减式：f(n)=f(1)*f(n-1)+f(2)*f(n-2)+....

2.挖掘性质：任意前缀中的某种东西>=另一种东西

3.直觉看到3的答案是5可能是卡特兰数

1. 有趣的数列

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

这题就是卡特兰数

这题就是要满足：奇数项的个数大于偶数项的个数，我们可以把奇数项看成0，偶数项看成1

然后有1~2n个位置，奇数项对应0，偶数项对应1，相当于给我们n个0，n个1，然后保证任意前缀里面0的个数要大于等于1的个数，所以这题就对应了上一节的一道题了

然后这题答案就是C(2n,n)-C(2n,n-1)，然后用分解质因式+快速幂来求mod数，因为mod数会变所以不能用逆元来求C(a,b)=a!/(b!*(a-b)!)

#include
using namespace std;
typedef long long ll;
const int N=2e6+10;
int primes[N],cnt;
bool st[N];
int n,p;
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 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 get(int n,int p)//获取一个阶层的p次方s
{
    int s=0;
    while(n) s+=n/p,n/=p;
    return s;
}
int C(int a,int b)//获取C(a,b)
{
    int res=1;
    for(int i=0;i//分解质因式的方式求
    {
        int prime=primes[i];
        int s=get(a,prime)-get(b,prime)-get(a-b,prime);
        res=(ll)res*qmi(prime,s)%p;//乘以p的s次方
    }
    return res;
}
int main()
{
    cin>>n>>p;
    init(2*n);
    cout<<(C(2*n,n)-C(2*n,n-1)+p)%p<//输出卡特兰数
    return 0;
}

---

高斯消元

1.球形空间产生器

207. 球形空间产生器 - AcWing题库

直接求得的方程为

再进行转换就可以得到线性方程

#include
using namespace std;
const int N=15;
double a[N][N],b[N][N];
int n;
void gauss()
{
    //转化成上三角矩阵
    for(int r=1,c=1;c<=n;c++,r++)
    {
        //找主元
        int t=r;
        for(int i=r+1;i<=n;i++)
            if(fabs(b[i][c]>fabs(b[t][c])))
                t=i;
       //交换
       for(int i=c;i<=n+1;i++) swap(b[t][i],b[r][i]);
       //归一化
       for(int i=n+1;i>=c;i--) b[r][i]/=b[r][c];
       //消当前列的当前行的下面行的数为0
       for(int i=r+1;i<=n;i++)
          for(int j=n+1;j>=c;j--)
            b[i][j]-=b[i][c]*b[r][j];
    }
    //转化成对角矩阵
    for(int i=n;i>1;i--)
        for(int j=i-1;j;j--)
        {
            b[j][n+1]-=b[i][n+1]*b[j][i];
            b[j][i]=0;
        }
}
int main()
{
   scanf("%d",&n);
   for(int i=0;i<=n;i++)
     for(int j=1;j<=n;j++)
        scanf("%lf",&a[i][j]);
   for(int i=1;i<=n;i++)//转化成线性方程
      for(int j=1;j<=n;j++)
      {
         b[i][j]=2*(a[i][j]-a[0][j]);
         b[i][n+1]+=a[i][j]*a[i][j]-a[0][j]*a[0][j];
      }
  gauss();//高斯消元
  for(int i=1;i<=n;i++) printf("%.3lf ",b[i][n+1]);//输出答案
    return 0;
}

2.开关问题

208. 开关问题 - AcWing题库

线性方程组等式右边应该是灯最后的状态 不是1 2 3

 方案数取决于我们自由元的个数，每个自由元有两种情况0或者1，则假如自由元有k个则,答案有2^k个方案，k就是n - 非0行的个数也即自由元

#include
using namespace std;
const int N=35;
int n;
int a[N][N];
int gauss()
{
    int r,c;
    for(r=1,c=1;c<=n;c++)
    {
        //找主元
        int t=r;
        for(int i=r+1;i<=n;i++)
            if(a[i][c])
              t=i;
        //假如最大已经是了，则这一列不用操作了
        if(!a[t][c]) continue;
        //交换
        for(int i=c;i<=n+1;i++) swap(a[t][i],a[r][i]);
        //消
        for(int i=r+1;i<=n;i++)
            for(int j=n+1;j>=c;j--)
              a[i][j]^=a[i][c]&a[r][j];
        r++;
    }
    int res=1;
    if(r1)//求自由元个数
    {
        for(int i=r;i<=n;i++)
        {
            if(a[i][n+1]) return -1;//出现了0==！0无解
            res*=2;//每个自由元都有两个状态则就是*2
        }
    }
    return res;
}
int main()
{
   int T;
   scanf("%d",&T);
   while(T--)
   {
       memset(a,0,sizeof a);//清空
       scanf("%d",&n);
       for(int i=1;i<=n;i++) scanf("%d",&a[i][n+1]);//存初始状态
       for(int i=1;i<=n;i++)
       {
           int t;
           scanf("%d",&t);
           a[i][n+1]^=t;//初始跟末状态异或
           a[i][i]=1;//自己这盏灯影响自己的状态
       }
       int x,y;
       while(scanf("%d%d",&x,&y),x||y) a[y][x]=1;//x影响y这盏灯则y这行x会影响他
       int t=gauss();
       if(t==-1) puts("Oh,it's impossible~!!");//假如无解
       else printf("%d\n",t);
   }
    return 0;
}