P5520 [yLOI2019] 青原樱-数学+排列组合

[yLOI2019] 青原樱

题目背景

星川之下皆萤火尘埃，
我独行在人潮你天真而待。
相遇若是借丹青着色，
青原上 绯樱如海。

——银临《青原樱》(Cover 人衣大人)

题目描述

扶苏是一个非常喜欢边听古风鸽边写数学题的人，因此这道题其实是个五三原题。

扶苏希望重现青原上樱花盛开的景色，于是他准备了很多互不相同樱花树幼苗，准备种成一行。

这一行中，一共有 $n$ 个位置可以种下樱花，而扶苏准备了 $m$ 支幼苗。由于樱花盛放时对左右空间需求非常大，所以樱花不能紧挨着种植，也就是任意两支幼苗之间必须至少存在一个不种花的空位置。

按照这种方式种花并不难，但是令扶苏感到好奇的是一共有多少合法的方案让他把这 $m$ 支幼苗都种下去。一个方案是合法的当且仅当他满足上一段中叙述的要求。如果我们将花按照 $1,2,3,\dots ,m$ 编号，两种方案不同当且仅当被选择种花的位置不同或从左向右数花的编号序列不同。

为了避免输出过大，答案对一个参数 $p$ 取模。

输入格式

每个输入文件中有且仅有一组测试数据。

测试数据只有一行四个整数，依次代表 $type,n,m,p$，其中 $type$ 是一个帮助你判断测试点类型的参数，会在数据范围中说明。

输出格式

输出一行一个整数，代表答案对 $p$ 取模的结果。

样例 #1

样例输入 #1

1 3 2 19260718

样例输出 #1

2

#include 
using namespace std;
#define de(x) cout<<x<<" ";
#define Pu puts("");
#define sf(x) scanf("%d",&x);
typedef long long ll;
const int N=3e6+10,mod=100003;
ll n,m,ans;//n个位置去掉m-1个空位，剩下的n-m+1个位置中选m个->A(m,n-m+1)
ll p;
int main(){ll type;cin>>type>>n>>m>>p;ans=1;for(ll i=n-m+1;i>=(n-m+1)-(m)+1;i--){ans=(ans*i)%p;}de(ans)
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！