Submission #833120

#	Time	Username	Problem	Language	Result	Execution time	Memory
833120		exodus_	Tents (JOI18_tents)	C++14	100 / 100	158 ms	82728 KiB

tents

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
long long dp[4004][4004];
int main() {
    int n,m;
    cin >> n >> m;
    for(int i=0; i<=m; i++) {
        dp[0][i] = 1;
    }
    for(int i=1; i<=n; i++) {
        for(int j=0; j<=m; j++) {
            dp[i][j] += dp[i-1][j];
            if(j>=1) {
                dp[i][j] += ((dp[i-1][j-1] * j)%mod * 4)%mod;
                dp[i][j] %= mod;
            }
            if(j>=1 && i>=2) {
                dp[i][j] += ((dp[i-2][j-1] * j)%mod * (i-1))%mod;
                dp[i][j] %= mod;
            }
            if(i>=1 && j>=2) {
                dp[i][j] += (dp[i-1][j-2] * (j*(j-1)/2)%mod)%mod;
                dp[i][j] %= mod;
            }
        }
    }
    cout << dp[n][m]-1 << endl;
    return 0;
}

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