Submission #745271

#	Time	Username	Problem	Language	Result	Execution time	Memory
745271		sword060	Magneti (COCI21_magneti)	C++17	0 / 110	1068 ms	234372 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int N=10005,M=1e9+7;
long long add(long long a,long b){
	return (a+b)-(a+b>=M)*M;
}
long long mul(long long a,long long b){
	return (a*b)%M;
}
int x,k,a[N],ncr[N][N],fact[N];
int main(){
  ios::sync_with_stdio(0);cin.tie(0);
  cin>>x>>k;
  bool f=1;
  for(int i=1;i<=x;i++)cin>>a[i],f&=(a[i]==a[1]);
  fact[0]=1;
  for(int i=1;i<=x;i++)fact[i]=mul(fact[i-1],i);
  for(int i=0;i<=k;i++){
  	for(int j=0;j<=i;j++){
  		if(i==j||j==0)ncr[i][j]=1;
  		else ncr[i][j]=add(ncr[i-1][j],ncr[i-1][j-1]);
  	}
  }
  if(!f){
   long long sum=0,m=1,cnt=1;
   sort(a+1,a+x+1);
   for(int i=2;i<=x;i++){
   	if(a[i]==a[i-1])cnt++;
   	else{
   		m=mul(m,fact[cnt]);
   		cnt=1;
   	}
   }
   m=mul(m,fact[cnt]);
   do{
   	long long taken=1;
   	for(int i=2;i<=x;i++)
   		taken+=max(a[i-1],a[i]);
   	if(taken>k)continue;
   	sum=add(sum,mul(ncr[k][taken],m));
   }while(next_permutation(a+1,a+x+1));
   cout<<sum<<"\n";
  }else{
  	if(a[1]*x>k)cout<<0;
    else cout<<mul(ncr[k][k-a[1]*x],fact[x]);
  }
  return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 50