Submission #1281793

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281793		Jawad_Akbar_JJ	Tents (JOI18_tents)	C++20	100 / 100	555 ms	294976 KiB

tents

#include <iostream>
#include <vector>

using namespace std;
const int N = 5005;
int seen[N][N], dp[N][N], ch[N][N], fac[N], inv[N], mod = 1e9 + 7;
long long Ans;

int calc(int n, int m){
    if (n == 0 or m == 0)
        return 1;
    if (seen[n][m])
        return dp[n][m];

    seen[n][m] = seen[m][n] = 1;
    dp[n][m] = dp[m][n] = (1LL * m * 4 * calc(n-1, m-1) + calc(n-1, m)) % mod;
    return dp[n][m];
}

int n, m;
void get(int a, int b){
    if (a + b + b > n or a + a + b > m)
        return;
    Ans += 1LL * ch[n][a] * ch[m][2 * a] % mod * ch[n-a][2 * b] % mod * ch[m-2*a][b] % mod * fac[2 * a] % mod * fac[2 * b] % mod * inv[a + b] % mod * calc(n - a - b - b, m - a - a - b) % mod;// % mod;
}

signed main(){
    inv[N-1] = 105853511;
    for (int i=N-2;i>=0;i--)
        inv[i] = inv[i+1] * 2 % mod;

    for (int i=1;i<N;i++){
        for (int j=ch[i-1][0]=1;j<N;j++)
            ch[i][j] = (ch[i-1][j-1] + ch[i-1][j]) % mod;
    }

    for (int i=fac[0]=1;i<N;i++)
        fac[i] = 1LL * fac[i-1] * i % mod;

    calc(N-1, N-1);

    cin>>n>>m;

    for (int a = 0;a <= n; a++){
        for (int b = 0;a + b + b <= n and a + a + b <= m;b++)
            get(a, b);
    }
    cout<<(Ans - 1 + mod) % mod<<endl;
}

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