Submission #897730

#	Time	Username	Problem	Language	Result	Execution time	Memory
897730		denniskim	NoM (RMI21_nom)	C++17	52 / 100	139 ms	31828 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())

ll n, m;
ll ss = 1000000007;
ll ans;
ll cou[2010];
ll dp[4000010];
ll fac[5010] = {0, }, inv[5010] = {0, };

ll num(ll X, ll Y)
{
	return X * (m + 1) + Y;
}

ll power(ll xx, ll yy)
{
    ll ret = 1;
     
    while(yy > 0)
    {
        if(yy % 2)
            ret = (ret * xx) % ss;
        xx = (xx * xx) % ss;
        yy /= 2;
    }
     
    return ret;
}
 
ll C(ll xx, ll yy)
{
	if(xx < yy)
		return 0;
	
    if(xx == yy || !yy)
        return 1;
    
    long long r = (fac[xx] * inv[xx - yy]) % ss;
    r = (r * inv[yy]) % ss;
    return r;
}

void init(void)
{
	fac[0] = 1;
    fac[1] = 1;
     
    for(ll i = 2 ; i <= 4500 ; i++)
        fac[i] = (fac[i - 1] * i) % ss;
     
    inv[4500] = power(fac[4500], ss - 2);
    
    for(ll i = 4499 ; i >= 0 ; i--)
        inv[i] = (inv[i + 1] * (i + 1)) % ss;
}

int main(void)
{
	fastio
	
	cin >> n >> m;
	
	init();
	
	ll siz = n * 2;
	
	ans = fac[siz];
	
	for(ll i = 1 ; i <= siz ; ++i)
	{
		ll gap = i % m;
		
		if(gap == 0)
			gap = m;
		
		cou[gap]++;
	}
	
	for(ll i = 0 ; i <= m ; ++i)
		dp[num(0, i)] = 1;
	
	for(ll i = 1 ; i <= n ; ++i)
	{
		for(ll j = 1 ; j <= m ; ++j)
		{
			ll X = cou[j];
			
			for(ll k = 1 ; k * 2 <= X && k <= i ; ++k)
			{
				dp[num(i, j)] = (dp[num(i, j)] + dp[num(i - k, j - 1)] * C(X, k * 2) % ss * fac[k * 2] % ss * C(i, k) % ss);
				
				if(dp[num(i, j)] < 0)
					dp[num(i, j)] += ss;
				while(dp[num(i, j)] > ss)
					dp[num(i, j)] -= ss;
			}
		}
		
		for(ll j = 1 ; j <= m ; ++j)
		{
			dp[num(i, j)] = (dp[num(i, j)] + dp[num(i, j - 1)]);
			
			if(dp[num(i, j)] < 0)
				dp[num(i, j)] += ss;
			while(dp[num(i, j)] > ss)
				dp[num(i, j)] -= ss;
		}
	}
	
	for(ll i = 1 ; i <= n ; ++i)
	{
		ll gap = dp[num(i, m)] * C(n, i) % ss * fac[n * 2 - i * 2] % ss;
		
		if(i & 1)
		{
			ans = (ans - gap);
			
			if(ans < 0)
				ans += ss;
			while(ans > ss)
				ans -= ss;
		}
		
		else
		{
			ans = (ans + gap);
			
			if(ans < 0)
				ans += ss;
			while(ans > ss)
				ans -= ss;
		}
	}
	
	ans = (ans + ss) % ss;
	
	cout << ans;
	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 18 / 18
• Subtask 5: 0 / 48