Codeforces 1093F. Vasya and Array (DP)

日付: 12月 19, 2018

[Problem - 1093F - Codeforces](https://codeforces.com/contest/1093/problem/F)
## Problem
Given an array <math><semantics><mrow><mi>A</mi></mrow><annotation encoding="application/x-tex">A</annotation></semantics></math>A of <math><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math>n integers, each element is each -1 or between 1 and <math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math>k. You change each -1 into a number between 1 and <math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math>k, and the result array does not contain a range of length <math><semantics><mrow><mi>l</mi><mi>e</mi><mi>n</mi></mrow><annotation encoding="application/x-tex">len</annotation></semantics></math>len of the same number. Calculate how many ways to do this.

**Constraints:** <math><semantics><mrow><mn>1</mn><mo>≤</mo><mi>n</mi><mo>≤</mo><mn>1</mn><msup><mn>0</mn><mn>5</mn></msup><mo separator="true">,</mo><mtext> </mtext><mn>1</mn><mo>≤</mo><mi>k</mi><mo>≤</mo><mn>100</mn><mo separator="true">,</mo><mtext> </mtext><mn>1</mn><mo>≤</mo><mi>l</mi><mi>e</mi><mi>n</mi><mo>≤</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">1\le n \le 10^5,\ 1 \le k \le 100,\ 1 \le len \le n</annotation></semantics></math>1≤n≤105, 1≤k≤100, 1≤len≤n

## Solution
If we define <math><semantics><mrow><msub><mi>f</mi><mrow><mi>i</mi><mo separator="true">,</mo><mi>j</mi><mo separator="true">,</mo><mi>k</mi></mrow></msub></mrow><annotation encoding="application/x-tex">f_{i,j,k}</annotation></semantics></math>fi,j,k as the number of ways to fill <math><semantics><mrow><mi>A</mi><mo>[</mo><mn>1</mn><mo separator="true">,</mo><mi>i</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">A[1,i]</annotation></semantics></math>A[1,i] with the last element is <math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math>j and the length the suffix of the same number is <math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math>k, it seems easy to solve. However, <math><semantics><mrow><mi>l</mi><mi>e</mi><mi>n</mi></mrow><annotation encoding="application/x-tex">len</annotation></semantics></math>len is too large and we cannot include it in dp state.

Let's define:
* <math><semantics><mrow><msub><mi>f</mi><mrow><mi>i</mi><mo separator="true">,</mo><mi>j</mi></mrow></msub></mrow><annotation encoding="application/x-tex">f_{i,j}</annotation></semantics></math>fi,j - The number of valid ways to fill <math><semantics><mrow><mi>A</mi><mo>[</mo><mn>1</mn><mo>⋯</mo><mi>i</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">A[1\cdots i]</annotation></semantics></math>A[1⋯i] with the last element is <math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math>j
* <math><semantics><mrow><msub><mi>s</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">s_i</annotation></semantics></math>si - The number of valid ways to fill <math><semantics><mrow><mi>A</mi><mo>[</mo><mn>1</mn><mo>⋯</mo><mi>i</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">A[1\cdots i]</annotation></semantics></math>A[1⋯i]. <math><semantics><mrow><msub><mi>s</mi><mi>i</mi></msub><mo>=</mo><msubsup><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>k</mi></msubsup><msub><mi>f</mi><mrow><mi>i</mi><mo separator="true">,</mo><mi>j</mi></mrow></msub></mrow><annotation encoding="application/x-tex">s_i = \sum_{j=1}^k f_{i,j}</annotation></semantics></math>si=∑j=1kfi,j
* <math><semantics><mrow><msub><mi>p</mi><mrow><mi>i</mi><mo separator="true">,</mo><mi>j</mi></mrow></msub></mrow><annotation encoding="application/x-tex">p_{i,j}</annotation></semantics></math>pi,j - The rightmost position of a number <math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math>j in <math><semantics><mrow><mi>A</mi><mo>[</mo><mn>1</mn><mo>⋯</mo><mi>i</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">A[1\cdots i]</annotation></semantics></math>A[1⋯i].

Initially, if <math><semantics><mrow><msub><mi>A</mi><mi>i</mi></msub><mo>=</mo><mi>j</mi></mrow><annotation encoding="application/x-tex">A_i=j</annotation></semantics></math>Ai=j or <math><semantics><mrow><msub><mi>A</mi><mi>i</mi></msub><mo>=</mo><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">A_i=-1</annotation></semantics></math>Ai=−1, <math><semantics><mrow><msub><mi>f</mi><mrow><mi>i</mi><mo separator="true">,</mo><mi>j</mi></mrow></msub><mo>=</mo><msub><mi>s</mi><mrow><mi>i</mi><mo>−</mo><mn>1</mn></mrow></msub></mrow><annotation encoding="application/x-tex">f_{i,j} = s_{i-1}</annotation></semantics></math>fi,j=si−1. But when these conditions are met:
* <math><semantics><mrow><mi>i</mi><mo>&gt;</mo><mo>=</mo><mi>l</mi><mi>e</mi><mi>n</mi></mrow><annotation encoding="application/x-tex">i &gt;= len</annotation></semantics></math>i>=len.
* All elements in <math><semantics><mrow><mi>A</mi><mo>[</mo><mi>i</mi><mo>−</mo><mi>l</mi><mi>e</mi><mi>n</mi><mo>+</mo><mn>1</mn><mo>⋯</mo><mi>i</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">A[i-len+1 \cdots i]</annotation></semantics></math>A[i−len+1⋯i] are either -1 or <math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math>j (this can be checked by <math><semantics><mrow><mi>p</mi></mrow><annotation encoding="application/x-tex">p</annotation></semantics></math>p)

There exist cases when <math><semantics><mrow><mi>A</mi><mo>[</mo><mi>i</mi><mo>−</mo><mi>l</mi><mi>e</mi><mi>n</mi><mo>+</mo><mn>1</mn><mo>⋯</mo><mi>i</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">A[i-len+1 \cdots i]</annotation></semantics></math>A[i−len+1⋯i] are all filled to <math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math>j (notice that <math><semantics><mrow><mi>A</mi><mo>[</mo><mi>i</mi><mo>−</mo><mi>l</mi><mi>e</mi><mi>n</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">A[i-len]</annotation></semantics></math>A[i−len] couldn't be <math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math>j because these cases are already substracted at position <math><semantics><mrow><mi>i</mi><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">i-1</annotation></semantics></math>i−1). The number of such bad cases are <math><semantics><mrow><msub><mi>s</mi><mrow><mi>i</mi><mo>−</mo><mi>l</mi><mi>e</mi><mi>n</mi></mrow></msub><mo>−</mo><msub><mi>f</mi><mrow><mi>i</mi><mo>−</mo><mi>l</mi><mi>e</mi><mi>n</mi><mo separator="true">,</mo><mi>j</mi></mrow></msub></mrow><annotation encoding="application/x-tex">s_{i-len}-f_{i-len,j}</annotation></semantics></math>si−len−fi−len,j

## Code
```c++
#include <bits/stdc++.h>
using namespace std;
#define FI(i,a,b) for(int i=(a);i<=(b);++i)
constexpr int madd(int x, int y, int m) { return (0LL + x + y + m + m) % m; }

const int N = 1e5 + 5, M = 998244353;
int n, k, len, C[N], F[N][105], P[N][105], S[N];

int main() {
 scanf("%d%d%d", &n, &k, &len);
 FI(i, 1, n) scanf("%d", C + i);
 FI(i, 1, n) FI(j, 1, k) { P[i][j] = P[i - 1][j]; if (C[i] == j) P[i][j] = i; }
 S[0] = 1;
 FI(i, 1, n) FI(j, 1, k) {
 if (C[i] != -1 && C[i] != j) F[i][j] = 0;
 else {
 F[i][j] = S[i - 1];
 bool ok = true;
 if (i < len) ok = false;
 FI(jj, 1, k) if (jj != j && P[i][jj] > i - len) ok = false;
 if (ok) F[i][j] = madd(F[i][j], madd(-S[i - len], F[i - len][j], M), M);
 }
 S[i] = madd(S[i], F[i][j], M);
 }
 printf("%d\n", S[n]);
}
```

KONGROOの基地

このブログを検索

Codeforces 1093F. Vasya and Array (DP)

コメント

コメントを投稿