本题用到Lucas定理，即若p是素数则有
$$\binom{m}{n}=\prod_{i=0}^k\binom{m_i}{n_i} \pmod p,$$
其中
$$m=\sum_{i=0}^km_ip^i,\quad n=\sum_{i=0}^kn_ip^i,$$
是m、n在p进制下的表示，且为了记号的统一规定若$m_i < n_i$，则$\binom{m_i}{n_i}=0$。
因此第m行(m从0开始)中有$\prod_{i=0}^{k}(1+m_i)$项不能被p整除。
本题的最后一行是$m=10^9-1$，转换成7进制是33531600615。
不难看出在前$7^k$（即m从0至$7^k-1$)行中共有$(7(7+1)/2)^k=28^k$项不能被7整除，反复运用这一结论即可得结果$2129970655314432$。
def f(m,r):
return r*(m[0]+2)*(m[0]+1)/2 if len(m)==1 else r*((28**(len(m)-1))*(1+m[0])*m[0]/2+f(m[1:],m[0]+1))
print f([3,3,5,3,1,6,0,0,6,1,5],1)
|
