|
|
題目鏈接：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/b * 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, 0, sizeof(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;
}
|