湘潭邀请赛 2018 D Circular Coloring

题意：

　　给一个环，环上有n+m个点。给n个点染成B，m个点染成W。求所有染色情况的每段长度乘积之和。

题解：

　　染成B的段数和染成W的段数是一样的（因为是环）。

　　第一段是可以移动的，例如BBWWW移动为BWWWB。

　　所以处理两个方程：b[i][j]代表把j分成i段的乘积和且第一段不能移动；f[i][j]代表把j分成i段的乘积和且第一段可以移动。

　　那么枚举分成的段数，对于当前枚举分成i段，答案就为：f[i][n]*b[i][m]+f[i][m]*b[i][n].

　　问题是方程怎么转移了。

　　对于b[i][j]，枚举一个新加的数（1~j-i+1），即b[i][j] = 1*b[i-1][j-1]+2*b[i-1][j-2]+...+(j-i+1)*b[i-1][i-1].

　　对于f[i][j]，确定他的第一个数是什么，然后枚举一个新加的数，即f[1][i] = i*i（确定第一个数）；f[i][j] = 1*f[i-1][j-1]+2*f[i-1][j-2]+...+(j-i+1)*f[i-1][i-1].

　　HDU上建2个数组会MLE，所以只能在camp上过2个数组的。camp题目地址：https://www.icpc.camp/contests/6CP5W4knRaIRgU

#include <bits/stdc++.h>
using namespace std;
const int N = 5001;
const int mod = 1e9+7;
typedef long long ll;
int n, m;
ll f[N][N], b[N][N];
ll ans;
int main() {
        b[0][0] = 1;
        for(int i = 1; i <= 5000; i++) {
                ll sum = 0, res = 0;
                for(int j = i; j <= 5000; j++) {
                        res = (res+b[i-1][j-1])%mod;
                        sum = (sum+res)%mod;
                        b[i][j] = sum;
                }
        }
        for(int i = 1; i <= 5000; i++) f[1][i] = (i*i)%mod;
        for(int i = 2; i <= 5000; i++) {
                ll sum = 0, res = 0;
                for(int j = i; j <= 5000; j++) {
                        res = (res+f[i-1][j-1])%mod;
                        sum = (sum+res)%mod;
                        f[i][j] = sum;
                }
        }
        while(~scanf("%d%d", &n, &m)) {
                ans = 0;
                int up = min(m, n);
                for(int i = 1; i <= up; i++) {
                        ans = (ans+f[i][n]*b[i][m]+f[i][m]*b[i][n])%mod;
                }
                printf("%lld
", ans);
        }
}