|
题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=2984
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*
题意:
给出一个长度为N(N <= 1000000)的串,要求求出所有串的不重复排列的方案。
输出方案数的最后一个非零位。
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
题解:
组合数学 + 数论
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
思路:
首先将所有字符归类,相同的放在一起计数,然后就是一个组合问题了,可以
想象成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匹配掉,多余部分再乘到答案上即可。
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <iostream>
#include <cstring>
#include <cstdio>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int hash[26];
char str[1000001];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int exp(int a, int b, int& x, int& y) {
int q;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int inv(int v, int m) {
int x, y;
exp(v, m, x, y);
return (x % m + m) % m;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) struct Triple {
int num2, num5, other_product;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) Triple() {
num2 = num5 = 0;
other_product = 1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) Triple(int _2, int _5, int _p) {
num2 = _2;
num5 = _5;
other_product = _p;
}
};
Triple tp[1000010];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) Triple Go(int n) {
return tp[n];
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int AccPro = 1;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) Triple C(int n, int m) {
Triple U, D[2];
U = Go(n);
D[0] = Go(m);
D[1] = Go(n - m);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
U.num2 -= D[0].num2 + D[1].num2;
U.num5 -= D[0].num5 + D[1].num5;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
AccPro = AccPro * D[0].other_product * D[1].other_product % 10;
return U;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) 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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int main() {
int i;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 2; i < 1000001; i++) {
tp[i] = tp[i-1];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int val = i;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(val % 2 == 0) {
val /= 2;
tp[i].num2 ++;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(val % 5 == 0) {
val /= 5;
tp[i].num5 ++;
}
tp[i].other_product *= val;
tp[i].other_product %= 10;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(scanf("%s", str) != EOF) {
memset(hash, 0, sizeof(hash));
int len = strlen(str);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 0; i < len; i++) {
hash[ str[i] - 'a' ] ++;
}
Triple ans;
AccPro = 1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 0; i < 26; i++) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
len -= hash[i];
}
}
AccPro = inv(AccPro, 10);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int as = 1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(ans.num2 < ans.num5) {
ans.num5 -= ans.num2;
as = ans.other_product * Binary(5, ans.num5, 10) * AccPro % 10;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else {
ans.num2 -= ans.num5;
as = ans.other_product * Binary(2, ans.num2, 10) * AccPro % 10;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf("%d\n", as);
}
return 0;
}
|