Submission #906953

#	Time	Username	Problem	Language	Result	Execution time	Memory
906953		ibm2006	Tents (JOI18_tents)	C++17	48 / 100	24 ms	348 KiB

tents

#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 (stderr)

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 / 48
• Subtask 2: 0 / 52