Submission #17177505

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define FOE(i, s, t) for (int i = s; i <= t; i++)
#define FOR(i, s, t) for (int i = s; i < t; i++)
#define FOD(i, s, t) for (int i = s; i >= t; i--)

#define LL long long
#define mp make_pair
#define pb push_back

#define K 601
#define M 1000000007

int n;

int a[K];

int b[14], exi[14], rv[14];

LL bigmod(LL a, LL p) {
	if (!p) return 1;
	LL t = bigmod(a, p >> 1);
	
	t = t * t % M;
	if (p & 1) t = t * a % M;
	
	return t;	
}

int l[K], r[K];

vector<pair<int, pair<int, int > > > E;

LL C(LL n, int k) {
	LL ret = 1;
	for (int i = 1; i <= k; i++) {
		ret = ret * (n - i + 1) % M;
		ret = ret * rv[i] % M;
	}
	
	return ret;
}

LL cnt() {
//	if (b[1] != 2 || b[2] != 1 || b[3] != 3) return 0;
	E.clear();
	FOE(i, 1, n) {
		l[i] = l[i - 1];
		
		if (i > 1 && b[i - 1] <= b[i]) l[i]++;
	}
	
//	FOE(i, 1, n) printf("l[%d] = %d\n", i, l[i]);

	FOD(i, n, 1) {
		int u = b[i];
		r[i] = a[u] - l[i];

		if (i != n) r[i] = min(r[i], r[i + 1]);
		E.pb(mp(r[i], mp(-1, i)));
	}
	
	FOE(i, 1, n) if (r[i] <= 0) return 0;
	
	LL cnt[9];
	FOE(i, 1, n + 1) cnt[i] = 1;
	int last = 1;
	
	sort(E.begin(), E.end());
	
	for (auto event : E) {
		int time = event.first;
		int dir = event.second.first;
		int row = event.second.second;
		
		LL cnt2[9];
		FOE(i, 1, n + 1) cnt2[i] = 0;
		
		if (time == last) FOE(i, 1, n + 1) cnt2[i] = cnt[i];
		else {
			FOE(i, 1, n + 1) FOE(j, i, n + 1) {
				LL way = C(time - last - 1 + (j - i), j - i);
				cnt2[j] = (cnt2[j] + cnt[i] * way % M) % M;
			}
		}
		
		cnt2[row] = 0;	
		
	//	FOE(i, 1, n + 1) printf("cnt[%d] = %lld at step %d\n", i, cnt2[i], row);
		
		FOE(i, 1, n + 1) cnt[i] = cnt2[i];
		last = time;
	}
	
	return cnt[n + 1];
}

LL ret = 0;

int dp[14];

void check() {
	FOE(i, 1, n) dp[i] = 0;
	FOE(i, 1, n) {
		int u = b[i];
		dp[u] = 1;
		
		FOE(j, 1, u - 1) {
			dp[u] = max(dp[u], dp[j] + 1);	
		}
	}
	
	int ma = dp[1];
	FOE(i, 1, n) ma = max(ma, dp[i]);
	LL tot = cnt();
	
/*	printf("PERM: ");
	FOE(i, 1, n) printf("%d ", b[i]);
	puts("");
	printf("= %d\n", ma);
*/
//	printf("%lld * %lld\n", tot, ma);
	ret = (ret + tot * ma % M) % M;
}

void gen(int u, int tar) {
	if (u == tar) {
		check();
		return;
	}
	
	FOE(i, 1, n) if (!exi[i]) {
		exi[i] = 1;
		b[u + 1] = i;
		
		gen(u + 1, tar);
		exi[i] = 0;
	//	return;
	}
}

int main() {
	scanf("%d", &n);
	
	FOE(i, 1, n) scanf("%d", &a[i]);
	FOE(i, 1, n + 1) rv[i] = bigmod(i, M - 2);
	
	gen(0, n);
	LL rev = 1;
	FOE(i, 1, n) rev = (rev * bigmod(a[i], M - 2)) % M;
	
//	printf("%lld\n", ret);
	printf("%lld\n", ret * rev % M);
}

Submission Info

Compile Error

./Main.cpp: In function ‘long long int cnt()’:
./Main.cpp:75:7: warning: unused variable ‘dir’ [-Wunused-variable]
   75 |   int dir = event.second.first;
      |       ^~~
./Main.cpp: In function ‘int main()’:
./Main.cpp:145:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  145 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
./Main.cpp:147:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  147 |  FOE(i, 1, n) scanf("%d", &a[i]);
      |               ~~~~~^~~~~~~~~~~~~

Judge Result