oj.uz

Submission #212725

# Submission time Handle Problem Language Result Execution time Memory
212725 2020-03-24T07:50:50 Z dorijanlendvaj 마스코트 (JOI13_mascots) C++14
100 / 100
 439 ms 104452 KB 
//DUEL
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#pragma GCC optimize("unroll-loops")
#define shandom_ruffle(a, b) shuffle(a, b, rng)
#define vi vector<int>
#define vl vector<ll>
#define popcnt __builtin_popcount
#define popcntll __builtin_popcountll
#define all(a) begin(a),end(a)

using namespace std;
using namespace __gnu_pbds;

using ll=long long;
using ull=unsigned long long;
using ld=long double;
int MOD=1000000007;
int MOD2=998244353;
vector<int> bases;
const ll LLINF=1ll<<60;
const char en='\n';

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void yes() {cout<<"YES"<<en; exit(0);}
void no() {cout<<"NO"<<en; exit(0);}
inline int rund() {int x576363482791fuweh=rng();return abs(x576363482791fuweh)%RAND_MAX;}
template<class T>
void prVec(vector<T> w,bool fl=false)
{
	cout<<w.size()<<en;
	for (int i=0;i<int(w.size())-1;++i) cout<<w[i]<<' ';
	if (w.size()) cout<<w[w.size()-1]<<en;
	if (fl) cout<<flush;
}

void M998()
{
	swap(MOD,MOD2);
}

ll raand()
{
	ll a=rund();
	a*=RAND_MAX;
	a+=rund();
    return a;
}

#define rand raand

ll raaand()
{
	return raand()*(MOD-7)+raand();
}

string to_upper(string a)
{
	for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A';
	return a;
}

string to_lower(string a)
{
	for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A';
	return a;
}

ll sti(string a,int base=10)
{
	ll k=0;
	for (int i=0;i<(int)a.size();++i)
	{
		k*=base;
		k+=a[i]-'0';
	}
	return k;
}

template<class T>
void eras(vector<T>& a,T b)
{
	a.erase(find(a.begin(),a.end(),b));
}

string its(ll k,int base=10)
{
	if (k==0) return "0";
	string a;
	while (k)
	{
		a.push_back((k%base)+'0');
		k/=base;
	}
	reverse(a.begin(),a.end());
	return a;
}

ll min(ll a,int b)
{
	if (a<b) return a;
	return b;
}

ll min(int a,ll b)
{
	if (a<b) return a;
	return b;
}

ll max(ll a,int b)
{
	if (a>b) return a;
	return b;
}

ll max(int a,ll b)
{
	if (a>b) return a;
	return b;
}

ll gcd(ll a,ll b)
{
	if (b==0) return a;
	return gcd(b,a%b);
}

ll lcm(ll a,ll b)
{
	return a/gcd(a,b)*b;
}

template<class T,class K>
pair<T,K> mp(T a,K b)
{
	return make_pair(a,b);
}

inline int mult(ll a,ll b)
{
	return (a*b)%MOD;
}

inline int pot(int n,int k)
{
	if (k==0) return 1;
	ll a=pot(n,k/2);
	a=mult(a,a);
	if (k%2) return mult(a,n);
	else return a;
}

int divide(int a,int b)
{
	return mult(a,pot(b,MOD-2));
}

inline int sub(int a,int b)
{
	if (a-b>=0) return a-b;
	return a-b+MOD;
}

inline int add(int a,int b)
{
	if (a+b>=MOD) return a+b-MOD;
	return a+b;
}

bool prime(ll a)
{
	if (a==1) return 0;
	for (int i=2;i<=round(sqrt(a));++i)
	{
		if (a%i==0) return 0;
	}
	return 1;
}

const int N=3010;
int n,m,k,fac[N*N],inf[N*N],dp[N][N];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	for (int i=0;i<10;++i) bases.push_back(rand()%(MOD-13893829*2)+13893829);
	cin>>n>>m>>k;
	fac[0]=1;
	for (int i=1;i<=n*m;++i) fac[i]=mult(fac[i-1],i);
	inf[n*m]=divide(1,fac[n*m]);
	for (int i=n*m;i>=1;--i) inf[i-1]=mult(inf[i],i);
	int ix=MOD,ax=0,iy=MOD,ay=0;
	for (int i=0;i<k;++i)
	{
		int a,b;
		cin>>a>>b;
		ix=min(ix,a);
		ax=max(ax,a);
		iy=min(iy,b);
		ay=max(ay,b);
	}
	int lx=ax-ix+1,ly=ay-iy+1;
	int ans=fac[lx*ly-k];
	int l=ix-1,r=n-ax,u=iy-1,d=m-ay;
	//cout<<ans<<' '<<l<<' '<<r<<' '<<u<<' '<<d<<en;
	dp[0][0]=1;
	for (int i=0;i<=l+r;++i) for (int j=0;j<=u+d;++j)
	{
		dp[i+1][j]=add(dp[i+1][j],mult(fac[ly+j],dp[i][j]));
		dp[i][j+1]=add(dp[i][j+1],mult(fac[lx+i],dp[i][j]));
	}
	ans=mult(ans,dp[l+r][u+d]);
	ans=mult(ans,divide(fac[l+r],mult(fac[l],fac[r])));
	ans=mult(ans,divide(fac[u+d],mult(fac[u],fac[d])));
	cout<<ans<<en;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 7 ms 1408 KB Output is correct
3 Correct 9 ms 2304 KB Output is correct
4 Correct 43 ms 12924 KB Output is correct
5 Correct 40 ms 12024 KB Output is correct
6 Correct 52 ms 12664 KB Output is correct
7 Correct 45 ms 14968 KB Output is correct
8 Correct 93 ms 31612 KB Output is correct
9 Correct 217 ms 71388 KB Output is correct
10 Correct 364 ms 92536 KB Output is correct
11 Correct 292 ms 81272 KB Output is correct
12 Correct 196 ms 63352 KB Output is correct
13 Correct 21 ms 7040 KB Output is correct
14 Correct 206 ms 70776 KB Output is correct
15 Correct 439 ms 104452 KB Output is correct
16 Correct 288 ms 72604 KB Output is correct
17 Correct 221 ms 74744 KB Output is correct
18 Correct 406 ms 103288 KB Output is correct