P5520 【[yLOI2019] 青原樱】题解

整理博客的时候改了下分类标签，重新审一下
题目传送门
翻了翻题解区，发现基本没和我写的一样的（主要是都比我的写的简单
看题目：
第一眼，数学题；第二眼：组合数
接着想起来那道放苹果
n个位置，m棵树，就有n-m个空位，记space=n-m
转化问题为：

1. space个空位插入m-1个位置（即左右两边都不留空）
   
2. sapce个空位插入m个位置（即左边或右边留空，这种情况的答案要乘2）
   
3. space个空位插入m+1个位置（即左右两边都留空位）

现在将space个空位看作space个苹果，m或m-1或m+1个位置看成盘子，因为每个位置（盘子）都要有至少一个空位（苹果），所以，这和放苹果就没什么区别了
运用一点隔板法解决：
以情况1为例： space个苹果间有space-1个间隔，因为要放进m-1个盘子，所以只需在space-1个间隔中选m-2个插入隔板，不重复不考虑顺序，所以：\(\tbinom {space-1} {m-2}\)
那么另外两种也就简单了，分别为：\(\tbinom {space-1} {m-1}\),\(\tbinom{space-1} {m}\)
考虑如何算组合数，发现p不一定为质数，所以对组合数计算的每个数分解，再约分
我用he数组表示一个数的最小质因子，为0说明不为合数
用sum数组记录每个质数的指数，是分子就加一，分母就减一
之后再快速幂乘起来
因为那m棵树是不同的，所以有m！种排列方式，也就是ans\(\times {m!}\)

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstring>
#define R register
#define EN printf("\n")
#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;
}  

P5520 【[yLOI2019] 青原樱】

原文：https://www.cnblogs.com/suxxsfe/p/12527490.html