oj.uz

Submission #913981

# Submission time Handle Problem Language Result Execution time Memory
913981 2024-01-20T16:40:49 Z alexdd Tents (JOI18_tents) C++17
48 / 100
 2000 ms 71000 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)
    //for(int i=0;i<2*cntl;i++)
      //  aux2 = (aux2 * (m-i))%MOD;
    aux2 = (fact[m] * put(fact[m-2*cntl],MOD-2))%MOD;
    aux2 = (aux2 * put(put(2,cntl),MOD-2))%MOD;
    return aux2;
}
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;
        for(int cntc=0;cntc<=min(m-2*cntl,(n-cntl)/2);cntc++)
        {
            sum += (aux * ((comb(m-2*cntl,cntc) * place2(cntc,n-cntl))%MOD))%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 70748 KB Output is correct
2 Correct 17 ms 70756 KB Output is correct
3 Correct 17 ms 70748 KB Output is correct
4 Correct 18 ms 70888 KB Output is correct
5 Correct 27 ms 70748 KB Output is correct
6 Correct 39 ms 70748 KB Output is correct
7 Correct 41 ms 70748 KB Output is correct
8 Correct 27 ms 70744 KB Output is correct
9 Correct 17 ms 70748 KB Output is correct
10 Correct 105 ms 70748 KB Output is correct
11 Correct 18 ms 70744 KB Output is correct
12 Correct 589 ms 71000 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 70748 KB Output is correct
2 Correct 17 ms 70756 KB Output is correct
3 Correct 17 ms 70748 KB Output is correct
4 Correct 18 ms 70888 KB Output is correct
5 Correct 27 ms 70748 KB Output is correct
6 Correct 39 ms 70748 KB Output is correct
7 Correct 41 ms 70748 KB Output is correct
8 Correct 27 ms 70744 KB Output is correct
9 Correct 17 ms 70748 KB Output is correct
10 Correct 105 ms 70748 KB Output is correct
11 Correct 18 ms 70744 KB Output is correct
12 Correct 589 ms 71000 KB Output is correct
13 Correct 18 ms 70748 KB Output is correct
14 Correct 19 ms 70748 KB Output is correct
15 Execution timed out 2085 ms 70748 KB Time limit exceeded
16 Halted 0 ms 0 KB -