TopCoder SRM 592 Div2 Hard LittleElephantAndArray

最近のDiv2 Hardの中では若干難しいけど、それでも自分で解き方が思いつかないレベルではなかった。
http://community.topcoder.com/stat?c=problem_statement&pm=12704

問題

数AとNが与えられたとき、A～(A+N)で作られる数列を考える。
各数列からいくつか数字を取り除き、非減少数列になる組み合わせ数を答えよ。

解法

数列の各要素について、そこから数字を取り除いて生成できる値を考える。
Aが最大16桁なので、生成できる値は高々2^16-1通り。

A～A+iから生成できる数列のうち、最後のA+iから生成した数値がvであるときの組み合わせ数をDP[A+i][v]と考えて、あとはA+iとA+i+1の間でDPしていけばよい。
A+i+1から生成できるwに対し、DP[A+i+1][w]はv<=wであるDP[A+i][v]の和である。

上記処理は普通に行うとvとwの組み合わせ分で(2^16)*(2^16)通りかかってでTLEしてしまうけど、DP[A+i][v]の累積和をとっておけば(2^16)*log(2^16)ですむ。

なお、最初コードを書いたらDP処理よりもA～(A+N)すべてで2^16-1個分数字を生成する処理の方が重い。
なので、以下では最後の1ケタだけが違う場合は前の結果を再利用して生成を高速化した。
また、一気に作るとメモリもあふれるので、1回ずつ作るようにしている。

ll mo=1000000007;
vector<ll> S[2];
ll dpdp[2][100000];

class LittleElephantAndArray {
	public:
	ll p10[20];
	vector<ll > create(ll V) {
		static ll prev=-1;
		static vector<ll> SV;
		int i,x;
		
		if(prev!=V/10) {
			ll t=V/10;
			int d=0,ma;
			SV.clear();
			while(t) t/=10,d++;
			for(int ma=1;ma<1<<d;ma++) {
				ll v=0;
				int nd=0,cd;
				FOR(cd,d) if(ma & (1<<cd)) v+=((V/10/p10[cd])%10)*p10[nd++];
				SV.push_back(v);
			}
			prev=V/10;
		}
		
		vector<ll> RV;
		FOR(i,SV.size()) RV.push_back(SV[i]),RV.push_back(SV[i]*10+V%10);
		RV.push_back(V%10);
		
		sort(RV.begin(),RV.end());
		return RV;
	}
	
	int getNumber(long long A, int N) {
		int i,x,y;
		p10[0]=1;
		FOR(i,15) p10[i+1]=p10[i]*10;
		
		S[0]=create(A);
		FOR(i,S[0].size()) dpdp[0][i]=1;
		
		FOR(i,N) {
			int cur=i%2,tar=(i+1)%2;
			S[tar]=create(A+i+1);
			
			for(x=1;x<S[cur].size();x++) dpdp[cur][x] = ( dpdp[cur][x]+dpdp[cur][x-1]) % mo;
			ZERO(dpdp[tar]);
			
			FOR(x,S[tar].size()) {
				vector<ll>::iterator vit=upper_bound(S[cur].begin(),S[cur].end(),S[tar][x]);
				if(vit!=S[cur].begin()) dpdp[tar][x] = dpdp[cur][vit-S[cur].begin()-1];
			}
		}
		
		ll ret=0;
		FOR(i,S[N%2].size()) ret+=dpdp[N%2][i];
		return (int)(ret%mo);
	}
};

まとめ

上記コードで最大1秒以上かかるのだけど、もっと軽くできるのかな？