Submission #913989

#	Time	Username	Problem	Language	Result	Execution time	Memory
913989		alexdd	Tents (JOI18_tents)	C++17	0 / 100	2062 ms	80300 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];
int calc_brut(int x, int y)
{
    int sum=0;
    for(int cntc=0;cntc<=min(x,y/2);cntc++)
    {
        sum += (comb(x,cntc) * place2(cntc,y))%MOD;
        sum %= MOD;
    }
    return sum;
}
int calc2(int n, int m)
{
    int sum=0;
    for(int cntl=0;cntl<=min(n,m/2);cntl++)
    {
        int aux = (comb(n,cntl) * place2(cntl,m))%MOD;
        //sum += (calc_brut(m-2*cntl,n-cntl)*aux)%MOD;
        sum += (prec[m-2*cntl][n-cntl]*aux)%MOD;
        sum%=MOD;
    }
    return sum;
}
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;
    for(int i=0;i<=m;i++)
        for(int j=0;j<=n;j++)
            prec[i][j] = calc_brut(i,j);
    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;
    }
    cout<<sum;
    return 0;
}
/**

*/

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