cf 869c The Intriguing Obsession

题意：有三种三色的岛，用a,b,c来标识这三种岛。然后规定，同种颜色的岛不能相连，而且同种颜色的岛不能和同一个其他颜色的岛相连。问有多少种建桥的方法。

题解：em....dp。我们先看两个岛之间怎么个连法。由题意可得岛与岛之间的链接是单射，我们定义f[a][b],表示有a个颜色1的岛和b个颜色2的岛想连的方案数。

首先当a==1 || b==1的时候 f[a][b]=（b+1）或者 (a+1)。然后尝试去找状态转移方程，我们对一个岛去连接另一个岛只有连或者不连两种状态，那么对于不连的状态为f[a-1][b];连的状态为b*f[a-1][b-1],这里要乘上一个b，因为有b个岛可连。

ac代码：

#include <cstdio>

#include <iostream>

#include <cstring>

#include <algorithm>

#define mt(a) memset(a,0,sizeof(a))

#include <map>

#include <string>

#include <queue>

#include <stack>

#include <cmath>

using namespace std;

typedef long long ll;

ll mod=;

ll f[][];

int main()

{

    ll a,b,c;

    cin>>a>>b>>c;

    int mx=max(a,max(b,c));

    mt(f);

    for(int i=;i<=mx;i++)

    {

        f[i][]=i+;

        f[][i]=i+;

    }

    for(int i=;i<=mx;i++)

    {

        for(int j=;j<=mx;j++)

        {

            f[i][j]=(j*f[i-][j-]+f[i-][j])%mod;

        }

    }

    ll ans=;

    ans=(ans*f[a][b])%mod;

    ans=(ans*f[a][c])%mod;

    ans=(ans*f[b][c])%mod;

    cout<<ans<<endl;

    return ;

}

巴特西

cf 869c The Intriguing Obsession

最新文章

热门文章