Submission #1194416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194416		nouka28	Boat (APIO16_boat)	C++20	100 / 100	829 ms	12520 KiB

boat

#include<bits/stdc++.h>
using namespace std;

// #include<atcoder/all>
// using namespace atcoder;
// using mint=atcoder::modint998244353;

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define rng(i,l,r) for(int i=(l);i<(r);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrng(i,l,r) for(int i=(r)-1;i>=(l);i--)

#define fi first
#define se second
#define all(x) (x).begin(),(x).end()

struct fast_io{fast_io(){cin.tie(nullptr)->sync_with_stdio(false);}}_;

template<long long mod,long long MAX_N>
struct factional_prime{
	long long inv_[MAX_N+1];
    long long fac_[MAX_N+1];
    long long fac_inv_[MAX_N+1];

    factional_prime(){
        inv_[0]=0;inv_[1]=fac_[0]=fac_[1]=fac_inv_[0]=fac_inv_[1]=1;
        for(long long i=2;i<=MAX_N;i++){
            inv_[i]=((mod-mod/i)*inv_[mod%i])%mod;
            fac_[i]=(fac_[i-1]*i)%mod;
            fac_inv_[i]=(fac_inv_[i-1]*inv_[i])%mod;
        }
    }
    long long inv(long long n){
        if(n<0)return 0;
        return inv_[n];
    }
    long long fac(long long n){
        if(n<0)return 0;
        return fac_[n];
    }
    long long finv(long long n){
        if(n<0)return 0;
        return fac_inv_[n];
    }
    long long nCr(long long n,long long r){
        if(n<r||n<0||r<0)return 0;
        return ((fac_[n]*fac_inv_[n-r])%mod*fac_inv_[r])%mod;
    }
    long long nPr(long long n,long long r){
        if(n<r||n<0||r<0)return 0;
        return (fac_[n]*fac_inv_[n-r])%mod;
    }
};

factional_prime<1000000007,509> fp;

signed main(){
	int N;cin>>N;
	vector<int> A(N),B(N);
	rep(i,N)cin>>A[i]>>B[i],B[i]++;

	vector<int> v=A;v.insert(v.end(),all(B));
	sort(all(v));v.erase(unique(all(v)),v.end());

	int m=v.size()-1;
	const int mod=1000000007;

	vector<vector<int>> dp(m,vector<int>(N+1));
	vector<vector<int>> bi(m,vector<int>(N+1));
	rep(i,m){
		bi[i][0]=1;
		rep(j,N){
			bi[i][j+1]=bi[i][j]*(v[i+1]-v[i]-j)%mod*fp.inv(j+1)%mod;
		}
	}

	rep(i,N){
		vector<vector<int>> ndp(m,vector<int>(N+1));
		int sum=1;
		rep(j,m){
			if(A[i]<=v[j]&&v[j+1]<=B[i]){
				ndp[j][1]+=sum;
				ndp[j][1]%=mod;
			}
			rep(k,i+1){
				if(A[i]<=v[j]&&v[j+1]<=B[i]){
					ndp[j][k+1]+=dp[j][k];
					ndp[j][k+1]%=mod;
				}
				ndp[j][k]+=dp[j][k];
				ndp[j][k]%=mod;
				sum+=dp[j][k]*bi[j][k];
				sum%=mod;
			}
		}
		swap(dp,ndp);

		// cout<<"dp : "<<endl;
		// rep(j,m){
		// 	cout<<j<<" : ";
		// 	for(auto&&e:dp[j])cout<<e<<" ";cout<<endl;
		// }
	}

	int ans=0;
	rep(j,m){
		rep(k,N+1){
			ans+=dp[j][k]*bi[j][k];
			ans%=mod;
		}
	}

	cout<<ans<<endl;
}

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