Codeforces #326 Div1 B. Duff in Beach

問題設定がややこしいが、わかってしまえば簡単。
http://codeforces.com/contest/587/problem/B

問題

とても長いL要素の数列B[0..(L-1)]がある。
この数列はN要素の数列A[0..(N-1)]を繰り返して作られたもので、B[x]=A[x%N]の関係にある。

Bのうち最大K要素の部分列を作りたい。
部分列の構成要素がB[I[0]], B[I[1]], B[I[2]], ... B[I[x-1]]と表現できるとすると、Iは以下の条件を満たす数列である。

• floor(I[i]/n) + 1 = floor(I[i+1]/n)
• B[I[i]] ≦ B[I[i+1]]

条件を満たすIは何通り作れるか。

解法

条件は一見ややこしいが、言い換えると以下のとおりである。

• BはAをL/N回繰り返したものである。(L%N分ちょっとあまるが)
• そこから、Aを連続x回分抜き出したものを選ぶ。(約L/N-x+1通り)
• そのx回分の繰り返しから、1個ずつ要素を抜き出して順に並べると、その要素が昇順になるようにしたい。
  • さらに言い換えると、「Aの要素から1個取り出すことをx回行い、順に並べるとそれらが昇順になるようにする」である。

上２つの事は後回しにして、最後の行の内容に関して、Iの長さxについて1≦x≦Kを順に処理して行けば良い。
最初にAを座標圧縮しておくと、累積和を使うことで最後の条件を満たす組み合わせができる。
各組み合わせに関し（L/N-x+1）を掛けていけば良い。
ただしL%Nが非0の場合、一部の要素を末尾にする場合で「Aを連続x回分抜き出したものを選ぶ」の選び方が１ずれるので注意。
(コード中len=(L/N)+(x

int N,K,NN;
ll L;
int A[1010101];
int num[1010101];
int B[1010101];
ll mo=1000000007;
ll ret;
vector<int> V;
ll dp[2][1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L>>K;
	
	V.push_back(0);
	FOR(i,N) cin>>A[i], V.push_back(A[i]);
	sort(ALL(V));
	V.erase(unique(ALL(V)),V.end());
	FOR(i,N) A[i]=lower_bound(ALL(V),A[i])-V.begin();
	NN=V.size();
	
	FOR(i,NN+1) dp[0][i]=1;
	for(i=1;i<=K;i++) {
		int tar=i&1,cur=tar^1;
		FOR(x,NN+1) dp[tar][x]=0;
		FOR(x,N) {
			dp[tar][A[x]] += dp[cur][A[x]];
			if(dp[tar][A[x]]>=mo) dp[tar][A[x]]-=mo;
			
			ll len=(L/N)+(x<L%N);
			if(len>=i) ret += dp[cur][A[x]]*((len+1-i)%mo)%mo;
		}
		for(x=1;x<=NN;x++) {
			dp[tar][x]+=dp[tar][x-1];
			if(dp[tar][x]>=mo) dp[tar][x]-=mo;
		}
	}
	
	cout<<ret%mo<<endl;
}

まとめ

問題文がややこしいけど、同等に厳密でわかりやすく書く書き方も思いつかないな…。