제출 #1094231

#제출 시각아이디문제언어결과실행 시간메모리
1094231vjudge1Magneti (COCI21_magneti)C++14
110 / 110
217 ms215252 KiB
#include<bits/stdc++.h> #define int long long const int N=2e5+1; const int mod=1e9+7; int fac[N],ifac[N],a[N]; int f[52][52][10001]; int qmi(int x,int y){ int res=1; while(y>0){ if(y&1) res=res*x%mod; x=x*x%mod; y>>=1; } return res; } void init(int x){ fac[0]=ifac[0]=1; for(int i=1;i<=x;i++) fac[i]=fac[i-1]*i%mod; ifac[x]=qmi(fac[x],mod-2); for(int i=x-1;i>=1;i--) ifac[i]=ifac[i+1]*(i+1)%mod; } inline int C(int n,int m){ return (n<m||n<0||m<0)?0:fac[n]*ifac[m]%mod*ifac[n-m]%mod; } inline void add(int &x,int y){ x+=y,x%=mod; } void solve(){ int n,m; std::cin>>m>>n; for(int i=1;i<=m;i++) std::cin>>a[i]; std::sort(a+1,a+m+1); memset(f,0,sizeof f); f[0][0][0]=1; for(int i=1;i<=m;i++){ for(int j=1;j<=i;j++) for(int k=1;k<=n;k++){ add(f[i][j][k],f[i-1][j-1][k-1]); if(k>=a[i]) add(f[i][j][k],f[i-1][j][k-a[i]]*j*2%mod); if(k>=2*a[i]-1) add(f[i][j][k],f[i-1][j+1][k-2*a[i]+1]*j*(j+1)%mod); } } int ans=0; for(int i=1;i<=n;i++){ ans=(ans+C(n-i+m,m)*f[m][1][i]%mod)%mod; } std::cout<<ans<<"\n"; } signed main(){ std::ios::sync_with_stdio(false),std::cin.tie(NULL),std::cout.tie(NULL); int t=1; // std::cin>>t; init(N-2); while(t--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...