bzoj 4465: [Jsoi2013]游戏中的学问
2024-10-20 13:35:47
4465: [Jsoi2013]游戏中的学问
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 121 Solved: 59
[Submit][Status][Discuss]
Description
大家应该都见过很多人手拉手围着篝火跳舞的场景吧?一般情况下,大家手
拉手跳舞总是会围成一个大圈,每个人的左手拉着旁边朋友的右手,右手拉着另
一侧朋友的左手。
不过,如果每一个人都随机的拉住两个不同人的手,然后再慢慢散开,事情
就变得有趣多了——此时大家依旧会形成圈,不过却可能会形成多个独立的圈。
当然这里我们依然要求一个人的右手只能拉另一个人的左手,反之亦然。
班里一共有N个同学,由1到N编号。Will想知道,究竟有多少种本质不
同的拉手方案,使得最终大家散开后恰好形成k个圈呢?
给定两种方案,若存在一个人和他的一只手,满足在这两种方案中,拉着这
只手的人的编号不同,则这两种方案本质不同。
Input
输入一行包含三个正整数N,k和P.
3<=3k<=N<=3000,10^4<=p<=2×10^9
Output
输出文件的包含一行一个整数,表示本质不同的方案数对p的余数。保证p
一定是一个质数。
Sample Input
3 1 1000000009
Sample Output
2
HINT
Source
本质是求有多少个n个元素的置换,有k个循环且其中每个循环长度至少是3。
这样就设f[i][j]为1-i构成的有j个循环的每个循环至少是3的方案数。
转移的话考虑一下是否新开一个循环即可。
#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
using namespace std;
int f[maxn*3][maxn],n,k,P;
int jc[maxn*3],ni[maxn*3]; inline int add(int x,int y){
x+=y;
return x>=P?x-P:x;
} inline void dp(const int ha){
f[0][0]=1;
for(int i=3;i<=n;i++){
int tp=min(i,k);
for(int j=1;j<=tp;j++) f[i][j]=add(f[i-3][j-1]*(ll)(i-1)%ha*(ll)(i-2)%ha,f[i-1][j]*(ll)(i-1)%ha);
}
} int main(){
scanf("%d%d%d",&n,&k,&P);
dp(P);
printf("%d\n",f[n][k]);
return 0;
}
最新文章
- JavaWeb——ServletContext
- MFC AfxMessageBox默认标题修改
- javascript平时小例子④(setInterval使用2)
- App开发流程之配置Info.plist文件
- segment fault
- linux进程后台运行的几种方法
- ASP.NET MVC Razor视图(2)
- java一点内容
- (iOS)开发中收集的小方法
- 【转】linux shell 逻辑运算符、逻辑表达式
- web.config文件中配置数据库连接的两种方式
- Tomcat 日志文件分割
- winform界面特效470多例
- 设计模式のVisitorPattern(访问者模式)----行为模式
- ubuntu 忽略文件的50unattended升级问题
- linux 搭建ftp服务
- flask 在视图函数中验证表单
- 自定义适用于手机和平板电脑的 Dynamics 365(四):窗体脚本
- linux下通过命令行上传文件到百度网盘
- vue 混入的理解