$\quad $ 我在题库做题时被一道计数类DP的高精度恶心到了。本着能不打高精就不打的原则,我就用了 \(long \\\\double\) 来解决这个问题。
$\quad $ 但毕竟是浮点类型的,勾石精度真的很逆天。试了很久决定写 \(Python\) (doge)。
$\quad $ 就直接去学 \(Python\) 了,然后发现还是有丢失精度的问题。
$\quad $ 然后就解决了一下精度问题(还是逆天的浮点数运算),把所有的除法都改成地板除就好了(逆天地板除)
N=51
n=int(input())
fact=[0]*N
def C(n,m):
return fact[n]//fact[m]//fact[n-m]
def g(i):
return pow(2,i*(i-1)//2)
fact[0]=1
for i in range(1,N-1):
fact[i]=fact[i-1]*i
f=[0]*N
f[0]=1
f[1]=1
while n>0:
for i in range(2,n+1):
f[i]=g(i)
ans=0
for j in range(1,i):
ans=ans+f[j]*C(i-1,j-1)*g(i-j)
f[i]=f[i]-ans
print(int(f[n]))
n=int(input())
标签:int,Graph,range,Connected,ans,quad,fact
From: https://www.cnblogs.com/0shadow0/p/18242773