Submission #1162227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162227		AlgorithmWarrior	Tents (JOI18_tents)	C++20	100 / 100	168 ms	32008 KiB

tents

#include <bits/stdc++.h>

using namespace std;

int const MAX=3005;
int const MOD=1e9+7;
int fact[MAX];
int invfact[MAX];
int invpow2[MAX];
int dp[MAX][MAX];

int bin_exp(int base,int exp){
    int rez=1;
    while(exp){
        if(exp&1)
            rez=1LL*rez*base%MOD;
        base=1LL*base*base%MOD;
        exp/=2;
    }
    return rez;
}

void precalc(){
    int i;
    fact[0]=1;
    for(i=1;i<MAX;++i)
        fact[i]=1LL*i*fact[i-1]%MOD;
    invfact[MAX-1]=bin_exp(fact[MAX-1],MOD-2);
    for(i=MAX-2;i>=0;--i)
        invfact[i]=1LL*(i+1)*invfact[i+1]%MOD;
    int inv2=bin_exp(2,MOD-2);
    invpow2[0]=1;
    for(i=1;i<MAX;++i)
        invpow2[i]=1LL*inv2*invpow2[i-1]%MOD;
}

int comb(int n,int k){
    return 1LL*fact[n]*invfact[k]%MOD*invfact[n-k]%MOD;
}

int aranj(int n,int k){
    return 1LL*fact[n]*invfact[n-k]%MOD;
}

void add(int& x,int val){
    x=(x+val)%MOD;
}

int choose_individual(int n,int m){
    if(dp[n][m])
        return dp[n][m];
    if(n==0 || m==0)
        return dp[n][m]=1;
    return dp[n][m]=(choose_individual(n-1,m)+4LL*m*choose_individual(n-1,m-1)%MOD)%MOD;
}

int choose_columns(int n,int m){
    int total=0;
    int i;
    for(i=0;i<=m && 2*i<=n;++i)
        add(total,1LL*comb(m,i)*aranj(n,2*i)%MOD*invpow2[i]%MOD*choose_individual(n-2*i,m-i)%MOD);
    return total;
}

int choose_rows(int n,int m){
    int total=0;
    int i;
    for(i=0;i<=n && 2*i<=m;++i)
        add(total,1LL*comb(n,i)*aranj(m,2*i)%MOD*invpow2[i]%MOD*choose_columns(n-i,m-2*i)%MOD);
    return total;
}

int main()
{
    precalc();
    int n,m;
    cin>>n>>m;
    cout<<choose_rows(n,m)-1;
    return 0;
}

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