P4609 [FJOI2016]建筑师

逃离我推掉我的手 2021-12-23 14:09 198阅读 0赞

#### 思路 ####

裸的第一类斯特林数，思路和CF960G相同

预处理组合数和第一类斯特林数回答即可

#### 代码 ####

#include <cstdio> #include <cstring> #include <algorithm> #define int long long using namespace std; const long long MOD= 1e9+7; long long jc[300],inv[300],n,a,b,S_[50100][210]; long long pow(long long a,long long b){ long long ans=1; while(b){ if(b&1) ans=(ans*a)%MOD; a=(a*a)%MOD; b>>=1; } return ans%MOD; } long long S(long long n,long long k){ if(k==0&&n==0) return 1; if(k==0||n==0) return 0; if(S_[n][k]!=-1) return S_[n][k]; return S_[n][k]=(S(n-1,k-1)%MOD+(n-1)*S(n-1,k)%MOD)%MOD; } long long C(long long n,long long m){ return jc[n]*inv[m]%MOD*inv[n-m]%MOD; } void init(void){ jc[0]=inv[0]=1; for(int i=1;i<300;i++){ jc[i]=jc[i-1]*i%MOD; inv[i]=pow(jc[i],MOD-2); } } int T; signed main(){ memset(S_,-1,sizeof(S_)); init(); scanf("%lld",&T); while(T--){ scanf("%lld %lld %lld",&n,&a,&b); if((!a)||(!b)||a+b-2>n-1){ printf("0\n"); continue; } if(n==1){ printf("%lld\n",1); continue; } printf("%lld\n",S(n-1,a+b-2)*C(a+b-2,b-1)%MOD); } return 0; }

转载于:https://www.cnblogs.com/dreagonm/p/10432991.html

发表评论取消回复

表情：

评论列表（有 0 条评论，198人围观）

还没有评论，来说两句吧...

相关阅读

相关 P4585 [FJOI2015]火星商店问题线段树分治+可持久化trie树

题意：有编号为1-n的商店每个商店有一个永久化的商品价值为v 操作1：时间过了一天第x商店增加了一个价值为val的货物操作2：该火星人有自己的密码值x 问第L个商店到

绝地灬酷狼/ 2023年08月17日 15:48/ 0 赞/ 135 阅读

相关 HDU 4609——3-idiots

题意：给定n个数，随机从这n个数中取3个数，问能组成三角形的概率是多少？思路：首先把统计这n个数出现的个数，那么会得到一个向量，这个向量的自我的乘积就是a\[i\]

淩亂°似流年/ 2022年07月19日 02:39/ 0 赞/ 45 阅读

相关 HDU 4609 3-idiots

题目：[点击打开链接][Link 1] 题意：给定n（n<=100000）个火柴棍的长度l（l<=100000），问任选三根能组成三角形的概率。分析：这道题实际

一时失言乱红尘/ 2022年05月13日 23:59/ 0 赞/ 101 阅读

相关战略游戏（LGOJ P2016） —— 树形DP基础

目录题目题目描述输入输出样例输入样例输出提示解析参考代码 -------------------- 前言为什么库存里还有一个这个

古城微笑少年丶/ 2022年03月08日 07:49/ 0 赞/ 327 阅读

相关 P4609 [FJOI2016]建筑师

思路裸的第一类斯特林数，思路和CF960G相同预处理组合数和第一类斯特林数回答即可代码 include <cstdio> include <cst

逃离我推掉我的手/ 2021年12月23日 14:09/ 0 赞/ 199 阅读

相关 P5459 [BJOI2016]回转寿司

[传送门][Link 1] 暴力怎么搞，维护前缀和 $s\[i\]$ ，对于每一个 $s\[i\]$，枚举所有 $j\\in\[0,i-1\]$，看看 $s\[i\]-s\[

左手的ㄟ右手/ 2021年12月10日 02:53/ 0 赞/ 158 阅读

相关 Luogu P2824 [HEOI2016/TJOI2016]排序线段树+脑子

只会两个$log$的$qwq$ -------------------- 我们二分答案：设答案为$ans$，则我们把$a\[i\]<=ans$全部设成$0$，把$a\

你的名字/ 2021年11月17日 15:28/ 0 赞/ 279 阅读

相关 P4071 [SDOI2016]排列计数题解

分析：线性求逆元：[https://blog.csdn.net/qq\_34564984/article/details/52292502][https_blog.cs

以你之姓@/ 2021年10月24日 07:00/ 0 赞/ 252 阅读

相关 P4070 [SDOI2016]生成魔咒

题目 [P4070 \[SDOI2016\]生成魔咒][P4070 _SDOI2016] 有点水做法每次把加上\\(np\\)这个点新生产的串，直接加上\\

た入场券/ 2021年09月30日 00:08/ 0 赞/ 330 阅读

相关 FJOI2016 神秘数

题目大意给定长为$N$一个序列，每次询问一个区间，求最小的不能表示为由区间内若干个（可以是$0$个）数的和的非负整数。考虑一个可重集合$S$，设抽取$S$中若干个

偏执的太偏执、/ 2021年09月29日 08:02/ 0 赞/ 221 阅读