求助dalao们，51nod1170实在是不会了，有没有大佬讲一下，有兴趣的可以告诉我，我提供AC代码。
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Numerics; namespace Problem51Nod
{
class Program
{
public static void Main(String[] args)
{
//BigInteger m = BigInteger.Pow(5, 143) - 1;
//BigInteger n = BigInteger.Pow(2, 331) + 1;
//int k = 100;
BigInteger m = BigInteger.Parse(Console.ReadLine());
BigInteger n = BigInteger.Parse(Console.ReadLine());
int k = Convert.ToInt32(Console.ReadLine()); //Stopwatch timer = new Stopwatch();
//timer.Start();
Console.WriteLine(Cmn(m, n, k));
//timer.Stop();
//Console.WriteLine(timer.Elapsed);
} static BigInteger[][] PowerTable = new BigInteger[][];
static List<BigInteger[][]>[] PreTable = new List<BigInteger[][]>[];
static BigInteger[,] CMatrix; static void InitCMatrix(int l)
{
CMatrix = new BigInteger[l + , l + ];
for (int i = ; i <= l; i++)
CMatrix[i, ] = CMatrix[i, i] = ; for (int i = ; i <= l; i++)
for (int j = ; j * <= i; j++)
CMatrix[i, j] = CMatrix[i, i - j] = CMatrix[i - , j - ] + CMatrix[i - , j];
} static void InitPowerTab(int l, int p)
{
PowerTable[p] = new BigInteger[l + ];
PowerTable[p][] = ; for (int j = ; j < PowerTable[p].Length; j++)
PowerTable[p][j] = PowerTable[p][j - ] * p;
} static void InitData(int l, BigInteger max, int p)
{
PreTable[p] = new List<BigInteger[][]>();
BigInteger[] pre = MulTo(l, p);
BigInteger[,] cMatrix = new BigInteger[l + , l + ]; for (int i = ; i <= l; i++)
for (int j = ; j <= i; j++)
cMatrix[i, j] = CMatrix[i, j]; int power = ;
for (BigInteger i = p; i <= max; i *= p)
{
BigInteger[][] cTable = new BigInteger[p - ][];
cTable[] = pre;
for (int j = ; j < p; j++)
{
BigInteger[] next = ReplaceWith(cTable[], i * j % PowerTable[p][l], l, p, cMatrix); if (j < p - )
cTable[j] = MulMod(cTable[j - ], next, l, p);
else
pre = MulMod(cTable[j - ], next, l, p);
} PreTable[p].Add(cTable);
power++;
}
} static BigInteger Cmn(BigInteger m, BigInteger n, int l)
{
InitCMatrix(l);
InitPowerTab(l, );
InitPowerTab(l, );
BigInteger up5 = CalP(m, n, , l);
BigInteger up2 = CalP(m, n, , l);
BigInteger mod = ((up5 - up2) + PowerTable[][l]) % PowerTable[][l];
mod = IMod(PowerTable[][l], mod, PowerTable[][l]) * PowerTable[][l] + up2;
return mod;
} static BigInteger CalP(BigInteger m, BigInteger n, int p, int l)
{
BigInteger count = Count(m, p) - Count(n, p) - Count(m - n, p);
if (count > l) return ;
InitData(l, m, p);
BigInteger up = Cal(m, p, l) * PowerTable[p][(int)count];
BigInteger down = Cal(n, p, l);
down *= Cal(m - n, p, l);
down %= PowerTable[p][l];
up = IMod(down, up, PowerTable[p][l]);
return up;
} static BigInteger Count(BigInteger v, BigInteger mod)
{
BigInteger count = ; while (v > )
{
v /= mod;
count += v;
} return count;
} static List<BigInteger> Values = new List<BigInteger>();
static List<int> Mods = new List<int>(); static BigInteger Cal(BigInteger nums, int p, int l)
{
BigInteger numsBak = nums;
Values.Clear();
Mods.Clear(); while (numsBak > )
{
Values.Add(numsBak);
Mods.Add((int)(numsBak % p));
numsBak /= p;
} BigInteger result = ; for (int i = ; i < Values.Count; i++)
{
result *= CalSingle(i, p, l);
result %= PowerTable[p][l];
} return result;
} static BigInteger CalSingle(int cIndex, int p, int l)
{
int len = Mods[cIndex];
BigInteger sum = , last = (Values[cIndex] - len) % PowerTable[p][l];
BigInteger[] pre = new BigInteger[] { };
BigInteger result = ;
cIndex++; for (int i = Mods.Count - ; i >= cIndex; i--)
{
int index = Mods[i]; if (index > )
{
BigInteger modValue = , current = ;
foreach (var item in PreTable[p][i - cIndex][index - ])
{
if (item != )
current = (current + modValue * item) % PowerTable[p][l]; if (sum == || modValue == )
break; modValue = modValue * sum % PowerTable[p][l];
} if (i - cIndex + <= l)
sum = (sum + index * PowerTable[p][i - cIndex + ]) % PowerTable[p][l]; result = (result * current) % PowerTable[p][l];
}
} for (int i = ; i <= len; i++)
{
if (i % p == )
continue; result *= last + i;
result %= PowerTable[p][l];
} return result;
} static BigInteger[] MulTo(int l, int p)
{
BigInteger[] result = new BigInteger[] { }; for (BigInteger i = ; i < p; i++)
{
if (i % p == )
continue; BigInteger[] b = new BigInteger[] { i, };
result = MulMod(result, b, l, p);
} return result;
} static BigInteger[] MulMod(BigInteger[] a, BigInteger[] b, int l, int p)
{
int len = Math.Min(l + , a.Length + b.Length - );
BigInteger[] result = new BigInteger[len]; for (int i = ; i < Math.Min(a.Length, l + ); i++)
{
if (a[i] == )
continue; int upper = Math.Min(b.Length, l - i + );
for (int j = ; j < upper; j++)
result[i + j] += a[i] * b[j];
} int last = ; for (int i = ; i < result.Length; i++)
{
result[i] %= PowerTable[p][l - i];
if (result[i] > )
last = i + ;
} if (last < result.Length)
Array.Resize(ref result, last); return result;
} //2次方算法，考虑大数是3次方 除以大进制的常数
static BigInteger[] ReplaceWith(BigInteger[] source, BigInteger into, int l, int p, BigInteger[,] cMatrix)
{
int len = source.Length;
len = Math.Min(len, l + );
BigInteger[] result = new BigInteger[len];
BigInteger[] power = new BigInteger[len];
power[] = ; for (int i = ; i < len; i++)
power[i] = power[i - ] * into % PowerTable[p][l]; for (int i = ; i < len; i++)
{
if (source[i] == )
continue; for (int j = ; j <= i; j++)
{
if (power[i] == ) continue;
var tmp = power[i - j] * source[i] % PowerTable[p][l - j];
if (tmp == ) continue;
result[j] += tmp * cMatrix[i, j];
}
} for (int i = ; i < result.Length; i++)
result[i] %= PowerTable[p][l - i]; return result;
} public static BigInteger EuclidExtend(BigInteger X, BigInteger Y, out BigInteger A, out BigInteger B)
{
if (Y == ) { A = ; B = ; return X; }
BigInteger quotient = X / Y;
BigInteger gcd = EuclidExtend(Y, X - Y * quotient, out A, out B);
BigInteger Temp = A; A = B; B = Temp - quotient * A;
return gcd;
} public static bool Linear(BigInteger X, BigInteger Y, BigInteger N, out BigInteger xResult, out BigInteger yResult)
{
BigInteger gcd = EuclidExtend(X, Y, out xResult, out yResult);
if (N % gcd != ) { return false; }
xResult = xResult * N / gcd % Y;
xResult = xResult >= ? xResult : xResult + Y;
yResult = yResult * N / gcd % X;
yResult = yResult <= ? yResult : yResult - X;
return true;
} public static BigInteger IMod(BigInteger A, BigInteger B, BigInteger P)
{
BigInteger x, y;
Linear(A, P, B, out x, out y);
return x;
}
}
}