2013-C22-team5

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
C题，碳的同分异构体个数。

Solution:
问题即为求度数不超过4的无根树的个数。

令f[i][j][k]表示最大子树的size不超过i，自身的size为j，根节点度数为k的有根树的个数。
所以可以得到递推关系：
    f[i][j][k] = sum { f[i-1][j-i*r][k-r] * C(s[i]+r-1,r) } ( 0 <= r <= k && i*r <= j )
其中s[i]表示大小为i的且度数不超过3的有根树的个数，即sum{f[i-1][i][k]}( 0 <= k <= 3 );

树的重心定义：以该点为根的树，其所有子树的size不会超过其自身size的一半。

因为以树的重心为根节点可以唯一确定一颗无根树。

所以当n为奇数时, res = sum{f[n/2][n][k]} ( 1 <= k <= 4 )

但是当n为偶数时，按上式求出的res中的一些树会存在两个重心，所以这些树可能会被重复计算两次。
出现这种情况当且仅当整棵树可以被划分成size为n/2的两个部分，他们通过一条边相连。
令s0 = sum{f[n/2-1][n][k]} (1 <= k <= 3)
所以答案需要减去 s0*(s0-1)/2 
（如果划分的这两个部分形状相同的话，分别以这两个重心构成的有根树形状也是相同的，所以在初始的res内只会被计算一次，故这种情况不会被重复计算）


Code:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
typedef pair <int, int> PII;
const int INF=10000007;
const int MN=105;
LL f[MN][MN][MN],s[MN];

LL comb(LL n, LL m){
    long double res=1;
    for (LL i=n-m+1; i<=n; i++) res*=i;
    for (LL i=2; i<=m; i++) res/=i;
    return LL(res+0.5);
}

int main(){
    LL n,i,j,k,r;
    cin >> n;
    f[0][1][0]=1; s[1]=1;
    for (i=1; i<=n; i++){
        for (j=1; j<=n; j++){
            for (k=0; k<=4; k++)
                for (r=0; r<=k && r*i<j; r++)
                    f[i][j][k]+=f[i-1][j-r*i][k-r]*comb(s[i]+r-1,r);
        }
        for (k=1; k<=3; k++) s[i+1]+=f[i][i+1][k];
    }
    LL ans=0,tmp=0;
    if (n%2)
        for (i=0; i<=4; i++) ans+=f[n/2][n][i];
    else{
        for (i=0; i<=4; i++) ans+=f[n/2][n][i];
        for (i=1; i<=3; i++) tmp+=f[n/2-1][n/2][i];
        ans-=tmp*(tmp-1)/2;
    }
    cout << ans << endl;
    return 0;
}

}}}

C题，碳的同分异构体个数。
Solution:
问题即为求度数不超过4的无根树的个数。
令f[i][j][k]表示最大子树的size不超过i，自身的size为j，根节点度数为k的有根树的个数。
所以可以得到递推关系：
    f[i][j][k] = sum { f[i-1][j-i*r][k-r] * C(s[i]+r-1,r) } ( 0 <= r <= k && i*r <= j )
其中s[i]表示大小为i的且度数不超过3的有根树的个数，即sum{f[i-1][i][k]}( 0 <= k <= 3 );
树的重心定义：以该点为根的树，其所有子树的size不会超过其自身size的一半。
因为以树的重心为根节点可以唯一确定一颗无根树。
所以当n为奇数时, res = sum{f[n/2][n][k]} ( 1 <= k <= 4 )
但是当n为偶数时，按上式求出的res中的一些树会存在两个重心，所以这些树可能会被重复计算两次。
出现这种情况当且仅当整棵树可以被划分成size为n/2的两个部分，他们通过一条边相连。
令s0 = sum{f[n/2-1][n][k]} (1 <= k <= 3)
所以答案需要减去 s0*(s0-1)/2 
（如果划分的这两个部分形状相同的话，分别以这两个重心构成的有根树形状也是相同的，所以在初始的res内只会被计算一次，故这种情况不会被重复计算）
Code:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
typedef pair <int, int> PII;
const int INF=10000007;
const int MN=105;
LL f[MN][MN][MN],s[MN];
LL comb(LL n, LL m){
    long double res=1;
    for (LL i=n-m+1; i<=n; i++) res*=i;
    for (LL i=2; i<=m; i++) res/=i;
    return LL(res+0.5);
}
int main(){
    LL n,i,j,k,r;
    cin >> n;
    f[0][1][0]=1; s[1]=1;
    for (i=1; i<=n; i++){
        for (j=1; j<=n; j++){
            for (k=0; k<=4; k++)
                for (r=0; r<=k && r*i<j; r++)
                    f[i][j][k]+=f[i-1][j-r*i][k-r]*comb(s[i]+r-1,r);
        }
        for (k=1; k<=3; k++) s[i+1]+=f[i][i+1][k];
    }
    LL ans=0,tmp=0;
    if (n%2)
        for (i=0; i<=4; i++) ans+=f[n/2][n][i];
    else{
        for (i=0; i<=4; i++) ans+=f[n/2][n][i];
        for (i=1; i<=3; i++) tmp+=f[n/2-1][n/2][i];
        ans-=tmp*(tmp-1)/2;
    }
    cout << ans << endl;
    return 0;
}