prime :array [1..4] of Longint=(2,3,5,7)；
var
a,c :array [0..100000] of Longint；
s :array [1..4,0..20] of Longint；
t :array [1..4] of Longint；
n,i,ans :Longint；
n1,n2 :Longint；
st :ansistring；
Procedure Getprime(n,p:Longint)；
var
i,j,k :Longint；
begin
while n>1 do
begin
for i:=1 to 4 do
while n mod prime[i]=0 do
begin
inc(t[i],p)；
n:=n div prime[i]；
end；
n:=n mod 10；
end；
end；
Procedure GetC(n:Longint)；
var
i,j,k :Longint；
begin
c[n]:=1；
for i:=1 to 4 do
begin
j:=0；
k:=t[i]；
while k>0 do
begin
if k mod 2=1 then
c[n]:=(c[n]*s[i,j]) mod 10；
k:=k shr 1；
inc(j)；
end；
end；
end；
Procedure Prepare；
var
i,j,k :Longint；
begin
for i:=1 to 4 do
begin
s[i,0]:=prime[i]；
for j:=1 to 20 do
s[i,j]:=sqr(s[i,j-1]) mod 10；
end；
c[0]:=1；c[n-2]:=1；
for i:=1 to n shr 1 do
begin
Getprime(n-i-1,1)；
Getprime(i,-1)；
GetC(i)；
c[n-i-2]:=c[i]；
end；
end；
Begin
readln(st)；
for i:=1 to length(st) do
if st[i] in [0..9] then
begin
inc(n)；
a[n]:=ord(st[i])-ord(0)；
end；
Prepare；
for i:=1 to n-1 do
n1:=(n1+a[i]*c[i-1]) mod 10；
for i:=2 to n do
n2:=(n2+a[i]*c[i-2]) mod 10；
ans:=n1*10+n2；
if ans=0 then ans:=100；
writeln(ans)；
End.
我不希望看到这题的通过人数飙升
实质上是排列组合，求组合数
容易证明
结果第一位数与前面 n-1 个数字有关（设它们为 a1..an-1)
为 (a1 * C(n - 2, 1) + a2 * C(n - 2, 2) + a3 * C(n - 2, 3) ... + an-1 * C(n - 2, n - 1)) mod 10
但是 n 可能比较大（100000），直接公式求肯定超时
不过这题很特殊，它只要组合数的个位数，我于是就用分解因数来加速，最后好像8个点（比裸加多一个）。
一直没想到什么好的求组合数个位数的方法，研究此程序中～
我原来裸求过100000的组合数，发现了个位数字的确很有规律（中间很多 0，而且结果中有很多对称（回文）的重复。
但查阅很多资料都未果～
因该是
(a1 * C(n - 2, 0) + a2 * C(n - 2, 1) + a3 * C(n - 2, 2) ... + an-1 * C(n - 2, n - 2)) mod 10
6 8 8 9 7
4 6 7 6
0 3 3
3 6
首先把数字放在格子的，第1行最后的3走到结果数字6（按题向下走一格向左走0或1格）需要走4行4列，这样它对结果数字个位的影响就是它走到6的方案数C（4，4），依次类推再找1行倒数第2个，结果中的个位就是（3*C（4，4）+4*C（4，3）+5*C（4，2）+3*C（4，1）+5*C（4，0））mod 10。依次类推算下面的吧！
结果的十位数：
(A(1)*C(n-1, 0)+A(2)*C(n-1, 1)+...+A(n-1)*C(n-1, n-2))MOD 10
结果的个位数：
(A(2)*C(n-1, 0)+A(3)*C(n-1, 1)+...+A(n)*C(n-1, n-2))MOD 10
求组合的公式：C(n, i)=C(n, i-1)*(n+1-i)DIV i
C(n, 0)=1
可是这里C(n, i)只能保留个位数，如果再按照这种方法计算的话会出问题！
怎么办？