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=998244353;
ll f[5010][5010];
int main()
{
    ll a,b,c;
    cin>>a>>b>>c;
    int mx=max(a,max(b,c));
    mt(f);
    for(int i=1;i<=mx;i++)
    {
        f[i][1]=i+1;
        f[1][i]=i+1;
    }
    for(int i=2;i<=mx;i++)
    {
        for(int j=2;j<=mx;j++)
        {
            f[i][j]=(j*f[i-1][j-1]+f[i-1][j])%mod;
        }
    }
    ll ans=1;
    ans=(ans*f[a][b])%mod;
    ans=(ans*f[a][c])%mod;
    ans=(ans*f[b][c])%mod;
    cout<<ans<<endl;
    return 0;
}      

轉載于:https://www.cnblogs.com/z1141000271/p/7637735.html