Submission #914002

#	Time	Username	Problem	Language	Result	Execution time	Memory
914002		alexdd	Tents (JOI18_tents)	C++17	48 / 100	2054 ms	127556 KiB

tents

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;
int put(int a, int exp)
{
    if(exp==0)
        return 1;
    if(exp%2==0)
        return put((a*a)%MOD,exp/2);
    else
        return (put((a*a)%MOD,exp/2)*a)%MOD;
}
int cm[3005][3005];
int fact[6005];
int comb(int x, int y)
{
    return cm[x][y];
}
int place2(int cntl, int m)
{
    int aux2 = 1;///aux2 = m * (m-1) * (m-2) * ... * (m-2*cntl+1) / put(2,cntl)
    aux2 = (fact[m] * put(fact[m-2*cntl],MOD-2))%MOD;
    aux2 = (aux2 * put(put(2,cntl),MOD-2))%MOD;
    return aux2;
}
int prec[3005][3005];
bool done[3005][3005];
int calc_unu(int n, int m)
{
    if(n>m)
        swap(n,m);
    if(!done[n][m])
    {
        int sum=0;
        for(int cnt1=0;cnt1<=min(n,m);cnt1++)
        {
            sum += (((((comb(n,cnt1) * comb(m,cnt1))%MOD) * fact[cnt1])%MOD)*put(4,cnt1))%MOD;
            sum%=MOD;
        }
        prec[n][m]=sum;
        done[n][m]=1;
    }
    return prec[n][m];
}
signed main()
{
    fact[0]=1;
    for(int i=1;i<=6000;i++)
        fact[i]=(fact[i-1]*i)%MOD;
    for(int i=0;i<=3000;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(i==j)
                cm[i][j]=1;
            else if(j==0)
                cm[i][j]=1;
            else
                cm[i][j]=(cm[i-1][j-1]+cm[i-1][j])%MOD;
        }
    }
    int n,m;
    cin>>n>>m;
    int sum=MOD-1;
    /*for(int cnt1=0;cnt1<=min(n,m);cnt1++)
    {
        int moduri1 = (((((comb(n,cnt1) * comb(m,cnt1))%MOD)*fact[cnt1])%MOD) * put(4,cnt1))%MOD;///in cate moduri putem pune corturile care sunt singure pe rand si coloana
        int moduri2 = calc2(n-cnt1,m-cnt1);
        sum += (moduri1 * moduri2)%MOD;
        sum %= MOD;
    }*/
    for(int cntl=0;cntl<=min(n,m/2);cntl++)
    {
        for(int cntc=0;cntc<=min(m-2*cntl,(n-cntl)/2);cntc++)
        {
            int aux = (((((comb(n,cntl) * place2(cntl,m))%MOD) * comb(m-2*cntl,cntc))%MOD) * place2(cntc,n-cntl))%MOD;
            sum += (aux * calc_unu(n-cntl-cntc*2,m-cntc-cntl*2))%MOD;
            sum %= MOD;
        }
    }
    cout<<sum;
    return 0;
}
/**

*/

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