给出 n n n个黑球， m m m个白球，并且 m , n ≤ 5000 m,n\leq5000 m,n≤5000。然后呈环状排列，相同的颜色看作连续的一段，答案是这些段的长度之积。求问所有可能的排列答案之和是多少。 最终构成环状的形态一定是白球和黑球都分成了 i i i段， i ≤ m i n ( n , m ) i\leq min(n,m) i≤min(n,m)。枚举最终分成了多少段，预处理出白球和黑球分成 i i i段的答案。那么 a n s = ( n + m ) ∑ i = 1 m i n ( n , m ) F i G i / i ans=(n+m)\sum\limits_{i=1}^{min(n,m)}F_iG_i/i ans=(n+m)i=1∑min(n,m)FiGi/i. 接下来要求 F i , G i F_i,G_i Fi,Gi，考虑 f i , j f_{i,j} fi,j表示前 j j j个数分成 i i i段的答案。 f i , j = ∑ k = i − 1 j − 1 f i − 1 , k ( j − k ) = j ∑ k = i − 1 j − 1 f i − 1 , k − ∑ k = i − 1 j − 1 k f i − 1 , k f_{i,j}=\sum\limits_{k=i-1}^{j-1}f_{i-1,k}(j-k)=j\sum\limits_{k=i-1}^{j-1}f_{i-1,k}-\sum\limits_{k=i-1}^{j-1}kf_{i-1,k} fi,j=k=i−1∑j−1fi−1,k(j−k)=jk=i−1∑j−1fi−1,k−k=i−1∑j−1kfi−1,k. 维护两个前缀和转移。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int mod=1e9+7; const int N=5e3+7; int f[N][N]; int inv[N]; int main() { inv[1]=1; for(int i=2;i<=5000;i++) inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod; f[0][0]=1; for(int i=1;i<=5000;i++) { int s1=f[i-1][i-1]; int s2=1LL*f[i-1][i-1]*(i-1)%mod; for(int j=i;j<=5000;j++) { f[i][j]=(1LL*s1*j%mod-s2+mod)%mod; s1+=f[i-1][j],s1%=mod; s2+=(1LL*j*f[i-1][j])%mod,s2%=mod; } } int n,m; while(scanf("%d%d",&n,&m)!=EOF) { int lim=min(n,m); int ans=0; for(int i=1;i<=lim;i++) { ans+=1LL*f[i][n]*f[i][m]%mod*inv[i]%mod; ans%=mod; } printf("%d\n",1LL*ans*(n+m)%mod); } return 0; }