제출 #76782

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
76782		vex	Boat (APIO16_boat)	C++14	58 / 100	2055 ms	5180 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];
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);
}
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;
}


int n;
int d[2*maxn];
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);

    precalc();
    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);

    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;
                    }
                    dp[i][j]+=sss*bc(d[i+1]-d[i]-1,k);
                    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;
                    }
                    dp[i][j]+=sss*bc(d[i+1]-d[i],k);
                    dp[i][j]%=mod;
                }
		
	    dp[i][j]+=pre[j]*(d[i+1]-d[i]);
	    dp[i][j]%=mod;
                tre.push_back(j);
            }
            /*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++)
                {
                    dp[i][j]+=bc(d[i+1]-d[i]-1,k)*f[k];
                    dp[i][j]%=mod;
                }

                dp[i][j]+=pre[j];
            }

            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);

                dp[i][j]+=(d[i+1]-d[i])*pre[j];
                dp[i][j]%=mod;

                for(int k=2;k<=dd;k++)
                {
                    dp[i][j]+=bc(d[i+1]-d[i],k)*gf[k];
                    dp[i][j]%=mod;
                }

                for(int k=dd;k>2;k--)
                {
                    gf[k]+=gf[k-1];
                    gf[k]%=mod;
                }
                gf[2]+=pre[j];
                gf[2]%=mod;

                ///!!!!!
                ///BAGA OVDE

                tre.push_back(j);
                sz++;
                if(sz+1<=d[i+1]-d[i])
                {
                    gf[sz+2]=pre[tre[0]];
                }


                for(int k=dd;k>1;k--)
                {
                    f[k]+=f[k-1];
                    f[k]%=mod;
                }
                f[1]+=pre[j];
                f[1]%=mod;
                if(sz<=d[i+1]-d[i])
                {
                    f[sz]=pre[tre[0]];
                }
            }*/
        }


        //for(int j=1;j<=n;j++)cout<<pre[j]<<" ";cout<<endl;
    }


    //for(int i=1;i<=n;i++)cout<<i<<"   "<<t[i].f<<" "<<t[i].s<<endl;
    //for(int i=1;i<=2*n;i++)cout<<d[i]<<" ";cout<<endl;
    /*for(int i=0;i<=2*n-1;i++)
    {
        cout<<i<<"     ";
        for(int j=1;j<=n;j++)cout<<dp[i][j]<<" ";
        cout<<endl;
    }*/


    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: 0 / 42