n次中有c个连续同样点数的扔法总数是
$$P(n,c)=\binom{n-1}{c}\cdot5^{n-c-1}\cdot6,$$
这是因为需要在$n-1$个位置中选出c个作为出现连续同样点数的位置，每个连续同样点数都有6种可能，而其他位置的点数因为要与前一个位置相异所以只有5种可能。从而
$$C(n)=\sum_{c=0}^{\pi(n)}\binom{n-1}{c}\cdot5^{n-c-1}\cdot6=\begin{cases}6C(n-1)+5B(n-1,\pi(n)) & n\text{为素数} \\ 6C(n-1)-B(n-1,\pi(n)) & n\text{为合数} \end{cases}.$$
递推计算即得结果$653972374$。
注：因组合数模余的计算中需要使用sympy求乘法逆，以下代码为Python 3，其中还打印了进度信息。
import sympy,math
target=50000000
mod=10**9+7
tick=target//100
P=[1-i%2 for i in range(target-2)]
for i in range(3,math.isqrt(target+1)+1,2):
if P[i-3]:
for j in range(2*i-3,len(P),i):
P[j]=0
print("initialization completed, start checking...")
d,c,s,x=1,36,42,6
for n,p in enumerate(P,start=3):
c=(c*6-x)%mod
if p:
d+=1
x=(x*(n-1)*sympy.mod_inverse(d,mod))%mod
c=(c+x)%mod
else:
x=(x*(n-1)*sympy.mod_inverse(n-1-d,mod)*5)%mod
s=(s+c)%mod
if n%tick==0:
print(n//tick,"percent completed, current sum:",s)
print(s)
|
