这两天一直比较郁闷的在写上周日TJU比赛时候的G题和B题，G题比赛结束后就发现是一道很水的题，直接是二分+O(n)的扫瞄，结果我们当天两个队都是二分+线段树，直接导致TLE。后面的B题是个大组合数的计算，比较麻烦。今天终于在LUXU大牛的点拨之下AC掉了。下面说说解法。

    其实题目的意思就是给两个大整数n,m（1<=n，m <= 1^9），然后求组合数C[A,B] mod 10009的值,其中A= n-m*(m+1)/2 + m -1 , B = n - m*(m+1)/2。这里用到一个定理：

     设p为质数，a，b为两正整数，且a,b在p进制下表示为 a=(ak……,a0),b=(bk……,b0) 0=<ai,bi<p，证明 c[a,b]=c[ak,bk]*……*c[a0,b0](mod p)
  证： p为质数时，易证 (1+x)^p=1+x^p(mod p)
      (1+x)^a=(1+x)^(ak*p^k)……(1+x)^(a0) （mod p）
             =(1+x^(p^k))^ak……(1+x)^a0（mod p） （1）
       x^b在（1）右边式子的系数为c[ak,bk]*……*c[a0,b0]。
       从而得证 c[a,b]=c[ak,bk]*……*c[a0,b0](mod p)

根据以上的定理，我们把C[A,B]中的A，B写成10009进制的形式AsA(s-1)A(s-2)……A0,BsB(s-1)B(s-2)……B0(其实最多也就3位)，然后分别求组合数C[Ai,Bi],(0<=i <= s )，再做乘法。由于计算的组合数C[Ai,Bi]时，Ai和Bi的值可能在1^5左右，计算还是有一定问题。

    再利用组合公式C[n,m] = C[n,m-1] * (n - m +1 ) / m ，即可在O(m)的时间里求出。由于该公式涉及到除法取模，而且是对质数10009取模，那就可以通过乘法逆元来把除法转化为乘法。其理论基础就是：b‘是b的逆元，必有b*b'= 1 (mod p ) 。利用逆元，则a/b (mod p) == a * b' ( mod p )。这样可以先预处理 1 ~ 10008的模p逆元，然后计算组合数直接调用，这样这题的时间复杂都就能控制在O(k*10^5)了，还是比较理想的。

    仔细分析上面的解法，还有一些问题，那就是时间复杂度依赖于我们取模时的模数，当模数很大（10^7~10^9）【zoj3183】时，这个算法还是无能为力,希望大家提出更好的算法。