Submission #1182333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182333		edga1	Tents (JOI18_tents)	C++20	100 / 100	140 ms	35824 KiB

tents

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define fi first
#define se second
#define pb push_back
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define MOD 1000000007
#define N 3005

int fact[N], inv[N], pak2[N], invpak2[N], dp[N][N];

int sum(int a, int b){
    a+=b;
    if(a>=MOD) a-=MOD;
    if(a<0) a+=MOD;
    return a;
}

int mul(int a, int b){
    return 1LL*a*b%MOD;
}

int poww(int n, int k){
    int r=1;
    while(k>0){
        if(k&1) r=mul(r,n);
        n=mul(n,n);
        k>>=1;
    }
    return r;
}

int comb(int n, int k){
    return mul(fact[n],mul(inv[k], inv[n-k]));
}

int main()
{
    fastIO;
    fact[0]=1;
    for(int i=1; i<N; i++) fact[i]=mul(fact[i-1],i);
    inv[N-1]=poww(fact[N-1],MOD-2);
    for(int i=N-2; i>=0; i--) inv[i]=mul(i+1,inv[i+1]);
    pak2[0]=1;
    for(int i=1; i<N; i++) pak2[i]=mul(pak2[i-1],2);
    invpak2[N-1]=poww(pak2[N-1],MOD-2);
    for(int i=N-2; i>=0; i--) invpak2[i]=mul(2,invpak2[i+1]);
    for(int i=0; i<N; i++){
        dp[i][0]=1;
        dp[0][i]=1;
    }
    for(int i=1; i<N; i++){
        for(int j=1; j<N; j++){
            dp[i][j]=sum(dp[i-1][j],mul(4,mul(j,dp[i-1][j-1])));
        }
    }
    int n,m;
    cin>>n>>m;
    int r=0;
    for(int vert=0; vert*2<=n && vert<=m; vert++){
        int cvert=mul(mul(comb(m, vert),comb(n,vert*2)),mul(fact[vert*2],invpak2[vert]));
        int newn=n-vert*2,newm=m-vert;
        for(int hor=0; hor*2<=newm && hor<=newn; hor++){
            int chor=mul(mul(comb(newn, hor),comb(newm,hor*2)),mul(fact[hor*2],invpak2[hor]));
            r=sum(r,mul(cvert,mul(chor,dp[newn-hor][newm-hor*2])));
        }
    }
    r=sum(r,-1);
    cout<<r;
    return 0;
}

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