Description

Input

Output

Sample Input

10 113
28 3 39 90 46 14 55 35 48 47

Sample Output

62453

Data Constraint

Solution

• 時間復雜度 O(N2?k) 。

Code

#include<cstdio> #include<cstring> #include<algorithm> #define add(a,b) a=(a+b)%mo using namespace std; const int N=201,mo=1e9+7; int a[N]; long long ans; long long f[2][N][N*5]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } int main() {int n=read(),m=read(),p=0;for(int i=1;i<=n;i++) a[i]=read();sort(a+1,a+1+n);for(int i=f[0][0][0]=1;i<=n;i++){memset(f[p^=1],0,sizeof(f[p]));for(int j=0;j<=i;j++)for(int k=0,v;k<=m;k++)if(f[p^1][j][k]){if((v=(a[i]-a[i-1])*j+k)>m) break;add(f[p][j+1][v],f[p^1][j][k]);add(f[p][j][v],f[p^1][j][k]);if(j){add(f[p][j][v],f[p^1][j][k]*j%mo);add(f[p][j-1][v],f[p^1][j][k]*j%mo);}}}for(int k=0;k<=m;k++) add(ans,f[p][0][k]);printf("%lld",ans);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5436. 【NOIP2017提高A组集训10.30】Group的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。