本题的策略与上一题完全相同，记$f(i,j)$为前i个数组成的集合中和模250余j的子集总数，则有初值$f(0,0)=1$（空集），$f(0,k)=0$ ($k\neq0$)，以及递推式
$$f(i,j)=f(i-1,j)+f(i-1,j-i^i \bmod 250),$$
等式右侧的两项分别对应子集中不含$i^i$和包含$i^i$的情况，用快速幂计算$i^i$，最终结果是$f(250250,0)-1=1425480602091519$（减1是因为需要排除空集的情况）。
m=250
n=10**16
def qp(a,b):
if b < 10:
return pow(a,b,m)
else:
c=qp(a,b/2)
return (c*c*a)%m if b%2>0 else (c*c)%m
f=[0]*250
f[0]=1
for i in range(1,250251):
f=[(f[j]+f[(j-qp(i,i))%m])%n for j in range(250)]
if i%2502==0:print "progress:",i/2502,"percent"
print f[0]-1
|
