Submission #17172245


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define FORR2(x,y,arr) for(auto& [x,y]:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
int A[101];
const ll mo=1000000007;
vector<int> V;
ll ret=0;

vector<int> LIS(vector<int>& v) {
	int i,N=v.size();
	vector<int> dp(N,1<<30),id(N);
	FOR(i,v.size()) {
		id[i] = lower_bound(dp.begin(),dp.end(),v[i]) - dp.begin();
		// id[i] = lower_bound(dp.begin(),dp.end(),v[i]+1) - dp.begin(); //こうすると同じ値も許容する
		dp[id[i]] = v[i];
	}
	int nl = *max_element(id.begin(),id.end());
	vector<int> ret(nl+1);
	FOR(i,N) if(id[N-1-i] == nl) ret[nl--] = v[N-1-i];
	return ret;
}

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll comb(int P_,int Q_) {
	if(P_<0 || Q_<0 || Q_>P_) return 0;
	ll p=1,q=1;
	Q_=min(Q_,P_-Q_);
	for(int i=1;i<=Q_;i++) p=p*P_%mo, q=q*i%mo,P_--;
	
	return p*modpow(q,mo-2)%mo;
}


ll hoge(vector<int>& P,int ma,vector<int>& Q) {
	if(Q.size()<=ma) {
		ll ret=0;
		for(int i=(Q.empty()?0:Q.back());i<V.size();i++) {
			Q.push_back(i);
			ret+=hoge(P,ma,Q);
			Q.pop_back();
		}
		return ret%mo;
	}
	
	int ok=1;
	int i;
	int num[7]={};
	FORR(q,Q) num[q]++;
	FOR(i,N) {
		int tar=Q[P[i]];
		if(V[tar]>A[i]) return 0;
	}
	int pre=0;
	ll pat=1;
	FOR(i,V.size()) {
		int cur=V[i]-pre;
		if(num[i]>cur) return 0;
		pat=pat*comb(cur,num[i])%mo;
		pre=V[i];
	}
	/*
	cout<<"!"<<endl;
	FORR(p,P) cout<<p;
	cout<<" ";
	FORR(q,Q) cout<<q;
	cout<<" "<<pat<<endl;
	*/
	
	return pat;
}

void go(vector<int>& P) {
	int lis=LIS(P).size();
	int ma=*max_element(ALL(P));
	vector<int> Q;
	ll pat=hoge(P,ma,Q);
	//FORR(p,P) cout<<p;
	//if(pat) cout<<" "<<lis<<" "<<pat<<endl;
	(ret+=lis*pat)%=mo;
	
}

void dfs(int cur,vector<int>& P) {
	if(cur==N) {
		set<int> S;
		FORR(p,P) S.insert(p);
		int gr=0;
		while(S.count(gr)) gr++;
		if(S.size()==gr) {
			go(P);
		}
		return;
	}
	for(int i=0;i<=5;i++) {
		P.push_back(i);
		dfs(cur+1,P);
		P.pop_back();
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		V.push_back(A[i]);
	}
	sort(ALL(V));
	V.erase(unique(ALL(V)),V.end());
	vector<int> P;
	dfs(0,P);
	
	FOR(i,N) ret=ret*modpow(A[i])%mo;
	cout<<ret<<endl;
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}

Submission Info

Submission Time
Task E - Random LIS
User kmjp
Language C++ (GCC 9.2.1)
Score 700
Code Size 2944 Byte
Status AC
Exec Time 64 ms
Memory 3652 KB

Compile Error

./Main.cpp: In function ‘std::vector<int> LIS(std::vector<int>&)’:
./Main.cpp:7:28: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    7 | #define FOR(x,to) for(x=0;x<(to);x++)
      |                            ^
./Main.cpp:25:2: note: in expansion of macro ‘FOR’
   25 |  FOR(i,v.size()) {
      |  ^~~
./Main.cpp: In function ‘ll hoge(std::vector<int>&, int, std::vector<int>&)’:
./Main.cpp:53:13: warning: comparison of integer expressions of different signedness: ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
   53 |  if(Q.size()<=ma) {
      |     ~~~~~~~~^~~~
./Main.cpp:55:37: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   55 |   for(int i=(Q.empty()?0:Q.back());i<V.size();i++) {
      |                                    ~^~~~~~~~~
./Main.cpp:7:28: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    7 | #define FOR(x,to) for(x=0;x<(to);x++)
      |                            ^
./Main.cpp:73:2: note: in expansion of macro ‘FOR’
   73 |  FOR(i,V.size()) {
      |  ^~~
./Main.cpp:63:6: warning: unused variable ‘ok’ [-Wunused-variable]
   63 |  int ok=1;
      |      ^~
./Main.cpp: In function ‘void dfs(int, std::vector<int>&)’:
./Main.cpp:107:14: warning: comparison of integer expressions of different signedness: ‘std::set<int>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  107 |   if(S.size()==gr) {
      |      ~~~~~~~~^~~~
./Main.cpp: In function ‘void solve()’:
./Main.cpp:120:8: warning: unused variable ‘j’ [-Wunused-variable]
  120 |  int i,j,k,l,r,x,y; string s;
      |        ^
./Main.cpp:120:10: warning: unused variable ‘k’ [-Wunused-variable]
  1...

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 3
AC × 34
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt AC 29 ms 3652 KB
02.txt AC 55 ms 3500 KB
03.txt AC 8 ms 3620 KB
04.txt AC 31 ms 3576 KB
05.txt AC 6 ms 3536 KB
06.txt AC 46 ms 3516 KB
07.txt AC 28 ms 3620 KB
08.txt AC 30 ms 3516 KB
09.txt AC 28 ms 3628 KB
10.txt AC 19 ms 3580 KB
11.txt AC 4 ms 3496 KB
12.txt AC 18 ms 3576 KB
13.txt AC 2 ms 3612 KB
14.txt AC 2 ms 3508 KB
15.txt AC 2 ms 3604 KB
16.txt AC 22 ms 3572 KB
17.txt AC 28 ms 3520 KB
18.txt AC 32 ms 3620 KB
19.txt AC 23 ms 3516 KB
20.txt AC 26 ms 3504 KB
21.txt AC 64 ms 3652 KB
22.txt AC 15 ms 3620 KB
23.txt AC 25 ms 3560 KB
24.txt AC 20 ms 3588 KB
25.txt AC 20 ms 3592 KB
26.txt AC 23 ms 3504 KB
27.txt AC 24 ms 3648 KB
28.txt AC 32 ms 3520 KB
29.txt AC 31 ms 3456 KB
30.txt AC 36 ms 3572 KB
31.txt AC 34 ms 3516 KB
s1.txt AC 3 ms 3508 KB
s2.txt AC 3 ms 3576 KB
s3.txt AC 59 ms 3620 KB