Submission #716375

#	Time	Username	Problem	Language	Result	Execution time	Memory
716375		S2speed	Tents (JOI18_tents)	C++17	100 / 100	166 ms	212880 KiB

tents

#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cout<<"--------------------------------------\n";
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef double db;
typedef pair<pll , ll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;

const ll maxn = 3e3 + 17 , md = 1e9 + 7 , inf = 2e16;

inline ll tav(ll n , ll k){
	ll res = 1;
	while(k > 0){
		if(k & 1){
			res *= n; res %= md;
		}
		n *= n; n %= md;
		k >>= 1;
	}
	return res;
}

ll fact[maxn] , _fact[maxn];

void fact_build(){
	fact[0] = 1;
	for(ll i = 1 ; i < maxn ; i++){
		fact[i] = fact[i - 1] * i % md;
	}
	_fact[maxn - 1] = tav(fact[maxn - 1] , md - 2);
	for(ll i = maxn - 2 ; ~i ; i--){
		_fact[i] = _fact[i + 1] * (i + 1) % md;
	}
	return;
}

ll chs(ll n , ll k){
	if(k < 0 || k > n) return 0;
	return fact[n] * _fact[k] % md * _fact[n - k] % md;
}

ll dp[maxn][maxn] , ps[maxn][maxn] , ps2[maxn][maxn];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	fact_build();
	ll n , m;
	cin>>n>>m;
	fill(dp[0] , dp[0] + m + 1 , 1);
	iota(ps[0] , ps[0] + m + 1 , 1);
	for(ll i = 0 ; i <= m ; i++){
		ps2[0][i] = (i + 2) * (i + 1) / 2;
	}
	for(ll i = 1 ; i <= n ; i++){
		ps2[i][0] = ps[i][0] = dp[i][0] = 1;
		for(ll j = 1 ; j <= m ; j++){
			ll h = 1;
			if(j > 1){
				h += ps2[i - 1][j - 2] * i % md;
			}
			if(i > 1){
				h += chs(i , 2) * ps[i - 2][j - 1] % md;
			}
			dp[i][j] = h % md;
			ps[i][j] = ps[i][j - 1] + dp[i][j]; ps[i][j] %= md;
			ps2[i][j] = ps2[i][j - 1] + dp[i][j] * (j + 1); ps2[i][j] %= md;
		}
	}
	ll ans = -1 , lm = min(n , m);
	for(ll i = 0 ; i <= lm ; i++){
		ll h = chs(n , i) * chs(m , i) % md * fact[i] % md * dp[n - i][m - i] % md * tav(4 , i) % md;
		ans += h;
	}
	ans %= md;
	cout<<ans<<'\n';
	return 0;
}

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52