SDOI2019

https://www.luogu.com.cn/article/vfy9p0b1

#include<bits/stdc++.h>
using namespace std;
#define gc getchar()
#define pc putchar
#define li long long
inline li read(){
    li x = 0,y = 0,c = gc;
    while(!isdigit(c)) y = c,c = gc;
    while(isdigit(c)) x = (x << 1) + (x << 3) + (c ^ '0'),c = gc;
    return y == '-' ? -x : x;
}
inline void print(li q){
    if(q < 0) pc('-'),q = -q;
    if(q >= 10) print(q / 10);
    pc(q % 10 + '0');
}
const li mo = 1000000009;
li n,c;
int a[100010],b[100010];
int wz[100010],ft;
li f[100010],g[100010][5],tp[100010];
li t[400010],c1[400010],c2[400010],c3[400010];
#define ls q << 1
#define rs q << 1 | 1
#define ln ls,l,mid
#define rn rs,mid + 1,r
#define md int mid = l + r >> 1
inline void build(int q,int l,int r){
    c1[q] = -1;c2[q] = 1;c3[q] = 0;
    if(l == r){
        t[q] = f[l];return;
    }
    md;
    build(ln);build(rn);
    t[q] = (t[ls] + t[rs]) % mo;
}
inline void ud(li x,int op,int q,int l,int r){
    if(op == 1){
        c1[q] = x;c2[q] = 1;c3[q] = 0;t[q] = x * (r - l + 1) % mo;
    }
    else if(op == 2){
        (c2[q] *= x) %= mo;(c3[q] *= x) %= mo;(t[q] *= x) %= mo;
    }
    else{
        (c3[q] += x) %= mo;(t[q] += x * (r - l + 1)) %= mo;
    }
}
inline void ud(li x,int op){ud(x,op,1,1,c);}
inline void ps(int q,int l,int r){
    md;
    if(c1[q] != -1){
        ud(c1[q],1,ln);ud(c1[q],1,rn);c1[q] = -1;
    }
    if(c2[q] != 1){
        ud(c2[q],2,ln);ud(c2[q],2,rn);c2[q] = 1;
    }
    if(c3[q]){
        ud(c3[q],3,ln);ud(c3[q],3,rn);c3[q] = 0;
    }
}
inline void xg(int ax,li x,int op,int q,int l,int r){
    if(l == r){
        ud(x,op,q,l,r);return;
    }
    ps(q,l,r);md;
    if(mid >= ax) xg(ax,x,op,ln);
    else xg(ax,x,op,rn);
    t[q] = (t[ls] + t[rs]) % mo;
}
inline void xg(int ax,li x,int op){xg(ax,x,op,1,1,c);}
inline li cx(int x,int q,int l,int r){
    if(l == r) return t[q];
    ps(q,l,r);md;
    if(mid >= x) return cx(x,ln);
    return cx(x,rn);
}
inline li cx(int x){return cx(x,1,1,c);}
int main(){
    int i,j,u,v,w;
    li s,x,y;
    n = read();c = read();
    for(i = 1;i <= n;++i) a[i] = read();for(i = 1;i <= n;++i) b[i] = read();
    for(i = 1;i <= n;++i){
        if(a[i] || b[i]) wz[++ft] = i;
        if(a[i] && a[i] == b[i]){
            pc('0');pc('\n');return 0;
        }
        if(i < n && ((a[i] && a[i] == a[i + 1]) || (b[i] && b[i] == b[i + 1]))){
            pc('0');pc('\n');return 0;
        }
    }
    if(!ft){
        li as = c * (c - 1) % mo;
        for(i = 2;i <= n;++i) (as *= (c - 1 + (c - 2) * (c - 2) % mo) % mo) %= mo;
        print(as);pc('\n');return 0;
    }
    
    g[1][1] = g[1][3] = g[1][4] = 1;
    for(i = 2;i <= n;++i){
        g[i][0] = (g[i - 1][1] + g[i - 1][3] * (c - 2) * 2 + g[i - 1][4] * (c - 2) % mo * (c - 3)) % mo;
        g[i][1] = (g[i - 1][0] + g[i - 1][2] * (c - 2) * 2 + g[i - 1][4] * (c - 2) % mo * (c - 3)) % mo;
        g[i][2] = (g[i - 1][1] + g[i - 1][2] * (c - 2) + g[i - 1][3] * (c - 2 + c - 3) + g[i - 1][4] * (c - 3) % mo * (c - 3)) % mo;
        g[i][3] = (g[i - 1][0] + g[i - 1][3] * (c - 2) + g[i - 1][2] * (c - 2 + c - 3) + g[i - 1][4] * (c - 3) % mo * (c - 3)) % mo;
        g[i][4] = (g[i - 1][0] + g[i - 1][1] + g[i - 1][2] * (c - 3) * 2 + g[i - 1][3] * (c - 3) * 2 + g[i - 1][4] * (c - 3 + (c - 4) * (c - 4) % mo)) % mo;
    } 
    
    if(wz[1] == 1){
        if(a[1] && b[1]) f[b[1]] = 1;
        else if(a[1]){
            for(i = 1;i <= c;++i) if(i != a[1]) f[i] = 1;
        } 
        else{
            for(i = 1;i <= c;++i) if(i != b[1]) f[i] = 1;
        } 
    }
    else{
        int u = wz[1];
        if(a[u] && b[u]) f[b[u]] = (g[u - 1][0] + g[u - 1][1] + g[u - 1][2] * (c - 2) * 2 + g[u - 1][3] * (c - 2) * 2 + g[u - 1][4] * (c - 2) % mo * (c - 3)) % mo;
        else if(a[u]){
            for(i = 1;i <= c;++i) if(i != a[u]) f[i] = (g[u - 1][0] + g[u - 1][1] + g[u - 1][2] * (c - 2) * 2 + g[u - 1][3] * (c - 2) * 2 + g[u - 1][4] * (c - 2) % mo * (c - 3)) % mo;
        } 
        else{
            for(i = 1;i <= c;++i) if(i != b[u]) f[i] = (g[u - 1][0] + g[u - 1][1] + g[u - 1][2] * (c - 2) * 2 + g[u - 1][3] * (c - 2) * 2 + g[u - 1][4] * (c - 2) % mo * (c - 3)) % mo;
        } 
    }
    build(1,1,c);
    
    for(i = 2;i <= ft;++i){
        w = wz[i] - wz[i - 1];s = t[1];
        if(a[wz[i]] && b[wz[i]]){
            u = a[wz[i]];j = b[wz[i]];x = cx(u);y = cx(j);ud(0,1);
            if(a[wz[i - 1]]){
                v = a[wz[i - 1]];
                if(v == u) xg(j,(y * g[w][0] + (s - y + mo) * g[w][2]) % mo,1);
                else if(v == j) xg(j,(x * g[w][1] + (s - x + mo) * g[w][3]) % mo,1);
                else xg(j,(x * g[w][3] + y * g[w][2] + (s - x - y + mo + mo) * g[w][4]) % mo,1);
            }
            else{
                v = b[wz[i - 1]];
                if(v == u) xg(j,(y * g[w][1] + (s - y + mo) * g[w][3]) % mo,1);
                else if(v == j) xg(j,(x * g[w][0] + (s - x + mo) * g[w][2]) % mo,1);
                else xg(j,(x * g[w][2] + y * g[w][3] + (s - x - y + mo + mo) * g[w][4]) % mo,1);
            }
        }
        else if(a[wz[i]]){
            u = a[wz[i]];x = cx(u);
            if(a[wz[i - 1]]){
                v = a[wz[i - 1]];
                if(v == u){
                    ud(g[w][0] - g[w][2] + mo,2);ud(s * g[w][2] % mo,3);
                }
                else{
                    ud(g[w][2] - g[w][4] + mo,2);ud((x * g[w][3] + s * g[w][4] - x * g[w][4] % mo + mo) % mo,3);xg(v,(x * g[w][1] + (s - x + mo) * g[w][3]) % mo,1);
                }
            }
            else{
                v = b[wz[i - 1]];
                if(v == u){
                    ud(g[w][1] - g[w][3] + mo,2);ud(s * g[w][3] % mo,3);
                }
                else{
                    ud(g[w][3] - g[w][4] + mo,2);ud((x * g[w][2] + s * g[w][4] - x * g[w][4] % mo + mo) % mo,3);xg(v,(x * g[w][0] + (s - x + mo) * g[w][2]) % mo,1);
                }
            }
            xg(u,0,1);
        }
        else{
            u = b[wz[i]];x = cx(u);
            if(a[wz[i - 1]]){
                v = a[wz[i - 1]];
                if(v == u){
                    ud(g[w][1] - g[w][3] + mo,2);ud(s * g[w][3] % mo,3);
                }
                else{
                    ud(g[w][3] - g[w][4] + mo,2);ud((x * g[w][2] + s * g[w][4] - x * g[w][4] % mo + mo) % mo,3);xg(v,(x * g[w][0] + (s - x + mo) * g[w][2]) % mo,1);
                }
            }
            else{
                v = b[wz[i - 1]];
                if(v == u){
                    ud(g[w][0] - g[w][2] + mo,2);ud(s * g[w][2] % mo,3);
                }
                else{
                    ud(g[w][2] - g[w][4] + mo,2);ud((x * g[w][3] + s * g[w][4] - x * g[w][4] % mo + mo) % mo,3);xg(v,(x * g[w][1] + (s - x + mo) * g[w][3]) % mo,1);
                }
            }
            xg(u,0,1);
        }
    }
    
    for(i = 1;i <= c;++i) f[i] = cx(i);
    li as = 0;
    if(wz[ft] == n) for(i = 1;i <= c;++i) (as += f[i]) %= mo;
    else{
        u = n - wz[ft];
        for(i = 1;i <= c;++i) (as += (g[u][0] + g[u][1] + g[u][2] * (c - 2) * 2 + g[u][3] * (c - 2) * 2 + g[u][4] * (c - 2) % mo * (c - 3)) % mo * f[i]) %= mo;
    }
    print((as % mo + mo) % mo);pc('\n');
    return 0;
}

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public int[] matrix = null;
    public int color = 0;
    public int n = 0;
    
    public int total = 0;
    public List<List<Integer>> list = new ArrayList<List<Integer>>();
    
    /**
     * 分出隔离的区域
     */
    public void split() {
        int a = 0;
        while (a < matrix.length) {
            if (matrix[a] == 0) {
                List<Integer> set = new ArrayList<>();
                list.add(set);
                matrix[a] = -1;
                set.add(a);
                search(a, set);
            }
            a++;
        }
    }
    
    private void search(int a, List<Integer> set) {
        if (a >= n) {
            if (matrix[a-n] == 0) {
                matrix[a-n] = -1;
                set.add(a-n);
                search(a-n, set);
            }
            if (a+1<2*n && matrix[a+1] == 0) {
                matrix[a+1] = -1;
                set.add(a+1);
                search(a+1, set);
            }
            if (a-1>n-1 && matrix[a-1] == 0) {
                matrix[a-1] = -1;
                set.add(a-1);
                search(a-1, set);
            }
        } else {
            if (matrix[a+n] == 0) {
                matrix[a+n] = -1;
                set.add(a+n);
                search(a+n, set);
            }
            if (a+1<n && matrix[a+1] == 0) {
                matrix[a+1] = -1;
                set.add(a+1);
                search(a+1, set);
            }
            if (a-1>-1 && matrix[a-1] == 0) {
                matrix[a-1] = -1;
                set.add(a-1);
                search(a-1, set);
            }
        }
    }
    
    /**
     * 搜索
     */
    public BigInteger print(List<Integer> set, BigInteger count) {
        BigInteger total = BigInteger.ZERO;
        List<Integer> recycle = new ArrayList<Integer>();
        recycle.addAll(set);
        int o = set.remove(0);
        for (int c=1;c<=color;c++) {
            if (o < n) {
                if ((o+1<n && c == matrix[o+1])
                        || (o > 0 && c == matrix[o-1])
                        || (c == matrix[o+n])) {
                    continue;
                } else {
                    matrix[o] = c;
                }
            } else {
                if ((o+1<2*n && c == matrix[o+1])
                        || (o > n && c == matrix[o-1])
                        || c == matrix[o-n]) {
                    continue;
                } else {
                    matrix[o] = c;
                }
            }
            if (set.size() == 0) {
                total = total.add(BigInteger.ONE);
            } else {
                total = print(set, total);
            }
            // 还原
            matrix[o] = -1;
        }
        // 还原
        set.add(0, o);
        return count.add(total);
    }
    
    public static void main(String[] args) {
        Main print = new Main();
        Scanner scanner = new Scanner(System.in);
        print.n = scanner.nextInt();
        print.color = scanner.nextInt();
        print.matrix = new int[2*print.n];
        for (int i=0;i<2*print.n;i++) {
            print.matrix[i] = scanner.nextInt();
        }
        scanner.close();
        
        print.split();
        BigInteger b = BigInteger.ONE;
        // 总方案数=各子区域方案数的积（高精度乘）
        for (int i=0;i<print.list.size();i++) {
            BigInteger count = print.print(print.list.get(i), BigInteger.ZERO);
            b = b.multiply(new BigInteger(String.valueOf(count)));
            b = b.mod(new BigInteger("1000000009"));
        }
        System.out.println(b.intValue());
    }
}