1. 首页
  2. Let's OI!
  3. 正文

bzoj1008: [HNOI2008]越狱【排列组合】

  • 内容
  • 评论
  • 相关

题目点击这里

其实就是小学数学题啦~没什么好说的，直接求不方便，可以先求出所有的方案数为M^N，然后不会越狱的方案数为M*(M-1)^(N-1)，相减就可以，当然由于数据稍微有点大，所以需要用快速幂来搞定。

代码：

var
  p,q,ans:int64;
  n,k,m:int64;
begin
  read(m,n);
  m:=m mod 100003;
  p:=1;
  k:=n;
  ans:=m;
  repeat
    if k mod 2=1 then p:=p*m mod 100003;
    m:=m*m mod 100003;
    k:=k div 2;
  until k=0;
  m:=ans;
  m:=m-1;
  if m<0 then m:=m+100003;
  q:=1;
  k:=n-1;
  repeat
    if k mod 2=1 then q:=q*m mod 100003;
    m:=m*m mod 100003;
    k:=k div 2;
  until k=0;
  m:=(ans) mod 100003;
  q:=q*m mod 100003;
  ans:=p-q;
  if ans<0 then ans:=ans+100003;
  writeln(ans);
end.

评论

0条评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。