Bài E - Codeforces Round 62 (Div.2)

Bài E:
Đề bài: Chúng ta kí hiệu rằng một mảng b nào đó là tồi tệ nếu nó chứa một mảng con b(l),b(l+1),...,b(r) với độ dài lẻ và lớn hơn 1 (l<r và r-l+1 là số lẻ) thỏa mãn $\forall i\in \left\{0,1,...,r-l\right\} b_{l+i}=b_{r-i}$.
Nếu một mảng không xấu, thì đó mảng tốt.
Bây giờ bạn được cho một mảng a(1),a(2),...,a(n). Một vài phần tử được thay thế bằng -1. Tính số mảng tốt bạn có thể đạt được bằng cách thay mỗi số -1 bằng 1 số nguyên nào đó từ 1 đến k.
Bởi vì câu trả lời có thể rất lớn, in ra nó modulo 998244353
Đầu vào:
+ Dòng đầu tiên chứa hai số nguyên n và k (2<=n,k<=2.10^5) - chiều dài của mảng a và kích thước của "alphabet"
+ Dòng thứ 2 chứa n số nguyên a(1),a(2),...,a(n) (a(i)=-1 hoặc 1<=a(i)<=k)- mảng a.
Đầu ra:
In ra một số nguyên - số mảng tốt bạn có thể đạt được , modulo 998244353.
Ví dụ:
Đầu vào:
2 3
-1 -1
Đầu ra:
9
/**/
Đầu vào:
5 2
1 -1 -1 1 2
Đầu ra:
0
/**/
Đầu vào:
5 3
1 -1 -1 1 2
Đầu ra: 2
/**/
Đầu vào:
4 200000
-1 -1 12345 -1
Đầu ra:
735945883.
Hướng dẫn:
 Đầu tiên, mảng chứa một mảng con đối xứng >=3 tương đương với mảng chứa một mảng con đối xứng có độ dài là 3.
Vì vậy, chúng ta cần tính số mảng mà không đối xứng có độ dài là 3. Điều này tương đương với mảng mà a[i]#a[i+2] với mọi i hợp lý.
Chú ý ràng, i và i+2 có cùng tính chẵn lẽ, vì vậy tất cả vị trí lẻ và vị trí chẵn trong mảng độc lập nhau, và câu trả lời là tích các cách chọn các số ở vị trí lẻ, và số cách chọn các số ở vị trí chẵn.
Về mặt tương đương hình thái điều kiện, a[i]#a[i+1] và chúng ta cần tính tất cả các cách để thay các số -1 bằng một cách nào đó các cặp phần tử liên tiếp là khác nhau.
  Để tính nó, chúng ta hãy nhìn vào chuỗi các số (-1) liên tiếp. Họ sẽ thấy rằng a,-1,-1,...,-1,b với l số (-1), ở đây a và b là các số nguyên dương (trường hợp a ở đây không có thể xét như k.(a,-1,-1,...,b với l-1 số -1)), trường hợp b rỗng được giải theo cách tương tự.
  Cuối cùng chúng ta cần tính số các dãy như vậy. Có hai loại dãy chúng ta cần xét tới đó là a,-1,..,-1,a (đầu và cuối giống nhau) và a,-1,-1,...,-1,b (đầu và cuối khác nhau). Giá trị chính xác của a và b không phải là vấn đề.
  Chúng ta sẽ tìm hai giá trị (đặt tên chúng là cntSame và cntDiff) với l số (-1) liên tiếp với thời gian O(log(l)). Các giá trị cơ sở: cntSame(0)=0,cntDiff(0)=1.
  Chúng ta thử chọn giá trị của -1 nằm ở giữa của dãy : Nếu l mod 2=1, thì chúng ta có thể tách thành hai dãy có độ dài [l/2] và cntSame(l)=cntSame(l/2)^2+(k-1).cntDiff(l/2)^2 và cntDiff(l)=2.cntSame(l/2).cntDiff(l/2)+(k-2).cntDiff(l/2)^2.
Nếu l mod 2= 1thì chỉ cần lặp giá trị cuối cùng -1m thì cntSame(l)=(k-1).cntDiff(l-1) và cntDiff(l)=cntSame(l-1)+(k-2).cntDiff(l-1).
Độ phức tạp cuối cùng là O(n).
Lời giải:

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;
typedef pair<int, int> pt;

const int MOD = 998244353;
int norm(int a) {
    while(a >= MOD) a -= MOD;
    while(a < 0) a += MOD;
    return a;
}
int mul(int a, int b) {
    return int(a * 1ll * b % MOD);
}

int n, k;
vector<int> a;

inline bool read() {
    if(!(cin >> n >> k))
        return false;
    a.resize(n);
    fore(i, 0, n)
        cin >> a[i];
    return true;
}

pair<int, int> calc(int len) {
    if(len == 0) return {0, 1};
    if(len & 1) {
        auto res = calc(len >> 1);
        return {norm(mul(res.x, res.x) + mul(k - 1, mul(res.y, res.y))),
                norm(mul(2, mul(res.x, res.y)) + mul(k - 2, mul(res.y, res.y)))};
    }
    auto res = calc(len - 1);
    return {mul(k - 1, res.y), norm(res.x + mul(k - 2, res.y))};
}

vector<int> curArray;

int calcSeg(int l, int r) {
    if(r >= sz(curArray)) {
        int len = r - l - 1, cf = 1;
        if(l < 0)
            len--, cf = k;
        if(len == 0) return cf;

        auto res = calc(len - 1);
        return mul(cf, norm(res.x + mul(k - 1, res.y)));
    }
    if(l < 0) {
        if(r - l == 1) return 1;
        auto res = calc(r - l - 2);
        return norm(res.x + mul(k - 1, res.y));
    }
    auto res = calc(r - l - 1);
    return curArray[l] == curArray[r] ? res.x : res.y;
}

inline void solve() {
    int ans = 1;
    fore(k, 0, 2) {
        curArray.clear();
        for(int i = 0; 2 * i + k < n; i++)
            curArray.push_back(a[2 * i + k]);

        int lst = -1;
        fore(i, 0, sz(curArray)){
            if(curArray[i] == -1) continue;
            ans = mul(ans, calcSeg(lst, i));
            lst = i;
        }
        ans = mul(ans, calcSeg(lst, sz(curArray)));
    }
    cout << ans << endl;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);

    if(read()) {
        solve();

#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}