Codeforces Round #326 (Div. 1) B. Duff in Beach
解法
dp[k][i] = (数列 a をつなげた個数が k 個で, 末尾の添字が i となるような場合の数) とします。
これがわかれば, 数列が k 個つないでいるようなものが大体 p = L/N - k 個あるのでそれを数えて dp[k][i] * p の和を取っていけば良いです。
ということで, dp[k][i] を求めます。
dp[k][i] は, a[j] <= a[i] となる j について, dp[k-1][j] の和になるので, これの値を cnt[] として求めます。
これは, a[i] の lower_bound を計算しておけば(この lower_bound の値を a[i] として保持しておく), まず cnt[a[i]] に dp[k-1][i] を足しこんでいき, その後 cnt[p] に cnt[0] から cnt[p-1] の和を足しこんでいけば, 求めていくことが出来ます。
dp[k][i] = cnt[a[i]] となるので, これを順次求めていけば良いです。
得た知見
- cnt[] をつかって累積和的なものを取るテクニック, 何回か見てるけど自力で使ったことがないかも
const int MAXN = 1000100; const int MOD = 1e9+7; int N, K; ll L; int a[MAXN]; vector<int> dp[MAXN]; inline void add(int& x, int y) { (x += y) %= MOD; } int main() { cin >> N >> L >> K; vector<int> vals; for (int i = 0; i < N; i++) { scanf("%d", a+i); vals.push_back(a[i]); } for (int i = 0; i <= K; i++) dp[i].resize(N+1); sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); for (int i = 0; i < N; i++) { a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin(); dp[1][i] = 1; } int num = vals.size(); vector<int> cnt(num); for (int k = 2; k <= K; k++) { for (int i = 0; i < num; i++) cnt[i] = 0; for (int i = 0; i < N; i++) add(cnt[a[i]], dp[k-1][i]); for (int i = 1; i < num; i++) add(cnt[i], cnt[i-1]); for (int i = 0; i < N; i++) dp[k][i] = cnt[a[i]]; } ll ans = 0; for (int k = 1; k <= K; k++) { for (int i = 0; i < N; i++) { ll b = L/N; if (L%N > i) b++; b -= k-1; if (b > 0) (ans += (b%MOD)*dp[k][i]) %= MOD; } } cout << ans << endl; return 0; }