bzoj 2142 国家集训队试题 礼物
2024-09-04 05:34:08
问题转化成求C(N,M) mod P p为非素数，那么我们可以将P分解质因数，
也就是 π pi^ci的形式，因为这些pi^ci是互质的，所以我们可以用crt将他们合并
那么问题就转化成了快速求C(N,M) mod pi^ci
那么我们看下c的形式，为N!/(M!(N-M)!) mod pi^ci
因为mod的数不是质数，所以分母没法正常求逆元，那么我们可以将分子分母
中的pi的值挑出，那么我们先求N!，可以发现，N！mod pi^ci可以分段，每段是
pi^ci长，这一段的值是0--（pi^ci-1），那么因为我们需要将N!中pi|I的挑出来
剩下一些数，那就是好几段这个数相乘，用快速幂解决就行了，设cnt为p!其中
不包括pi|n的
那么N！ mod pi^ci就变成了cnt^x*pi^y，那么x，y我们可以求出来，然后div掉p
之后，就又出现了一个阶乘，那么递归去做就行了。
比如N=11 pi=2 ci=2
N！为1*2*3*4*5*6*7*8*9*10*11
那么就是[1*3]*[5*7]*[9*11] mod pi^ci
挑出来的数是2,4,6,8,10，都div pi之后是
1,2,3,4,5 然后就成一个子问题了。
/**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/
//By BLADEVIL
var
m, n :longint;
pj, c :array[..] of longint;
pi, s, a :array[..] of int64;
p :int64;
tot :longint;
procedure divide(p:int64);
var
i, j :longint;
begin
tot:=;
for i:= to trunc(sqrt(p)) do
if p mod i= then
begin
inc(tot);
pj[tot]:=i;
while p mod i= do
begin
inc(c[tot]);
p:=p div i;
end;
end;
if p> then
begin
inc(tot);
pj[tot]:=p;
c[tot]:=;
end;
for i:= to tot do
begin
pi[i]:=;
for j:= to c[i] do pi[i]:=pi[i]*pj[i];
end;
end;
function ex_gcd(a,b:int64;var x,y:int64):int64;
var
t :int64;
begin
if (b=) then
begin
x:=;y:=;
exit(a);
end;
ex_gcd:=ex_gcd(b,a mod b,x,y);
t:=x;
x:=y;
y:=t-(a div b)*y;
end;
function gcd(a,p:int64):int64;
var
x, y :int64;
begin
x:=;y:=;
ex_gcd(a,p,x,y);
x:=(x mod p+p)mod p;
exit(x);
end;
function mi(x,y,q:int64):int64;
var
rec :int64;
begin
rec:=;
while (y>) do
begin
if y and = then rec:=rec*x mod q;
x:=x*x mod q;
y:=y shr ;
end;
exit(rec);
end;
function fac(n,p,q:int64):int64;
var
cnt :int64;
i :longint;
begin
cnt:=;
for i:= to n do
if (i mod p>) then
cnt:=cnt*i mod q;
exit(cnt);
end;
function fact(n:int64;var sum:int64;p,q:int64):int64;
var
cnt, rec :int64;
begin
rec:=;
cnt:=fac(q,p,q);
while n>=p do
begin
sum:=sum+n div p;
if (n div q>) then rec:=rec*(mi(cnt,n div q,q) mod q)mod q;
if (n mod q>) then rec:=rec*(fac(n mod q,p,q)mod q) mod q;
n:=n div p;
end;
if n> then rec:=rec*fac(n,p,q) mod q;
exit(rec);
end;
function combine(n,m,p,q:int64):int64;
var
ans1, ans2, ans3, ans :int64;
a, b, c :int64;
begin
a:=;b:=;c:=;
ans1:=fact(n,a,p,q);
ans2:=fact(m,b,p,q);
ans3:=fact(n-m,c,p,q);
a:=a-(b+c);
ans:=mi(p,a,q);
ans:=ans*ans1 mod q;
ans:=ans*gcd(ans2,q) mod q;
ans:=ans*gcd(ans3,q) mod q;
exit(ans);
end;
function doit(n,m:longint):int64;
var
i :longint;
x, y, sum :int64;
begin
sum:=;
for i:= to tot do
a[i]:=combine(n,m,pj[i],pi[i]);
for i:= to tot do
begin
x:=;y:=;
ex_gcd(s[i],pi[i],x,y);
x:=(x mod pi[i]+pi[i])mod pi[i];
sum:=(sum+((x*s[i] mod p)*a[i])mod p)mod p;
end;
exit(sum mod p);
end;
procedure main;
var
i :longint;
w :array[..] of longint;
ans :int64;
sum :int64;
begin
readln(p);
divide(p);
for i:= to tot do s[i]:=p div pi[i];
readln(n,m);
sum:=;
for i:= to m do
begin
readln(w[i]);
inc(sum,w[i]);
end;
if sum>n then
begin
writeln('Impossible');
exit;
end;
ans:=;
for i:= to m do
begin
ans:=ans*doit(n,w[i]) mod p;
n:=n-w[i];
end;
writeln(ans);
end;
begin
main;
end.
最新文章
- hpunix下11gRac的安装
- [异常] openCV安装和配置
- c++容器（vector、list、deque）
- Java注解（Annotation）自定义注解入门
- 微软自带报表rdlc操作（合并同数据项）
- A Tour of Go For continued
- Ibatis的分页机制的缺陷
- postfix日志分析pflogsumm
- selenium 执行js,实现滚动条
- docker学习（一）
- centos7 更新Firefox版本
- 学习笔记—XML
- LVS实现负载均衡安装配置详解
- 002 网上看的unity学习路线
- Android开发：在Eclipse中配置Android环境
- [C#]实现任何数据库类型的DbHelper帮助类
- centos如何查看linux内核，版本号
- java指令备忘
- poj1321 棋盘问题（DFS）
- mysql插入中文出错，提示1366 - Incorrect
热门文章
- 怎么防止别人动态在你程序生成代码（怎么防止别人反编译你的app）
- jmeter设置全局变量的方法
- 问题 A: 完数
- git instaweb 500 error
- Failed loading D:\Program Files\phpStudy20161103\php\php-5.6.27-nts\ext\php_xdebug.dll
- BZOJ 4184 shallot 线性基+分治
- Visual Studio 2012,创建工程Build Driver，基于纯Source Code.
- CKEditor的基本使用
- Metrics+ElasticSearch+grafana
- 安装和配置hadoop集群步骤