SRM592 Div2 Hard - LittleElephantAndArray

違う意味で教育的
キレた

問題

長さnの数列a = {A, A+1, A+2, ..., A+N}がある
LittleElephantくんはこの各要素について何個かの桁を消す
消す桁は0個でも良いが完全に消すことはない
また結果できる数が同じでも消す桁が違えば別の消し方として区別する
(例えば11なら左の1を消しても右の1を消しても1になるけどこれらは別物とする)
最終的に数列aが広義単調増加になるような消し方は何通りあるか

1 <= A <= 10^15
0 <= N <= 100

解法

aの各要素はたかだか16桁だから消し方2^16 ≒ 7*10^4通りを全列挙できる
つまり登場する数字はたかだか7 * 10^6個
これらの数字を頂点として、↓のように各頂点vから「次の要素のうちv以上の数字全て」へ辺を引いたグラフで、仮の始点Sから右端(A+N)の各頂点までのパスの総数の総和が答え

(サンプルにあるA=10、N=2の場合のグラフ)
これをそのままやると画像の通り辺が爆発して終わってしまう
そこで↓の赤線部分のように累積和を導入して、各頂点vからは「次の要素のうちv以上の数字のうち最小のもの」へのみ辺を引くようにすると辺がO(頂点数)になる

ここまで考察してまあ面白い問題だなと思ってたらシステムテストがまるで通らない
めちゃくちゃスタックオーバーフローしてた
dpの配列を節約するのはもちろん、頂点も全部一気に作っちゃうとメモリが足りないからちょっとずつ作る必要がある

この本質じゃないところで頑張らないといけない感じがスッキリしない
15人提出して1人しか通ってないのも納得できる
教育的ではあるけどね

実装

cr(i)はa[i]を削って出来る数字たちを全部numに突っ込むメソッド
a[0], a[1], ..., a[n-1]と見ていくとき、a[0]のときだけはcr(0)とcr(1)を実行し、そうでないときはnum[0]とnum[1]をswapしてからcr(i+1)を実行する
最後i=n-1でcr(n)が実行されるときはnumに1ll<<60(番兵)を突っ込むようにしてある
こうすることで最終的な答えであるΣdp[n-1][i]がdp[n][0]に集約される仕組み

class LittleElephantAndArray {
public:
	ll n, a[111], dp[2][1<<16];
	vector<ll> num[2];

	void cr(int I) {
		string s = to_string(a[I]);
		int l = s.size(), i = I&1;
		num[i].clear();
		if (I==n) {
			num[i].push_back(1ll<<60);
			return;
		}
		reps(j,1,1<<l) {
			ll t = 0;
			rep(k,l) if (j>>k&1) t *= 10, t += s[k]-'0';
			num[i].push_back(t);
		}
		sort(all(num[i]));
	}

	int getNumber(ll A, int N) {
		n = N+1;
		rep(i,n) a[i] = A+i;
		dp[0][0] = 1;
		rep(I,n) {
			int i = I&1;
			if (I==0) cr(0);
			cr(I+1);
			rep(j,num[i].size()) {
				if (j) (dp[i][j] += dp[i][j-1]) %= mod;
				int to = lower_bound(all(num[i^1]), num[i][j]) - num[i^1].begin();
				if (to<num[i^1].size()) (dp[i^1][to] += dp[i][j]) %= mod;
			}
			memset(dp[i], 0, sizeof(dp[i]));
		}
		return dp[n&1][0];
	}
};