ARC 067 E - Grouping

題面在這裡！

    很顯然是個暴力dp。

    我們先枚舉一下 隊伍人數的種類，然後再逆序枚舉一下dp數組裡的總人數(順序就會算重)，最後枚舉一下這種隊伍的數量，之後就可以O(1)算方案了。

    具體的，O(1)算方案可以推一推組合，發現是 (總人數!)/((該種隊伍人數!　)^隊伍數量 * (總人數-該隊伍人數*隊伍數量)! * (隊伍數量)!)。

    之是以最後還要除以一個隊伍數量的階乘是因為，隊伍直接是無序的，比如(1 2)(3 4) 和 (3 4)(1 2)就是一種。

    看起來是O(n^3)的？

    讓我們取一下極限資料算一算(n=1000,a=1,b=1000,c=1,d=1000)，

    發現每種總人數對應的被算次數是一個調和級數，是以這個代碼的複雜度其實是 O(n^2 log n)。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1005,ha=1e9+7;

inline int add(int x,int y){ x+=y; return x>=ha?x-ha:x;}
inline void ADD(int &x,int y){ x+=y; if(x>=ha) x-=ha;}

inline int ksm(int x,int y){
	int an=1;
	for(;y;y>>=1,x=x*(ll)x%ha) if(y&1) an=an*(ll)x%ha;
	return an;
}

int jc[N],ni[N],f[N],n,a,b,c,d,ans,inv[N];

inline void init(){
	jc[0]=1;
	for(int i=1;i<=n;i++) jc[i]=jc[i-1]*(ll)i%ha;
	ni[n]=ksm(jc[n],ha-2);
	for(int i=n;i;i--) ni[i-1]=ni[i]*(ll)i%ha;
}

inline void dp(){
	f[0]=1;
	for(int i=a;i<=b;i++) // 最外層枚舉 隊伍的人數 
	    for(int m=i*c,j=min(i*d,n);j>=m;j--) // 第二層枚舉 已經選好的人數
		    for(int k=c,now=ksm(ni[i],c),M=j-c*i;k<=d&&M>=0;k++,M-=i,now=now*(ll)ni[i]%ha)
		        /* 第三層枚舉 這種人數的隊伍選幾個*/
				ADD(f[j],jc[j]*(ll)now%ha*(ll)ni[M]%ha*(ll)f[M]%ha*(ll)ni[k]%ha);
}

int main(){
	scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
	init(),dp(),printf("%d\n",f[n]);
	return 0;
}
      

我愛學習，學習使我快樂