mayoko’s diary

プロコンとかいろいろ。

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;
}