Submission #824729

#	Time	Username	Problem	Language	Result	Execution time	Memory
824729		Dec0Dedd	Tents (JOI18_tents)	C++14	100 / 100	192 ms	58972 KiB

tents

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 3e3+10;
const int MOD = 1e9+7;

ll dp[N][N], n, m;

// From (N, M) we can:
// 1) do nothing and go to (N-1, M)
// 2) put random tent in N-th row in any direction 4*M * (N-1, M-1)
// 3) put 2 tents in N-th row in M*(M-1)/2 * (N-1, M-2)
// 4) put 2 tents in same column s.t. on is in N-th row in M*(N-1)*(N-2, M-1) ways

ll solve(ll n, ll m) {
    if (n <= 0 || m <= 0) return 1;
    if (dp[n][m] > 0) return dp[n][m];
    ll res=solve(n-1, m);
    (res+=4*m*solve(n-1, m-1))%=MOD;
    (res+=m*(m-1)/2*solve(n-1, m-2))%=MOD;
    (res+=m*(n-1)*solve(n-2, m-1))%=MOD;
    return dp[n][m]=res;
}

int main() {
    cin>>n>>m;
    cout<<solve(n, m)-1<<"\n";
}

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