湘潭邀请赛 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 = ;

const int mod = 1e9+;

typedef long long ll;

int n, m;

ll f[N][N], b[N][N];

ll ans;

int main() {

        b[][] = ;

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

                ll sum = , res = ;

                for(int j = i; j <= ; j++) {

                        res = (res+b[i-][j-])%mod;

                        sum = (sum+res)%mod;

                        b[i][j] = sum;

                }

        }

        for(int i = ; i <= ; i++) f[][i] = (i*i)%mod;

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

                ll sum = , res = ;

                for(int j = i; j <= ; j++) {

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

                        sum = (sum+res)%mod;

                        f[i][j] = sum;

                }

        }

        while(~scanf("%d%d", &n, &m)) {

                ans = ;

                int up = min(m, n);

                for(int i = ; i <= up; i++) {

                        ans = (ans+f[i][n]*b[i][m]+f[i][m]*b[i][n])%mod;

                }

                printf("%lld\n", ans);

        }

}

巴特西

湘潭邀请赛 2018 D Circular Coloring

最新文章

热门文章