P5520 【[yLOI2019] 青原樱】题解
整理博客的时候改了下分类标签，重新审一下
题目传送门
翻了翻题解区，发现基本没和我写的一样的（主要是都比我的写的简单
看题目：
第一眼，数学题；第二眼：组合数
接着想起来那道放苹果
n个位置，m棵树，就有n-m个空位，记space=n-m
转化问题为：
- space个空位插入m-1个位置（即左右两边都不留空）
- sapce个空位插入m个位置（即左边或右边留空，这种情况的答案要乘2）
- space个空位插入m+1个位置（即左右两边都留空位）
现在将space个空位看作space个苹果，m或m-1或m+1个位置看成盘子，因为每个位置（盘子）都要有至少一个空位（苹果），所以，这和放苹果就没什么区别了
运用一点隔板法解决：
以情况1为例： space个苹果间有space-1个间隔，因为要放进m-1个盘子，所以只需在space-1个间隔中选m-2个插入隔板，不重复不考虑顺序，所以：( binom {space-1} {m-2})
那么另外两种也就简单了，分别为：( binom {space-1} {m-1}),( binom{space-1} {m})
考虑如何算组合数，发现p不一定为质数，所以对组合数计算的每个数分解，再约分
我用he数组表示一个数的最小质因子，为0说明不为合数
用sum数组记录每个质数的指数，是分子就加一，分母就减一
之后再快速幂乘起来
因为那m棵树是不同的，所以有m！种排列方式，也就是ans( imes {m!})
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstring>
#define R register
#define EN printf("
")
#define LL long long
inline LL read(){
LL x=0,y=1;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-') y=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=getchar();}
return x*y;
}
int he[2000006],prime[2000006],cnt;//he[i]为i的最小质因子
LL sum[2000006];
inline void getprime(LL n){
for(R int i=2;i<=n;i++){
if(!he[i]) prime[++cnt]=i;
for(R int j=1;j<=cnt&&i*prime[j]<=n;j++){
he[prime[j]*i]=prime[j];
if(!(i%prime[j])) break;
}
}
}
inline LL pow(LL a,LL b,LL p){
LL ret=1;
while(b){
if(b&1) ret=(ret*a)%p;
a=(a*a)%p;
b>>=1;
}
return ret;
}
inline void fenjie(int x,int v){
while(he[x]){
sum[he[x]]+=v;
x/=he[x];
}
if(x>1) sum[x]+=v;
}
inline LL C(LL n,LL k,LL p){
memset(sum,0,sizeof sum);
if(k>n) return 0;
if(k==n) return 1%p;
if(k==0) return 1%p;
if(k==1) return n%p;
LL ret=1;
for(R int i=n-k+1;i<=n;i++) fenjie(i,1);
for(R int i=1;i<=k;i++) fenjie(i,-1);
for(R int i=2;i<=n;i++){
if(sum[i]) ret=(ret*pow(i,sum[i],p))%p;
}
return ret;
}
int main(){
LL ty=read(),n=read(),m=read(),p=read();
LL space=n-m;
getprime(n);
LL jc=1;
for(R int i=2;i<=m;i++) jc=(jc*i)%p;
LL ans=C(space-1,m-2,p);
ans=(ans+C(space-1,m-1,p)*2)%p;
ans=(ans+C(space-1,m,p))%p;
ans=(ans*jc)%p;
printf("%lld",ans);
return 0;
}