随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

ZJU 3108 Last Digit

题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=2984

/*
题意:
    给出一个长度为N(N <= 1000000)的串,要求求出所有串的不重复排列的方案。
输出方案数的最后一个非零位。

题解:
    组合数学 + 数论

思路:
    首先将所有字符归类,相同的放在一起计数,然后就是一个组合问题了,可以
想象成L个抽屉,然后一类一类插入,比如有A1个'a',那么就是C(L, A1)种方案,
还有L-A1个位置,继续下一步,如果有A2个'b'那么下一趟就是C(L-A1, A2)。将所
有的组合数相乘就是答案了。
    但是这题要求求的是答案的最后一个非零位,于是问题需要转化一下,每次不
能直接将C(n, m)求出来,可以这样想,导致一个数末几尾有0的条件是这个数中有
至少一对2和5,C(n, m) = n! / m! / (n-m)!,用F[x]来记录x的阶乘中 2和5的个
数以及其它数的乘积,那么就可以把C(n, m)中其它数的乘积求出来:
ans = X[n] * X[m] * Inv[ X[n-m] ];
其中X[v] 表示v的阶乘中其它数的乘积,Inv[v]表示v对于10的逆。
    所有的组合数求完之后,将剩下的2和5匹配掉,多余部分再乘到答案上即可。
*/



#include 
<iostream>
#include 
<cstring>
#include 
<cstdio>

using namespace std;

int hash[26];
char str[1000001];

int exp(int a, int b, int& x, int& y) {
    
int q;
    
if(b == 0{
        q 
= a; x = 1; y = 0;
        
return q;
    }

    q 
= exp(b, a%b, x, y);
    
int tmp = x;
    x 
= y;
    y 
= tmp - a/* y;
    
return q;
}


int inv(int v, int m) {
    
int x, y;
    exp(v, m, x, y);
    
return (x % m + m) % m;
}


struct Triple {
    
int num2, num5, other_product;
    Triple() 
{
        num2 
= num5 = 0;
        other_product 
= 1;
    }

    Triple(
int _2, int _5, int _p) {
        num2 
= _2;
        num5 
= _5;
        other_product 
= _p;
    }

}
;
Triple tp[
1000010];

Triple Go(
int n) {
    
return tp[n];
}


int AccPro = 1;

Triple C(
int n, int m) {
    Triple U, D[
2];
    U 
= Go(n);
    D[
0= Go(m);
    D[
1= Go(n - m);

    U.num2 
-= D[0].num2 + D[1].num2;
    U.num5 
-= D[0].num5 + D[1].num5;

    AccPro 
= AccPro * D[0].other_product * D[1].other_product % 10;
    
return U;
}


int Binary(int a, int b, int c) {
    
if(!b)
        
return 1 % c;
    
int tmp = Binary(a*a%c, b/2, c);
    
if(b & 1)
        tmp 
= tmp * a % c;
    
return tmp;
}


int main() {
    
int i;
    
for(i = 2; i < 1000001; i++{
        tp[i] 
= tp[i-1];

        
int val = i;
        
while(val % 2 == 0{
            val 
/= 2;
            tp[i].num2 
++;
        }

        
while(val % 5 == 0{
            val 
/= 5;
            tp[i].num5 
++;
        }

        
        tp[i].other_product 
*= val;
        tp[i].other_product 
%= 10;
    }


    
while(scanf("%s", str) != EOF) {
        memset(hash, 
0sizeof(hash));
        
int len = strlen(str);
        
for(i = 0; i < len; i++{
            hash[ str[i] 
- 'a' ] ++;
        }

        Triple ans;
        AccPro 
= 1;
        
for(i = 0; i < 26; i++{
            
if(hash[i]) {
                Triple X 
= C(len , hash[i]);
                
                ans.num2 
+= X.num2;
                ans.num5 
+= X.num5;
                ans.other_product 
= ans.other_product * X.other_product % 10;

                len 
-= hash[i];
            }

        }

        AccPro 
= inv(AccPro, 10);

        
int as = 1;

        
if(ans.num2 < ans.num5) {
            ans.num5 
-= ans.num2;
            
as = ans.other_product * Binary(5, ans.num5, 10* AccPro % 10;
        }
else {
            ans.num2 
-= ans.num5;
            
as = ans.other_product * Binary(2, ans.num2, 10* AccPro % 10;
        }



        printf(
"%d\n"as);
    }

    
return 0;
}

posted on 2011-04-15 14:19 英雄哪里出来 阅读(795) 评论(0)  编辑 收藏 引用 所属分类: 数学


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理