1.车的放置
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
因为n不是很大求组合数可以用杨辉三角，也可以直接循环求阶层来算
逆元的用法是：当mod的数是质数时，并且是一个数除以一个数时，可用一个数乘以他的逆元来求
#include<bits/stdc++.h> 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(a<b) return 0; return (ll)fact[a]*infact[a-b]%mod*infact[b]%mod; } int A(int a,int b)//A(a,b) { if(a<b) return 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<<res<<endl; return 0; }
2.数三角形
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
这题可以用补集的思想，用总的方式减不满足的情况，不满足的情况就是三个点在一条直线上的
这是有斜率大于0的情况中不满足的情况的分析
gcd(i,j)要减一，因为不能选第一个跟第二个点，所以要减一在乘，上面和下面都写错了
标准：
#include<bits/stdc++.h> 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<<res<<endl; return 0; }
3.序列统计
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
然后在枚举序列长度K
因为就需要求一个C(m+n+1，m+1)则直接用卢卡斯定理求组合数的方法求即可
#include<bits/stdc++.h> 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(a<b) return 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(a<p&&b<p) return 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<<endl;//输出分析的答案 } int main() { int T; cin>>T; while(T--) solve(); return 0; }
卡特兰数满足的性质：
1.递减式：f(n)=f(1)*f(n-1)+f(2)*f(n-2)+....
2.挖掘性质：任意前缀中的某种东西>=另一种东西
3.直觉看到3的答案是5可能是卡特兰数
4.网格
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
之前求卡特兰数的方法，但是这题换成了n跟m，则一样的分析
这题的推导过程：
1.直接求对称点
2.曲线救国
则答案就是C(n+m,m)-C(n+m,n+1)，因为答案非常大，所以得用高精度来写
#include<bits/stdc++.h> 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<len;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<cnt;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<al;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; }
5. 有趣的数列
这题就是要满足：奇数项的个数>=偶数项的个数，我们可以把奇数项看成0，偶数项看成1
然后有1~2n个位置，奇数项对应0，偶数项对应1，相当于给我们n个0，n个1，然后保证任意前缀里面0的个数要大于1的个数，所以这题就可以对应到卡特兰数
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
然后这题答案就是C(2n,n)-C(2n,n-1)，然后用分解质因式+快速幂来求mod数，因为mod数会变所以不能用逆元来求C(a,b)=a!/(b!*(a-b)!)
#include<bits/stdc++.h> 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<cnt;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<<endl;//输出卡特兰数 return 0; }
