Submission #897747

#	Time	Username	Problem	Language	Result	Execution time	Memory
897747		denniskim	NoM (RMI21_nom)	C++17	100 / 100	90 ms	99668 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;
int ans;
ll cou[2010];
int dp[9000010];
ll fac[5010] = {0, }, inv[5010] = {0, };
int C[5010][5010];
 
ll num(ll X, ll Y)
{
	return X * (m + 1) + Y;
}

void init(void)
{
	fac[0] = 1;
    fac[1] = 1;
     
    for(ll i = 2 ; i <= 4500 ; ++i)
        fac[i] = (fac[i - 1] * i) % ss;
    
    C[0][0] = 1;
    
    for(ll i = 1 ; i <= 4000 ; ++i)
    {
    	C[i][0] = C[i][i] = 1;
    	
    	for(ll j = 1 ; j < i ; ++j)
    	{
    		C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    		
    		if(C[i][j] > ss)
    			C[i][j] -= ss;
		}
	}
}
 
int main(void)
{
	fastio
	
	cin >> n >> m;
	
	init();
	
	ll siz = (n << 1);
	
	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 << 1) <= X && k <= i ; ++k)
            {
				dp[num(i, j)] = (dp[num(i, j)] + (ll)dp[num(i - k, j - 1)] * C[X][k << 1] % ss * fac[k << 1] % ss * C[i][k]% ss);
              	while(abs(dp[num(i, j)]) > ss)
                {
                    if(dp[num(i, j)] < 0)
                        dp[num(i, j)] += ss;
                    else
                        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)]);
          
          	while(abs(dp[num(i, j)]) > ss)
			{
				if(dp[num(i, j)] < 0)
					dp[num(i, j)] += ss;
				else
					dp[num(i, j)] -= ss;
			}
        }
	}
	
	for(ll i = 1 ; i <= n ; ++i)
	{
		ll gap = (ll)dp[num(i, m)] * C[n][i] % ss * fac[(n - i) << 1] % ss;
		
		if(i & 1)
			ans = (ans - gap);
		else
			ans = (ans + gap);
      
      	while(abs(ans) > ss)
        {
          if(ans < 0)
            ans += ss;
          else
            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: 48 / 48