|
|
题目链接：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;
}
|