Submission #404441

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
404441	2021-05-14T12:15:55 Z	CursedCode	Boat (APIO16_boat)	C++14	Compilation error	0 ms	0 KB

boat

#include <bits/stdc++.h>
#define ll long long
const ll MOD=1000000007;
using namespace std;
ll n,k;
ll l[1005],r[1005],dp[1005][1005],val[1005],cnt[1005][1005],c[1005][1005],sum[1005][1005],len[1005],C[1005][1005];
unordered_map<ll,ll>um;
set<ll>s;
lld pw(lld a, lld b){
    if(b<=0)return 1;
    lld g=pw(a,b/2);
    g=(g*g)%mod;
    if(b%2)g=(g*a)%mod;
    return g;
}
int main(){
	cin >> n;
	for(ll i=1;i<=n;i++){
		cin >> l[i] >> r[i];
		s.insert(l[i]);
		s.insert(r[i]+1);
		um[l[i]] = um[r[i] + 1] = 0;
	}
	for(auto i=s.begin();i!=s.end();++i){
		um[*i]=++k;
		val[k]=*i;
		if(k>1) len[k-1]=val[k]-val[k-1];
	}
	for(ll i=0;i<=n;i++){
		C[i][0]=1;
		for(ll j=1;j<=i;j++){
			C[i][j]=C[i][j-1]*(i+1-j);
			C[i][j]%=MOD;
			C[i][j]*=power(j,MOD-2);
			C[i][j]%=MOD;
		}
	}
	for (ll j=0;j<k;j++) c[0][j] = 1;
	for (ll j=0;j<k;j++) C[0][j] = 1;
	for(ll i=1;i<k;i++){
		c[i][0]=1;
		for(ll j=1;j<=min(len[i],n);j++){
			c[i][j]=c[i][j-1]*(len[i]+1-j);
			c[i][j]%=MOD;
			c[i][j]*=power(j,MOD-2);
			c[i][j]%=MOD;
			// cout << i << ' ' << j << ' ' << c[i][j] << '\n';
		}
	}
	for(ll i=1;i<k;i++){
		for(ll j=1;j<=min(len[i],n);j++){
			ll res=0;
			for(ll t=1;t<=j;t++){
				res+=(c[i][t]*C[j-1][t-1]);
				res%=MOD;
			}
			sum[i][j]=res;
		}
	}
	for(ll i=1;i<=n;i++){
		for(ll j=1;j<k;j++){
			if(l[i]<=val[j] && val[j]<=r[i]){
				cnt[i][j]=cnt[i-1][j]+1;
			}
			else cnt[i][j]=cnt[i-1][j];
			// cout << i << ' ' << j << ' ' << cnt[i][j] << '\n';
		}
	}
	for(ll i=0;i<=n;i++){dp[i][0]=1;}
	for(ll i=0;i<=n;i++){
		for(ll j=1;j<k;j++){
			dp[i][j]+=dp[i][j-1];
			dp[i][j]%=MOD;
			for(ll t=0;t<i;t++){
				if(l[t+1]<=val[j] && val[j]<=r[t+1]){
					ll p=cnt[i][j]-cnt[t][j];
					dp[i][j]+=(dp[t][j-1]*sum[j][min(p,len[j])]);
					dp[i][j]%=MOD;
				}
				// if(i==1 && j==2) cout << cnt[i][j] << '\n';
			}
			// cout << i << ' ' << j << ' ' << dp[i][j] << '\n';
		}
	}
	cout << (dp[n][k-1]-1)%MOD;
}

Compilation message

boat.cpp:9:1: error: 'lld' does not name a type; did you mean 'll'?
    9 | lld pw(lld a, lld b){
      | ^~~
      | ll
boat.cpp: In function 'int main()':
boat.cpp:34:13: error: 'power' was not declared in this scope
   34 |    C[i][j]*=power(j,MOD-2);
      |             ^~~~~
boat.cpp:45:13: error: 'power' was not declared in this scope
   45 |    c[i][j]*=power(j,MOD-2);
      |             ^~~~~