• <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)  編輯 收藏 引用 所屬分類: 數學

            一级女性全黄久久生活片免费| 色欲综合久久躁天天躁蜜桃| 亚洲成色999久久网站| 99热都是精品久久久久久| 久久亚洲2019中文字幕| 亚洲AV无码成人网站久久精品大| 97视频久久久| AA级片免费看视频久久| 久久午夜福利无码1000合集| 国产精品久久成人影院| 怡红院日本一道日本久久 | 久久精品欧美日韩精品| 久久久久久久尹人综合网亚洲 | 蜜臀久久99精品久久久久久小说 | 国产呻吟久久久久久久92| 久久人人添人人爽添人人片牛牛| 久久久精品免费国产四虎| 狠狠色婷婷久久一区二区| 久久精品国产亚洲Aⅴ香蕉 | 人人狠狠综合久久亚洲婷婷| 少妇人妻综合久久中文字幕| 久久国产成人| 久久综合综合久久狠狠狠97色88 | 9久久9久久精品| 国产69精品久久久久9999APGF| 久久亚洲国产精品123区| 久久777国产线看观看精品| 久久影院综合精品| 国内精品久久久久影院薰衣草 | 成人久久精品一区二区三区| 久久精品国产亚洲av麻豆图片| 久久综合视频网站| 久久久人妻精品无码一区| 99久久99久久精品国产片| 香蕉久久夜色精品国产小说| 91精品国产高清久久久久久io| 久久狠狠高潮亚洲精品| 久久综合给合久久狠狠狠97色69 | 久久强奷乱码老熟女网站| 亚洲色欲久久久久综合网| 狠狠色丁香久久婷婷综合_中|