oj.uz

Submission #906953

# Submission time Handle Problem Language Result Execution time Memory
906953 2024-01-15T05:03:40 Z ibm2006 Tents (JOI18_tents) C++17
48 / 100
 24 ms 348 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll mod=1000000007;
ll n,i,j,k,l,r,x,y,z,w,s,t,two[11000],four[11000],invtwo[11000],fac[11000],invfac[11000],m;
ll inv(ll x)
{
    ll y=mod-2,s=1;
    while(y)
    {
        if(y&1)
        {
            s=s*x%mod;
        }

        x=x*x%mod;
        y>>=1;
    }
    return s;
}
ll C(ll x,ll y)
{
    if(x<0)
        return 0;
    if(y<0||y>x)
        return 0;
    return fac[x]*invfac[y]%mod*invfac[x-y]%mod;
}
ll g(ll n,ll m)
{
    ll i,j,s=0;
    if(n<0||m<0)
        return 0;
    if(n==0||m==0)
        return 1;
    for(i=0;i<=m&&n-i*2>=0;i++)
    {
        s=(s+C(m,i)*C(n,2*i)%mod*fac[i*2]%mod*invtwo[i]%mod)%mod;
    }
    return s;
}
ll f(ll n,ll m)
{
    ll i,j,s=0;
    if(n>m)
        swap(n,m);
    for(i=0;i<=n;i++)
    {
        s=(s+C(n,i)*C(m,2*i)%mod*fac[i*2]%mod*invtwo[i]%mod*g(n-i,m-2*i))%mod;
    }
    return s;
}
int main()
{
    scanf("%lld %lld",&n,&m);
    fac[0]=1;
    invfac[0]=1;
    for(i=1;i<=1000;i++)
    {
        fac[i]=fac[i-1]*i%mod;
        invfac[i]=inv(fac[i]);
    }
    two[0]=1;
    invtwo[0]=1;
    for(i=1;i<=1000;i++)
    {
        two[i]=two[i-1]*2%mod;
        invtwo[i]=inv(two[i]);
    }
    four[0]=1;
    for(i=1;i<=1000;i++)
    {
        four[i]=four[i-1]*4%mod;
    }
    for(i=0;i<=min(n,m);i++)
    {
        s=(s+C(n,i)*C(m,i)%mod*fac[i]%mod*f(n-i,m-i)%mod*four[i]%mod)%mod;
    }
    s=(s+mod-1)%mod;
    printf("%lld",s);
}

Compilation message

tents.cpp: In function 'll g(ll, ll)':
tents.cpp:31:10: warning: unused variable 'j' [-Wunused-variable]
   31 |     ll i,j,s=0;
      |          ^
tents.cpp: In function 'll f(ll, ll)':
tents.cpp:44:10: warning: unused variable 'j' [-Wunused-variable]
   44 |     ll i,j,s=0;
      |          ^
tents.cpp: In function 'int main()':
tents.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%lld %lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 5 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 24 ms 348 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 5 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 24 ms 348 KB Output is correct
13 Incorrect 1 ms 344 KB Output isn't correct
14 Halted 0 ms 0 KB -