【BZOJ4517】排列计数(排列组合)
2024-09-29 01:00:53
题意:1-n的一个序列,其中有m个a[i]=i,求方案数
n,m<=1000000
题意:显然ANS=c(n,m)*d[n-m]
d[i]为错排方案数=d[i-1]*n+(-1)^n
const mo=;
var fac,exf,d:array[..]of int64;
cas,i,n,m:longint; function c(x,y:longint):int64;
begin
exit(fac[x]*exf[y] mod mo*exf[x-y] mod mo);
end; begin
assign(input,'bzoj4517.in'); reset(input);
assign(output,'bzoj4517.out'); rewrite(output);
d[]:=;
for i:= to do
begin
d[i]:=d[i-]*i;
if i and = then inc(d[i])
else dec(d[i]);
d[i]:=d[i] mod mo;
end;
fac[]:=; exf[]:=; exf[]:=;
for i:= to do fac[i]:=fac[i-]*i mod mo;
for i:= to do exf[i]:=exf[mo mod i]*(mo-mo div i) mod mo;
for i:= to do exf[i]:=exf[i-]*exf[i] mod mo;
readln(cas); d[]:=;
for i:= to cas do
begin
readln(n,m);
writeln(c(n,m)*d[n-m] mod mo);
end;
close(input);
close(output);
end.
最新文章
- 用NPOI从DataBase到Excel
- 关于WPF程序启动性能
- Solve error: Cannot open include file: &#39;X11/Xlocale.h&#39;: No such file or directory
- memcache和memcahced的区别
- [状压dp]HDOJ3182 Hamburger Magi
- KALI ssh无法登陆的解决办法
- mustache.js使用基本(二)sections
- 异步式I/O与实践式编程
- PLSQL配置怎么连ORACLE
- JavaScript正则表达式模式匹配(6)——常用的正则表达式
- java-关于java_home配置,classpath配置和javac,java命令,javac编译器,和java虚拟机之间的关系
- Tomcat下载,及环境变量配置
- 博客 first
- 使用Python生成基础验证码教程
- delphi 删除字符串的回车、空格、Tab键
- win7电脑遇到端口被占用的情况该如何查看并将其关闭
- Shadow Map 实现极其细节
- SQLite中的自增关键字:AUTO_INCREMENT、INTEGER PRIMARY KEY与AUTOINCREMENT
- C++ 百炼成钢20
- How to Design a Good&#160;API and Why it Matters