Submission #907047

#	Time	Username	Problem	Language	Result	Execution time	Memory
907047		ibm2006	Tents (JOI18_tents)	C++17	100 / 100	130 ms	160988 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,dp[3300][3300],b[3300][3300];
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*dp[n-2*i][m-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()
{
    for(i=0;i<=3000;i++)
    {
        dp[i][0]=1;
        dp[0][i]=1;
        b[0][i]=1;
        b[i][0]=i+1;
    }
    for(i=1;i<=3000;i++)
    {
        for(j=1;j<=3000;j++)
        {
            dp[i][j]=1+(b[i-1][j-1])*4%mod*j%mod;
            dp[i][j]%=mod;
            b[i][j]=(b[i-1][j]+dp[i][j])%mod;
        }
    }
    scanf("%lld %lld",&n,&m);
    fac[0]=1;
    invfac[0]=1;
    for(i=1;i<=10000;i++)
    {
        fac[i]=fac[i-1]*i%mod;
        invfac[i]=inv(fac[i]);
    }
    two[0]=1;
    invtwo[0]=1;
    for(i=1;i<=10000;i++)
    {
        two[i]=two[i-1]*2%mod;
        invtwo[i]=inv(two[i]);
    }
    four[0]=1;
    for(i=1;i<=10000;i++)
    {
        four[i]=four[i-1]*4%mod;
    }
    s=f(n,m);
    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:71:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     scanf("%lld %lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52