• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            隨筆 - 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 英雄哪里出來 閱讀(903) 評論(0)  編輯 收藏 引用 所屬分類: 數學

            国产精品久久久久久久久软件| 久久国产精品77777| 天天综合久久久网| 国产精品熟女福利久久AV| 久久九九久精品国产免费直播| 久久午夜免费视频| 久久精品国产亚洲AV大全| 国产精品热久久毛片| 99久久做夜夜爱天天做精品| www.久久热| 色偷偷91久久综合噜噜噜噜| 亚洲精品高清国产一线久久| 国产一区二区精品久久凹凸 | 欧美伊香蕉久久综合类网站| 精品久久人人做人人爽综合 | 国产精品99久久久久久宅男| 久久久中文字幕日本| 久久精品国产亚洲AV无码偷窥| 久久精品国产精品亚洲下载| 亚洲国产美女精品久久久久∴| 国产精品热久久毛片| 粉嫩小泬无遮挡久久久久久| 色综合合久久天天给综看| 久久免费视频网站| 久久精品国产亚洲av高清漫画| 色青青草原桃花久久综合| 91精品国产91久久久久久| 国产精品久久久久jk制服| 久久AV无码精品人妻糸列| 日韩中文久久| 精品久久久久久久久久中文字幕| 精品久久久久香蕉网| 成人免费网站久久久| 久久综合给合久久狠狠狠97色69| 一日本道伊人久久综合影| 久久久久亚洲av成人无码电影| 国产精品免费看久久久香蕉| 亚洲国产精久久久久久久| 欧美一区二区精品久久| 亚洲一本综合久久| 亚洲精品高清久久|