maker

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;

int main() {
    freopen("input.in", "w", stdout);
    puts("5000");
    for (int i = 5000; i; i--) printf("%d ", i + 1 ^ 1);
}

卡到极限答案 $2^{2500}$：

2500 375828023454801203683362418972386504867736551759258677056523839782231681498337708535732725752658844333702457749526057760309227891351617765651907310968780236464694043316236562146724416478591131832593729111221580180531749232777515579969899075142213969117994877343802049421624954402214529390781647563339535024772584901607666862982567918622849636160208877365834950163790188523026247440507390382032188892386109905869706753143243921198482212075444022433366554786856559389689585638126582377224037721702239991441466026185752651502936472280911018500320375496336749951569521541850441747925844066295279671872605285792552660130702047998218334749356321677469529682551765858267502715894007887727250070780350262952377214028842297486263597879792176338220932619489509376

炸掉题解：

https://www.luogu.com.cn/blog/_post/324857 (TLE 11.8s)
https://www.luogu.com.cn/blog/_post/13441 (WA)
https://www.luogu.com.cn/blog/_post/117381 (WA)
https://www.luogu.com.cn/blog/_post/40146 (WA)
https://www.luogu.com.cn/blog/_post/380799 (WA)
https://www.luogu.com.cn/blog/_post/229152 (WA)
https://www.luogu.com.cn/blog/_post/156879 (WA)
https://www.luogu.com.cn/blog/_post/282969 (WA)
https://www.luogu.com.cn/blog/_post/108505 (WA)
https://www.luogu.com.cn/blog/_post/137322 (WA)

不放高精度和打表的还有 py 选手先不管了，不然应该全撤掉。

所以这么做实际上是小常数 $O(n^3)$，那么这个范围下的正解应该是树状数组 $O(n^2\log n)$。

附上能卡进 1s 的压位高精度

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 5e3 + 10;
const int MAXM = 42;
const ll BASE = 1e18;

struct Int {
	ll a[MAXM];
	
	Int(int k = 0) {
		for (int i = MAXM - 1; ~i; i--) a[i] = k % BASE, k /= BASE;
	}
	
	Int operator + (const Int &rhs) const {
		ll t = 0; Int res = *this;
		for (int i = MAXM - 1; ~i; i--) {
			t += res.a[i] + rhs.a[i];
			res.a[i] = t % BASE, t /= BASE;
		}
		return res;
	}
	
	Int operator - (const Int &rhs) const {
		int t = 0; Int res = *this;
		for (int i = MAXM - 1; ~i; i--) {
			t += res.a[i] - rhs.a[i];
			if (t < 0) res.a[i - 1]--, t += BASE;
			res.a[i] = t % BASE, t /= BASE;
		}
		return res;
	}
	
	friend ostream & operator << (ostream &out, const Int &n) {
		int p = 0;
		for (; p < MAXM && !n.a[p]; p++);
		if (p == MAXM) return out << 0;
		for (out << n.a[p++]; p < MAXM; p++) out << setw(4) << setfill('0') << n.a[p];
		return out;
	}
	
	Int & operator += (const Int &rhs) { return *this = *this + rhs; }
	Int & operator -= (const Int &rhs) { return *this = *this - rhs; }
};

int n, a[MAXN], ans;

int dp[MAXN]; Int f[MAXN], sum;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++) {
		f[i] = dp[i] = 1;
		for (int j = 1; j < i; j++) {
			if (a[i] < a[j]) {
				if (dp[i] == dp[j] + 1) f[i] += f[j];
				else if (dp[i] < dp[j] + 1) dp[i] = dp[j] + 1, f[i] = f[j];
			} else if (a[i] == a[j]) f[j] = 0;
		}
		ans = max(ans, dp[i]);
	}
	for (int i = 1; i <= n; i++) if (dp[i] == ans) sum += f[i];
	cout << ans << " " << sum;
}