很显然是个暴力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)。
1#include<bits/stdc++.h> 2#define ll long long 3using namespace std; 4const int N=1005,ha=1e9+7; 5 6inline int add(int x,int y){ x+=y; return x>=ha?x-ha:x;} 7inline void ADD(int &x,int y){ x+=y; if(x>=ha) x-=ha;} 8 9inline int ksm(int x,int y){ 10 int an=1; 11 for(;y;y>>=1,x=x*(ll)x%ha) if(y&1) an=an*(ll)x%ha; 12 return an; 13} 14 15int jc[N],ni[N],f[N],n,a,b,c,d,ans,inv[N]; 16 17inline void init(){ 18 jc[0]=1; 19 for(int i=1;i<=n;i++) jc[i]=jc[i-1]*(ll)i%ha; 20 ni[n]=ksm(jc[n],ha-2); 21 for(int i=n;i;i--) ni[i-1]=ni[i]*(ll)i%ha; 22} 23 24inline void dp(){ 25 f[0]=1; 26 for(int i=a;i<=b;i++) // 最外层枚举 队伍的人数 27 for(int m=i*c,j=min(i*d,n);j>=m;j--) // 第二层枚举 已经选好的人数 28 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) 29 /* 第三层枚举 这种人数的队伍选几个*/ 30 ADD(f[j],jc[j]*(ll)now%ha*(ll)ni[M]%ha*(ll)f[M]%ha*(ll)ni[k]%ha); 31} 32 33int main(){ 34 scanf("%d%d%d%d%d",&n,&a,&b,&c,&d); 35 init(),dp(),printf("%d\n",f[n]); 36 return 0; 37}