HDU6279 Circular Coloring —— DP求环状黑白染色的方案数

This way

题意：

已知有m个黑球，n个白球，呈环状排列，如果一段球的颜色都相同，那么这段区间的值就是区间长度。这个环的值就是所有区间的相乘。问你所有可能的排列方法区间值的和。

题解：

dp[i][j]表示长度为j的时候分成i段的值，那么状态转移方程就是
$dp[i][j]$=${\sum }_{k=i-1}^{j-1}dp[i-1][k]\ast (j-k)$
$\to j\ast {\sum }_{k=i-1}^{j-1}dp[i-1][k]-{\sum }_{k=i-1}^{j-1}k\ast dp[i-1][k]$
那么我们在dp的时候弄两个前缀记录即可。
但是注意dp的时候会将不同顺序的相同结果记录下来，比如说3的时候，2 1与1 2是两个相同的结果，但是dp会记录两次，所以最后算的时候我们要/i但是不能直接除，要先预处理逆元再除。ans根据加法原理和乘法原理即可得出。由于它是一个环，所以最终的答案要乘上(n+m).

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
const int N=5e3+5;
ll dp[N][N],inv[N];
void init()
{
    inv[1]=1;
    for(int i=2;i<=5000;i++)
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    inv[0]=1;
    dp[0][0]=1;
    for(ll i=1;i<=5000;i++)
    {
        ll p1=dp[i-1][i-1],p2=(i-1)*dp[i-1][i-1];
        for(ll j=i;j<=5000;j++)
            dp[i][j]=(j*p1-p2+mod)%mod,p1=(p1+dp[i-1][j])%mod,p2=(p2+j*dp[i-1][j])%mod;
    }
}
int main()
{
    init();
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n<m)
            swap(n,m);
        ll ans=0;
        for(int i=1;i<=m;i++)
            ans=(ans+dp[i][n]*dp[i][m]%mod*inv[i])%mod;
        printf("%lldn",ans*(n+m)%mod);
    }
    return 0;
}

最后

以上就是搞怪鼠标最近收集整理的关于HDU6279 Circular Coloring —— DP求环状黑白染色的方案数的全部内容，更多相关HDU6279内容请搜索靠谱客的其他文章。