这道题就是AcWing308,在书上337页。
338页底下的求G的式子中第二个求和的范围是否该改为0~j或0~min(j,p)? G[i,j,k]=∑p=1i∑q=0kF[p,q]∗Ci−1p−1∗p∗G[i−p,j−q,k−1]G[i,j,k]=\sum_{p=1}^i\sum_{q=0}^kF[p,q]*C_{i-1}^{p-1}*p*G[i-p,j-q,k-1]G[i,j,k]=∑p=1i∑q=0kF[p,q]∗Ci−1p−1∗p∗G[i−p,j−q,k−1] k的含义是连通块个数,q是当前连通块里各边的数量,这两个应该没有关系。
包括题解使用的范围也是0~j,第一篇题解把G的后两位翻转后对应的也是0~j。