Submission #76785

#	Time	Username	Problem	Language	Result	Execution time	Memory
76785		vex	Boat (APIO16_boat)	C++14	100 / 100	840 ms	12940 KiB

boat

#include <bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
#define maxn 505
#define mod (long long)(1e9 + 7)
using namespace std;

long long ste(long long x,long long y)
{
    if(y==0)return 1LL;
    if(y%2==1)return (x*ste(x,y-1))%mod;

    long long ss=ste(x,y/2);
    return (ss*ss)%mod;
}
long long fact[2*maxn];
long long invf[2*maxn];
int d[2*maxn];
long long ff[2*maxn][maxn];
long long dff[2*maxn][maxn];
int n;
void precalc()
{
    fact[0]=1;
    for(int i=1;i<=1000;i++)
    {
        fact[i]=fact[i-1]*i;
        fact[i]%=mod;
    }
    for(int i=0;i<=1000;i++)
        invf[i]=ste(fact[i],mod-2);
        
    for(int i=1;i<=2*n-1;i++)
    {
    	ff[i][1]=d[i+1]-d[i];
    	dff[i][1]=d[i+1]-d[i]-1;
    	for(int j=1;j<500 && d[i+1]-d[i]-j>0;j++)
    	{
    		ff[i][j+1]=ff[i][j]*(d[i+1]-d[i]-j);
    		ff[i][j+1]%=mod;
    		
    		dff[i][j+1]=dff[i][j]*(d[i+1]-d[i]-j-1);
    		dff[i][j+1]%=mod;
    	}
    }
}
long long bc(int x,int y)
{
    if(x<y)return 0;
    if(x<=1000)return (((fact[x]*invf[y])%mod) * invf[x-y] )%mod;

	long long res=1;
	for(int i=0;i<y;i++)
	{
		res*=(x-i);
		res%=mod;
	}
	return (res*invf[y])%mod;
}


pii t[maxn];

long long dp[2*maxn][maxn];

vector<int>tre;
long long pre[maxn];
long long f[2*maxn],gf[2*maxn];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>t[i].f>>t[i].s;
        d[2*i-1]=t[i].f;
        d[2*i]=t[i].s;
    }

    sort(d+1,d+1+2*n);
    precalc();

    for(int i=1;i<=n;i++)dp[0][i]=0LL;
    for(int i=1;i<=n;i++)if(t[i].f==d[1])dp[0][i]=1LL;
    dp[0][0]=1LL;
    //for(int i=1;i<=n;i++)cout<<dp[0][i]<<" "<<t[i].f<<" "<<d[0]<<endl;

    for(int i=1;i<=2*n-1;i++)
    {
        for(int j=0;j<=n;j++)dp[i][j]=dp[i-1][j];
        if(d[i]==d[i+1])continue;

        tre.clear();
        for(int j=0;j<=n;j++)
        {
            f[j]=0;
            pre[j]=0;
            gf[j]=0;
        }

        for(int j=1;j<=n;j++)
        {
            if(t[j].f==d[i+1]);
            else if(t[j].f<=d[i] && d[i+1]<=t[j].s);
            else continue;


            for(int k=0;k<j;k++)
            {
                pre[j]+=dp[i-1][k];
                pre[j]%=mod;
            }

            if(t[j].f==d[i+1])
            {
                int sz=tre.size();
                int dd=min(d[i+1]-d[i]-1,sz);
                for(int k=1;k<=dd;k++)
                {
                    long long sss=0;
                    /*for(int kk=sz-k;kk>=0;kk--)
                    {
                        sss+=pre[tre[kk]]*bc(sz-kk-1,k-1);
                        sss%=mod;
                    }*/
                    sss=f[k];
                    dp[i][j]+=(((sss*invf[k])%mod)*dff[i][k])%mod;
                    dp[i][j]%=mod;
                }
                
                dp[i][j]+=pre[j];
                dp[i][j]%=mod;
            }
            else if(t[j].f<=d[i] && d[i+1]<=t[j].s)
            {
                int sz=tre.size();
                int dd=min(d[i+1]-d[i],sz+1);

                for(int k=2;k<=dd;k++)
                {
                    long long sss=0;
                    /*for(int kk=sz+1-k;kk>=0;kk--)
                    {
                        sss+=pre[tre[kk]]*bc(sz-1-kk,k-2);
                        sss%=mod;
                    }*/
                    sss=gf[k];
                    dp[i][j]+=(((sss*invf[k])%mod)*ff[i][k])%mod;
                    dp[i][j]%=mod;
                }
		
	    dp[i][j]+=pre[j]*(d[i+1]-d[i]);
	    dp[i][j]%=mod;
                tre.push_back(j);
                
                for(int k=dd;k>2;k--)
                {
                	gf[k]+=gf[k-1];
                	gf[k]%=mod;
                }
                gf[2]+=pre[j];
                gf[2]%=mod;
                if(sz+2<=d[i+1]-d[i])
                {
                	gf[sz+2]=pre[tre[0]];
                }
                
                
                dd=min(d[i+1]-d[i]-1,sz);
                for(int k=dd;k>1;k--)
                {
                	f[k]+=f[k-1];
                	f[k]%=mod;
                }
                f[1]+=pre[j];
                f[1]%=mod;
                if(sz+1<=d[i+1]-d[i]-1)
                {
            	f[sz+1]=pre[tre[0]];	
                }
            }
        }
    }

    long long sol=0;
    for(int i=1;i<=n;i++)
    {
        sol+=dp[2*n-1][i];
        sol%=mod;
    }
    cout<<sol<<endl;
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42