oj.uz

Submission #913992

# Submission time Handle Problem Language Result Execution time Memory
913992 2024-01-20T17:27:17 Z alexdd Tents (JOI18_tents) C++17
48 / 100
 2000 ms 127912 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_brut(int x, int y)
{
    if(!done[x][y])
    {
        int sum=0;
        for(int cntc=0;cntc<=min(x,y/2);cntc++)
        {
            sum += (comb(x,cntc) * place2(cntc,y))%MOD;
            sum %= MOD;
        }
        done[x][y]=1;
        prec[x][y]=sum;
    }
    return prec[x][y];
}
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%=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;
    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
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 74320 KB Output is correct
2 Correct 18 ms 74332 KB Output is correct
3 Correct 17 ms 74332 KB Output is correct
4 Correct 18 ms 74452 KB Output is correct
5 Correct 27 ms 78928 KB Output is correct
6 Correct 40 ms 76632 KB Output is correct
7 Correct 42 ms 79028 KB Output is correct
8 Correct 26 ms 74584 KB Output is correct
9 Correct 19 ms 74332 KB Output is correct
10 Correct 104 ms 76800 KB Output is correct
11 Correct 18 ms 74332 KB Output is correct
12 Correct 582 ms 81512 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 18 ms 74332 KB Output is correct
3 Correct 17 ms 74332 KB Output is correct
4 Correct 18 ms 74452 KB Output is correct
5 Correct 27 ms 78928 KB Output is correct
6 Correct 40 ms 76632 KB Output is correct
7 Correct 42 ms 79028 KB Output is correct
8 Correct 26 ms 74584 KB Output is correct
9 Correct 19 ms 74332 KB Output is correct
10 Correct 104 ms 76800 KB Output is correct
11 Correct 18 ms 74332 KB Output is correct
12 Correct 582 ms 81512 KB Output is correct
13 Correct 18 ms 74328 KB Output is correct
14 Correct 17 ms 74284 KB Output is correct
15 Execution timed out 2066 ms 127912 KB Time limit exceeded
16 Halted 0 ms 0 KB -