P4071 [SDOI2016]排列计数题解

以你之姓@ 2021-10-24 07:00 211阅读 0赞

# 分析： #

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

# 代码： #

#include<cstdio> using namespace std; const long long mod=1000000007; long long ni[1000005],cheng[1000005],dao[1000005],d[1000005]; int main() { d[0]=1; d[1]=0; d[2]=1; for(long long i=3;i<=1000000;i++) { d[i]=((i-1)*(d[i-1]+d[i-2]))%mod; }//错排递推公式！！！ ni[1]=1;//1的逆元为1 for(long long i=2;i<=1000000;i++) { ni[i]=(mod-mod/i)*ni[mod%i]%mod; }//求出i的逆元(线性求逆元板子 cheng[0]=1; for(long long i=1;i<=1000000;i++) { cheng[i]=(cheng[i-1]*i)%mod; } //求出i的正常阶乘 dao[0]=1; for(long long i=1;i<=1000000;i++) { dao[i]=(dao[i-1]*ni[i])%mod; } long long T; scanf("%lld",&T); while(T--) { long long n,m; scanf("%lld%lld",&n,&m); printf("%lld\n",(cheng[n]%mod*dao[m]%mod*dao[n-m]%mod*d[n-m]%mod)%mod); } return 0; }

转载于:https://www.cnblogs.com/ShineEternal/p/11219256.html

[https_blog.csdn.net_qq_34564984_article_details_52292502]: https://blog.csdn.net/qq_34564984/article/details/52292502

发表评论取消回复

表情：

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

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

相关阅读

相关 P2152-[SDOI2009]SuperGCD

1 // luogu-judger-enable-o2 2 include<bits/stdc++.h> 3 using namespace s

小鱼儿/ 2023年06月01日 08:47/ 0 赞/ 157 阅读

相关计数问题——题解

记录一下，写代码10分钟，改 Bug 3小时~ 给定两个整数 a 和 b，求 a 和 b 之间的所有数字中 0∼9 的出现次数。例如，a=1024，b=1032

Myth丶恋晨/ 2022年09月12日 08:52/ 0 赞/ 118 阅读

相关洛谷 P4071 [SDOI2016]排列计数

![1596060-20190612191650302-584562041.png][] ![1596060-20190612191710278-1020740109.png

Bertha 。/ 2022年01月12日 13:33/ 0 赞/ 163 阅读

相关 [SDOI2010]地精部落题解

Description 传说很久以前，大地上居住着一种神秘的生物：地精。地精喜欢住在连绵不绝的山脉中。具体地说，一座长度为 N 的山脉 H可分为从左到右的 N 段，每

刺骨的言语ヽ痛彻心扉/ 2021年12月01日 18:08/ 0 赞/ 186 阅读

相关 Perm 排列计数

排列组合这部分确实很水，但关键是想到树，堆。 i与2×i，2×i+1有关，符合树上节点编号的特点，加上大小限制就是堆的性质了。这个堆中存的是节点编号所以大小固定，每个节点

分手后的思念是犯贱/ 2021年11月11日 01:38/ 0 赞/ 174 阅读

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

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

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

相关 Luogu P2486 [SDOI2011]染色

[P2486 \[SDOI2011\]染色][P2486 _SDOI2011] 卡了我五天的题目。。是一道树剖一直RE查出来是无限递归，\\(cur\\)下标爆炸了。。

迈不过友情╰/ 2021年10月24日 01:10/ 0 赞/ 244 阅读

相关 P4070 [SDOI2016]生成魔咒

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

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

相关 P3704 [SDOI2017]数字表格

\\(\\color\{\0066ff\}\{ 题目描述 \}\\) Doris刚刚学习了fibonacci数列。用\\(f\[i\]\\)表示数列的第\\(i\\)项，

- 日理万妓/ 2021年09月29日 15:34/ 0 赞/ 253 阅读

相关 BZOJ2242：[SDOI2011]计算器——题解

[https://www.lydsy.com/JudgeOnline/problem.php?id=2242][https_www.lydsy.com_JudgeOnline_

灰太狼/ 2021年09月20日 09:36/ 0 赞/ 221 阅读