LTC-男人八题之二：古老的取石子游戏

勇气的挑战

LTC-男人八题之一：连通图

<pre><code>&#x27;&#x27;&#x27; 1) n个节点的无向图的形态有S(n) = 2^C(n,2)种，假设其中连通图的种类有L(n)种，非连通图的种类有F(n)种，则L(n) = S(n) - F(n) 2) 求F(n)，对于任意一个节点A来说，A的连通形态可能为与1到(n-1)个 a. 为1时，其他(n-1)个节点为任意形态，则此时非连通图的种类为S(n-1); b. 为2时，任选一个节点与A连通，其他n-2个节点为任意形态，此时非连通图的种类为C(n-1, 1)*L(2)*S(n-2) c. 为k时，1&lt;=k&lt;=n-1，此时非连通图的种类为C(n-1, k-1)*L(k)*S(n-k) d. 以上相加，即为F(n) &#x27;&#x27;&#x27; # 组合函数计算，从n个里面取k个，有多少种取法，用公式计算 def C(n, k): m = min(k, n - k) f = 1 for i in range(m): f *= n n -= 1 return f // math.factorial(m) # 定义S(n)为n个节点的无向图的形态总数，L(n)为n个节点连通图的总数，依次求L[i] S = [0, 1] + [2 ** C(_, 2) for _ in range(2, n + 1)] L = [0, 1] for i in range(2, n + 1): f_i = 0 for k in range(1, i): f_i += C(i - 1, k - 1) * L[k] * S[i - k] l_i = S[i] - f_i L.append(l_i) print(L[-1])</code></pre>

看解题报告

联通=所有图-非联通非联通要这样看，先选一个点A，与剩下N-1个点分开要么点A自己一组，剩下N-1个点随意组合（所有图），要么从N-1里选X个点，和A一组，成为X+1个点的联通，同时没和A一组的N-X个点随意（所有图）这X显然可以从0取到N-1，作和，就是所有非联通 T=[0,1] &nbsp; #所有图 F=[0,0] &nbsp; #非联通 L=[0,1] &nbsp; #联通 &nbsp; L=T-F def C(a,b): &nbsp; &nbsp; c=1 &nbsp; &nbsp; for i in range(b): &nbsp; &nbsp; &nbsp; &nbsp; c=c*(a-i) &nbsp; &nbsp; for i in range(1,b+1): &nbsp; &nbsp; &nbsp; &nbsp; c=c/i &nbsp; &nbsp; return c &nbsp; &nbsp;&nbsp; def lian(n): &nbsp; &nbsp; if n&lt;=1: &nbsp; &nbsp; &nbsp; &nbsp; return L[n] &nbsp; &nbsp; else: &nbsp; &nbsp; &nbsp; &nbsp; for i in range(2,n+1): &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; T.append(2**C(i,2)) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; s=0 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for j in range(0,i-1): &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; s=s+C(i-1,j)*L[j+1]*T[i-1-j] &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; F.append(s) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; L.append(T[i]-F[i]) &nbsp; &nbsp; &nbsp; &nbsp; return L[-1] print lian(n)

递推公式  总是想错

<div style="top: 0px;">﻿﻿</div>def jiecheng(n): &nbsp;&nbsp;&nbsp; m=int(n) &nbsp;&nbsp;&nbsp; p=1 &nbsp;&nbsp;&nbsp; if m&gt;0: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for i in range(1,m+1): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; p=p*i &nbsp;&nbsp;&nbsp; return pdef C(n,k): &nbsp;&nbsp;&nbsp; return jiecheng(n)/(jiecheng(k)*jiecheng(n-k))&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; f=[0]*(n+1) g=[0]*(n+1) h=[0]*(n+1) for i in range(1,n+1): &nbsp;&nbsp;&nbsp; h[i]=2**(i*(i-1)/2) f[1]=1 g[1]=0 for i in range(2,n+1): &nbsp;&nbsp;&nbsp; s=0 &nbsp;&nbsp;&nbsp; for j in range(1,i): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; s=s+C(i-1,j-1)*f[j]*h[i-j] &nbsp;&nbsp;&nbsp; g[i]=s &nbsp;&nbsp;&nbsp; f[i]=h[i]-sprint(int(f[n]))&nbsp;&nbsp;&nbsp;

一个无聊的解法，利用递推公式

主要思想：	补集转化、递归式应用、组合数学思路分析：	若不考虑连通性，则对于有n个点的任意图，有G(n)=2^C(n,&nbsp;2)种可能的形式。设答案F(n)，易知非连通图情况数T(n)=G(n)-F(n)。	于是我们考虑非连通图：对于结点1的连通块C,|Vc|=k。由于不连通,k&lt;n成立。则有C(n-1,k–1)种方法选择另k-1个结点与结点1组成C。故有C(n-1,k–1)*F(k)种方法组成C。剩下的结点任意组合即可。	综上所述，可建立递归式：F(n)=G(n)-sigma(for i in range(1,n);C(n-1,i-1)*F(i)*G(n-i))算法分析：	组合数C可利用C(m,n)=C(m-1,n-1)+C(m-1,n)预处理，复杂度O(n^2)	递归函数F可记忆化，整体复杂度O(n)	综上所述，算法时间复杂度为O(n^2)参考代码：C=[[0 for j in range(100)] for i in range(100)] F=[-1 for i in range(100)] def initC(m,n): &nbsp; &nbsp; global C &nbsp; &nbsp; for i in range(m+1): &nbsp; &nbsp; &nbsp; &nbsp; C[i][i]=1 &nbsp; &nbsp; &nbsp; &nbsp; C[i][0]=1 &nbsp; &nbsp; for i in range(1,m+1): &nbsp; &nbsp; &nbsp; &nbsp; for j in range(1,n+1): &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; C[i][j]=C[i-1][j-1]+C[i-1][j] def g(n): &nbsp; &nbsp; global C &nbsp; &nbsp; return 1&lt;&lt;C[n][2] def f(n): &nbsp; &nbsp; global F &nbsp; &nbsp; if F[n]&gt;-1: &nbsp; &nbsp; &nbsp; &nbsp; return F[n] &nbsp; &nbsp; global C &nbsp; &nbsp; tmp=0 &nbsp; &nbsp; for i in range(1,n): &nbsp; &nbsp; &nbsp; &nbsp; tmp+=C[n-1][i-1]*f(i)*g(n-i) &nbsp; &nbsp; F[n]=g(n)-tmp &nbsp; &nbsp; return F[n] if __name__==&quot;__main__&quot;: &nbsp; &nbsp; n=input() &nbsp; &nbsp; initC(n,n) &nbsp; &nbsp; print f(n)

第106题：LTC-男人八题之一：连通图

矩形覆盖

序列判断

National Day

光棍的悲伤