算法与acm

poj3406 C(n,m)Last digit

2008年11月16日 阅读(212)

转载请注明作者:phylips@bmy 出处:http://duanple.blog.163.com/blog/static/70971767200810165100622/

http://acm.pku.edu.cn/JudgeOnline/problem?id=3406 Last digit

计算n!/(m!*(n-m)!)也就是C(n,m)的最后一个非零位—-poj3406

因为(m!*(n-m)!)不是n!的一个子集,所以这个不能利用1150的方法,而且观察它的input,实际上只有一个case,而且n ,m< 1000000,所以nlogn的方法是可以过的。

但是我们可以采用最简单的思路来解它,也就是直接遍历,对于每个数,计算2,5因子数,以及把它的因子2,5去除剩余的最后一位,最后把这些最后一位相乘,再求最后一位再考虑多余的2.5,然后求出最后一位。思路一样,但是求解2,5,3,7,9的方法采用了遍历的方法,而不是递归了。。。

这个是上篇大体说到的方法,但是这个方法说明有些,简单,针对这个问题,其实还存在一个很大的技巧性,看下面如下一段陈述,日语写的。。。

あー、そこまでいっているのに。素因数分解して、nCm の素因数を列挙するところまでは私と一緒。

でも、求めるのは最後の非零の桁なので、そのまま法10の剰余環の上で演算してもだめなのだな。

ほかの解法としては egoh さんのが良さげ。割り算が一意に決まるという意味が最初わからなかったのだが、2 と 5 の因数を排除して計算すると、1の位は 1, 3, 7, 9 に限定されるので、これだと除算もうまくという。

どういうことかというと、

(10 * x + a) * (10 * y + b) = 10 * z + c

なる a, b, c (a, b, c ? {1, 3, 7, 9}) は x, y, z によらず、他の2つがわかれば残り一つがわかるということ。例えば、c = 1, b = 3 なら a = 7 になる。

ということで、egoh さんのアルゴリズムを実装して縮めたら 310B だった。まだまだ縮まりそうだけど。

再看一段代码:

#include <stdio.h>
#include <string.h>
//poj3406
int main()
{
  
  int n,m;

  // 素因数2,5の数を保持
  int n2,n5;
  int m2,m5;

  int i,j,k;
  int ans=1;
  int tm,tn;

  n2 = n5 = m2 = m5 = 0;

  scanf("%d%d",&n,&m);

  for(i=0;i<m;++i)
  {
    tn = ans*n–;
    tm = m-i;
   
    // 2,5で可能な限り割る。同時に回数も記録
    while(tn%2==0){ ++n2; tn/=2; }
    while(tn%5==0){ ++n5; tn/=5; }
    while(tm%2==0){ ++m2; tm/=2; }
    while(tm%5==0){ ++m5; tm/=5; }
   
    // 掛けて下一桁が等しくなるansを見つける
    for(ans=1;1;++ans)
    {
      if( (tm*ans)%10==tn%10 )break;
    }
    printf("tm:%d ans:%d tn:%d\n ",tm,ans,tn);
  }
 
  // 共通な素因数は約分できるので、どちらかが0になるまで
  // カウントを減らす(mが先のハズ)
  while(n2&&m2){ –n2; –m2; }
  while(n5&&m5){ –n5; –m5; }
 
  // 10の倍数は下一桁が0になってしまうので消去
  while(n2&&n5){ –n2; –n5; }

  while(n2){ –n2; ans = (ans*2)%10; }
  while(n5){ –n5; ans = (ans*5)%10; }
 
  printf("%d\n",ans);
  while(1); 
  return 0;
}

很明显,也是日语。。。

分析说明:

主要是我发现他的这个实现很巧妙,看了许久,才看出其中的数学原理,有必要说明一下。其中最关键的一点在这一步// 掛けて下一桁が等しくなるansを見つける
    for(ans=1;1;++ans)
    {
      if( (tm*ans)%10==tn%10 )break;
    }

很遗憾我日语学的不好,只能看代码了,注释基本用不上。。。

基本思路如下

首先:要分解出因子2,5,然后再进行处理,代码中的很多部分都是实现的这部分功能,不过是直接枚举的,如

// 2,5で可能な限り割る。同時に回数も記録
    while(tn%2==0){ ++n2; tn/=2; }

n2用于记录因子2的数目,tn则不断把因子2分解出去。

然后:计算分解出2,5之后的算式的last digit

注意:下面式子中使用的n,m实际上是已经提取出2,5因子后的结果,为了书写方便这里仍使用原值表示。

对于C(n,m)很明显的结论是 n!/(m!*(n-m)!)必然是个整数,n!中的因子2,5的个数必然大于m!*(n-m)!的

以 C(10,3)为例=(10*9*8)/(3*2*1),把2,5提取之后变成了,(1*9*1)/(3*1*1),我们的目标就是要计算这个算式最后结果的last digit,然后再结合2,5的因子个数,确定最终的last digit.

对于这个需求,上面的代码实际上做了这样一直判断,因为分子必然是下面分母的整数倍,对分子进行了扩大处理扩大的同时保证各个扩大后的数的最后一位与原来相同,即(m-i)*ans%10==(n-i)%10

(m*ans1)*(m-1*ans2)*(m-2*ans3)……/m*m-1*m-2……

可以看到实际上是用上面这个列代替了n*n-1*n-2…/m*m-1*m-2……但是我们需要证明这个替换是不会改变最终结果的,而这样替换的原因是m*ans1可以直接就是m的整数倍,可以直接约分,最终实际变成ans1*ans2*ans3….%10的 last digit。

实际上这个替换的正确性基于如下两个保证:

首先:替换的时候要保证[(m-i)*ans1]% 10 = (n-i) %10,这样实际上可以保证(m*ans1)*(m-1*ans2)*(m-2*ans3)…与n*n-1*n-2…结果的last digit是相同的

其次:当分子,分母的last digit最后一位确定之后,它们的除法结果的last digit也是确定了

这点可以通过,枚举证明,因为最后一位可能只有 1,3,7,9,如下:

当1为分子,则在可以整除的前提下,如下方程是只具有唯一解的

(1*x)%10=1 (3*x)%10=1 (7*x)%10=1 (9*x)%10=1 且 x <-{1,2,7,9}

当3为分子,则在可以整除的前提下,如下方程是只具有唯一解的

(1*x)%10=3 (3*x)%10=3 (7*x)%10=3 (9*x)%10=3  且 x <-{1,2,7,9}

当7,9为分子是也是唯一的,这就说明了如果分子最后一位为x,分母最后一位为y,因为已经保证整除,这时我们就能确定最后的除法结果的最后一位。

所以我们只要在对分子扩大时,只要保证最终的结果与未扩大时的last digit相同,同时保证能继续整除分母就可以了

You Might Also Like