oj.uz

Submission #913989

# Submission time Handle Problem Language Result Execution time Memory
913989 2024-01-20T17:25:21 Z alexdd Tents (JOI18_tents) C++17
0 / 100
 2000 ms 80300 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];
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.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 73816 KB Output is correct
2 Correct 24 ms 77860 KB Output is correct
3 Correct 18 ms 71644 KB Output is correct
4 Correct 18 ms 71728 KB Output is correct
5 Correct 108 ms 77984 KB Output is correct
6 Correct 255 ms 73812 KB Output is correct
7 Correct 172 ms 77908 KB Output is correct
8 Correct 150 ms 73892 KB Output is correct
9 Correct 19 ms 71712 KB Output is correct
10 Correct 711 ms 75704 KB Output is correct
11 Correct 23 ms 79960 KB Output is correct
12 Execution timed out 2062 ms 80300 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 73816 KB Output is correct
2 Correct 24 ms 77860 KB Output is correct
3 Correct 18 ms 71644 KB Output is correct
4 Correct 18 ms 71728 KB Output is correct
5 Correct 108 ms 77984 KB Output is correct
6 Correct 255 ms 73812 KB Output is correct
7 Correct 172 ms 77908 KB Output is correct
8 Correct 150 ms 73892 KB Output is correct
9 Correct 19 ms 71712 KB Output is correct
10 Correct 711 ms 75704 KB Output is correct
11 Correct 23 ms 79960 KB Output is correct
12 Execution timed out 2062 ms 80300 KB Time limit exceeded
13 Halted 0 ms 0 KB -