oj.uz

Submission #913978

# Submission time Handle Problem Language Result Execution time Memory
913978 2024-01-20T16:39:33 Z alexdd Tents (JOI18_tents) C++17
48 / 100
 2000 ms 70956 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 = (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 70744 KB Output is correct
2 Correct 21 ms 70744 KB Output is correct
3 Correct 17 ms 70736 KB Output is correct
4 Correct 17 ms 70780 KB Output is correct
5 Correct 23 ms 70744 KB Output is correct
6 Correct 40 ms 70952 KB Output is correct
7 Correct 39 ms 70744 KB Output is correct
8 Correct 23 ms 70732 KB Output is correct
9 Correct 18 ms 70748 KB Output is correct
10 Correct 133 ms 70748 KB Output is correct
11 Correct 17 ms 70744 KB Output is correct
12 Correct 898 ms 70956 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 70744 KB Output is correct
2 Correct 21 ms 70744 KB Output is correct
3 Correct 17 ms 70736 KB Output is correct
4 Correct 17 ms 70780 KB Output is correct
5 Correct 23 ms 70744 KB Output is correct
6 Correct 40 ms 70952 KB Output is correct
7 Correct 39 ms 70744 KB Output is correct
8 Correct 23 ms 70732 KB Output is correct
9 Correct 18 ms 70748 KB Output is correct
10 Correct 133 ms 70748 KB Output is correct
11 Correct 17 ms 70744 KB Output is correct
12 Correct 898 ms 70956 KB Output is correct
13 Correct 20 ms 70748 KB Output is correct
14 Correct 18 ms 70736 KB Output is correct
15 Execution timed out 2032 ms 70744 KB Time limit exceeded
16 Halted 0 ms 0 KB -