Submission #1102176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102176		quocthang	Zapina (COCI20_zapina)	C++14	110 / 110	269 ms	3668 KiB

zapina

#include <bits/stdc++.h>
#define base 31
#define fi first
#define endl "\n"
#define se second
#define NAME "FILE"
#define ll long long
#define int long long
#define mod 1000000007
#define pii pair<int,int>
#define bit(mask,i) (mask&(1<<i))
#define lcm(a,b) ((a*b)/__gcd(a,b))
#define turn_on(mask,i) (mask|(1<<i))
#define turn_off(mask,i) (mask^(1<<i))

template <class T1, class T2>
bool maximize(T1 &a, T2 b){if (a < b){a = b; return 1;} return 0;}

template <class T1, class T2>
bool minimize(T1 &a, T2 b){if (a > b){a = b; return 1;} return 0;}

template <class T1, class T2>
void add(T1 &a, T2 b){a += b; if (a >= mod) a -= mod;}

template <class T1, class T2>
void sub(T1 &a, T2 b){a -= b; if (a < 0) a += mod;}

using namespace std;
int dp[360][360][2];
int C[360][360];
int POW[360],n;
int lt(int a,int k){
	if(k==0)return 1;
	if(k==1)return a;
	int b=lt(a,k/2);
	(b*=b)%=mod;
	if(k&1)(b*=a)%=mod;
	return b;
}
// (n!)/(k!(n-k)!)
int c(int n,int k){
	if(k>n)return 0;
	if(C[n][k]!=-1)return C[n][k];
	int tmp=(POW[k]%mod*POW[n-k]%mod)%mod;
	 tmp=(POW[n]%mod*lt(tmp,mod-2)%mod+mod)%mod;
	 return C[n][k]=tmp;
}
int calc(int id,int job,bool is){
	if(!id)return is && job==0;
	if(dp[id][job][is]!=-1)return dp[id][job][is];
	int res=0;
	for(int i=0;i<=job;i++){
	 // cout<<job<<endl;
		add(res,calc(id-1,job-i,(i==id)||is)*c(job,i)%mod);
	}
	return dp[id][job][is]=res;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	if (fopen(NAME".inp","r")){
		freopen(NAME".inp","r",stdin);
		freopen(NAME".out","w",stdout);
	}
	POW[0]=1;
	for(int i=1;i<=350;i++)POW[i]=POW[i-1]*i%mod;
// 	for(int i=1;i<=350;i++)
// 		for(int j=1;j<=350;j++) C[i][j]=c(i,j)%mod;
	memset(dp,-1,sizeof dp);
	memset(C,-1,sizeof C);
	cin>>n;	
	cout<<calc(n,n,0);
}

Compilation message (stderr)

zapina.cpp: In function 'int main()':
zapina.cpp:62:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   freopen(NAME".inp","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
zapina.cpp:63:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |   freopen(NAME".out","w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 55 / 55