oj.uz

Submission #914002

# Submission time Handle Problem Language Result Execution time Memory
914002 2024-01-20T18:14:13 Z alexdd Tents (JOI18_tents) C++17
48 / 100
 2000 ms 127556 KB 
#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.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 74320 KB Output is correct
2 Correct 17 ms 74332 KB Output is correct
3 Correct 18 ms 74276 KB Output is correct
4 Correct 18 ms 74332 KB Output is correct
5 Correct 19 ms 74516 KB Output is correct
6 Correct 22 ms 76792 KB Output is correct
7 Correct 21 ms 76636 KB Output is correct
8 Correct 20 ms 74588 KB Output is correct
9 Correct 18 ms 74328 KB Output is correct
10 Correct 27 ms 76892 KB Output is correct
11 Correct 18 ms 74332 KB Output is correct
12 Correct 52 ms 81496 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 74320 KB Output is correct
2 Correct 17 ms 74332 KB Output is correct
3 Correct 18 ms 74276 KB Output is correct
4 Correct 18 ms 74332 KB Output is correct
5 Correct 19 ms 74516 KB Output is correct
6 Correct 22 ms 76792 KB Output is correct
7 Correct 21 ms 76636 KB Output is correct
8 Correct 20 ms 74588 KB Output is correct
9 Correct 18 ms 74328 KB Output is correct
10 Correct 27 ms 76892 KB Output is correct
11 Correct 18 ms 74332 KB Output is correct
12 Correct 52 ms 81496 KB Output is correct
13 Correct 18 ms 74332 KB Output is correct
14 Correct 18 ms 74332 KB Output is correct
15 Execution timed out 2054 ms 127556 KB Time limit exceeded
16 Halted 0 ms 0 KB -