[SDOI2019] 染色

admin LV 10 SU @ 2026-5-10 23:59:39

题目大意：2×n的格子，用c种颜色进行染色，要求相邻的格子不能用相同的颜色，一些格子已经事先涂好了颜色，求方案数。

先%一下现场切掉这题的rqy。

我这里的做法与rqy的不同，我没看过官方题解不过我猜这个做法应该类似于官方题解的思路。

先考虑一个最朴素的dp。设f(i,j,k)为前i列，最后一列上面填j下面填k的方案数，转移直接枚举下一列填什么。

这样做显然复杂度非常高，光状态数就达到了nc^2。

我们该怎么优化这个算法呢？

首先当然是要把状态数减下来。我们把视线放在这个c^2上，能否在这里做些手脚呢？

注意到当这一列已经有事先填过的格子时，我们显然只需要c的状态就可以了。

假设当前列的上面已经填了颜色x，我们就直接记f(y)表示下面格子填y的方案数，其中f(x)=0。下面填了颜色类似。为方便起见，我们可以将上下都填颜色当成上面填颜色处理。

那我们处理到了没填过的列该怎么办呢？注意到所有没填过的列都长成一个样子，我们就自然而然地想到了：或许可以预处理转移！

我们直接将所有连续的空列看成一大段来一起转移，只在所有非空列更新dp值。

预处理一个数组g(i,s)，表示相邻两个非空列中间隔着i个空列，这两个非空列的状态为s时的转移系数。

其中这个“状态”指的是对应元素的相等关系。一共有如下7种状态：

a ... a
b ... b
*******
a ... b
b ... a
*******
a ... a
b ... c
*******
a ... b
b ... c
*******
a ... c
b ... a
*******
a ... c
b ... b
*******
a ... c
b ... d

其中状态3和6，状态4和5是对称的，因此我们记5种状态即可。

g数组的预处理就是大分类讨论，细节详见代码。这一步是O(n)的。

这样我们只需要枚举所有非空列，也可以通过讨论一些列的相等关系实现转移。

注意特判一些特殊情况，比如数据本来就无解、没有非空列、开头和结尾有一堆空列等。

这样我们就获得了一个O(nc)的做法，可以获得96分的好成绩。

更进一步：仔细观察dp的转移，发现我们无非干了这么几件事：

单点修改；全局加；全局乘；全局赋值；单点查询；全局查询。

嗯？好像有点熟悉？

没错你只需要把t1的代码粘过来就能获得100分的好成绩了。

当然你也可以直接上线段树，反正照样跑得飞快。

96分代码：

#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;
inline li ksm(li q,li w){
	li as = 1;
	while(w){
		if(w & 1) as = as * q % mo;
		q = q * q % mo;
		w >>= 1;
	}
	return as;
}
int a[100010],b[100010];
int wz[100010],ft;
li f[100010],g[100010][5],tp[100010];
int main(){
	int i,j,k,l,u,v,w;
	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;
		} 
	}
	for(i = 2;i <= ft;++i){
		li s = 0;w = wz[i] - wz[i - 1];
		for(j = 1;j <= c;++j) s += f[j];s %= mo;
		if(a[wz[i]]){
			u = a[wz[i]];
			if(a[wz[i - 1]]){
				v = a[wz[i - 1]];
				for(j = 1;j <= c;++j) if(j != u && (!b[wz[i]] || j == b[wz[i]])){
					if(v == u) tp[j] = (f[j] * g[w][0] + (s - f[j] + mo) * g[w][2]) % mo;
					else if(v == j) tp[j] = (f[u] * g[w][1] + (s - f[u] + mo) * g[w][3]) % mo;
					else tp[j] = (f[u] * g[w][3] + f[j] * g[w][2] + (s - f[u] - f[j] + mo + mo) * g[w][4]) % mo;
				}
			}
			else{
				v = b[wz[i - 1]];
				for(j = 1;j <= c;++j) if(j != u && (!b[wz[i]] || j == b[wz[i]])){
					if(v == u) tp[j] = (f[j] * g[w][1] + (s - f[j] + mo) * g[w][3]) % mo;
					else if(v == j) tp[j] = (f[u] * g[w][0] + (s - f[u] + mo) * g[w][2]) % mo;
					else tp[j] = (f[u] * g[w][2] + f[j] * g[w][3] + (s - f[u] - f[j] + mo + mo) * g[w][4]) % mo;
				}
			}
		}
		else{
			u = b[wz[i]];
			if(a[wz[i - 1]]){
				v = a[wz[i - 1]];
				for(j = 1;j <= c;++j) if(j != u){
					if(v == u) tp[j] = (f[j] * g[w][1] + (s - f[j] + mo) * g[w][3]) % mo;
					else if(v == j) tp[j] = (f[u] * g[w][0] + (s - f[u] + mo) * g[w][2]) % mo;
					else tp[j] = (f[u] * g[w][2] + f[j] * g[w][3] + (s - f[u] - f[j] + mo + mo) * g[w][4]) % mo;
				}
			}
			else{
				v = b[wz[i - 1]];
				for(j = 1;j <= c;++j) if(j != u){
					if(v == u) tp[j] = (f[j] * g[w][0] + (s - f[j] + mo) * g[w][2]) % mo;
					else if(v == j) tp[j] = (f[u] * g[w][1] + (s - f[u] + mo) * g[w][3]) % mo;
					else tp[j] = (f[u] * g[w][3] + f[j] * g[w][2] + (s - f[u] - f[j] + mo + mo) * g[w][4]) % mo;
				}
			}
		}
		for(j = 1;j <= c;++j) f[j] = tp[j],tp[j] = 0;
	}
	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;
}
/*
0:
aa
bb

1:
ab
ba

2:
aa or ac
bc    bb

3:
ab or ac
bc    ba

4:
ac
bd
*/

100分代码（线段树）：

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

huangzheng LV 6 SU @ 2025-10-8 17:14:39

#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cctype>
#include <vector>
#include <queue>
#define fail(x) x?(puts("0"), exit(0)):void()
using namespace std;
typedef long long i64;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while (!isdigit(ch = getchar()))
        if (ch == '-')
            f = -1;

    while (isdigit(ch))
        x = x * 10 + ch - '0', ch = getchar();

    return f * x;
}
const int P = 1e9 + 9, N = 1e5 + 5;
i64 qpow(i64 a, int b)
{
    i64 c = 1;

    for (; b; b >>= 1, a = a * a % P)
        if (b & 1)
            c = c * a % P;

    return c;
}
int n, c, m, p[N], a[N], b[N];
i64 g[5][N], ans;
struct T
{
    int old, now, t[N];
    i64 f[N], S, K, B;
    i64 G(i64 x) {
        return (K * x + B) % P;
    }
    void add(i64 v) {
        ++now, (S += v * c) %= P, (B += v) %= P;
    }
    void set(i64 v) {
        ++now, S = v * c % P, K = 1, B = 0, f[0] = v, old = now;
    }
    void mul(i64 v) {
        if (v)
            ++now, S = S * v % P, K = K * v % P, B = B * v % P;
        else
            set(0);
    }
    void set(int p, i64 v) {
        ++now, (S += P - G(t[p] > old ? f[p] : f[0])) %= P, t[p] = now, (S += v) %= P, f[p] = (v + P - B) * qpow(K,
                P - 2) % P;
    }
    i64 ask(int p) {
        return G(t[p] > old ? f[p] : f[0]);
    }
    i64 ask() {
        return S;
    }
} t;
int main()
{
    n = read(), c = read(), t.set(0);

    for (int i = 1; i <= n; ++i)
        a[i] = read();

    for (int i = 1; i <= n; ++i)
        b[i] = read();

    for (int i = 1; i <= n; ++i)
        if (a[i] || b[i])
            p[++m] = i, fail(a[i] && a[i] == b[i]), fail(a[i] && a[i] == a[i + 1]), fail(b[i] && b[i] == b[i + 1]);

    if (!m)
        return printf("%lld\n", c * (c - 1ll) % P * qpow(((c - 1ll) * (c - 2) + 1) % P, n - 1) % P), 0;

    g[1][1] = g[3][1] = g[4][1] = 1;

    for (int i = 1; i < n; ++i)
        g[0][i + 1] = (g[1][i] + 2ll * (c - 2) * g[3][i] + (c - 2ll) * (c - 3) % P * g[4][i]) % P,
                      g[1][i + 1] = (g[0][i] + 2ll * (c - 2) * g[2][i] + (c - 2ll) * (c - 3) % P * g[4][i]) % P,
                                    g[2][i + 1] = (g[1][i] + (c - 2ll) * g[2][i] + (2 * c - 5ll) * g[3][i] % P + (c - 3ll) *
                                            (c - 3) % P * g[4][i]) % P,
                                            g[3][i + 1] = (g[0][i] + (2 * c - 5ll) * g[2][i] + (c - 2ll) * g[3][i] % P + (c - 3ll) *
                                                    (c - 3) % P * g[4][i]) % P,
                                                    g[4][i + 1] = (g[0][i] + g[1][i] + 2 * (c - 3ll) * g[2][i] + 2 * (c - 3ll) * g[3][i] + ((c - 3ll) *
                                                            (c - 4) + 1) % P * g[4][i]) % P;

    if (p[1] == 1)
        if (a[1] && b[1])
            t.set(b[1], 1);
        else if (a[1])
            t.set(1), t.set(a[1], 0);
        else
            t.set(1), t.set(b[1], 0);
    else
    {
        int u = p[1], w = (g[0][u - 1] + g[1][u - 1] + 2ll * (c - 2) * (g[2][u - 1] + g[3][u - 1]) + (c - 2ll) *
                           (c - 3) % P * g[4][u - 1]) % P;

        if (a[u] && b[u])
            t.set(b[u], w);
        else if (a[u])
            t.set(w), t.set(a[u], 0);
        else
            t.set(w), t.set(b[u], 0);
    }

    for (int i = 2; i <= m; ++i)
    {
        i64 s = t.ask(), fu;
        int w = p[i] - p[i - 1], u, v;

        if (a[p[i]])
        {
            u = a[p[i]], fu = t.ask(u);

            if (a[p[i - 1]])
            {
                v = a[p[i - 1]];

                if (!b[p[i]])
                {
                    if (u == v)
                        t.mul((g[0][w] - g[2][w] + P) % P), t.add(s * g[2][w] % P);
                    else
                        t.mul((g[2][w] - g[4][w] + P) % P), t.add((fu * g[3][w] + (s - fu + P)*g[4][w]) % P), t.set(v,
                                (fu * g[1][w] + (s - fu + P)*g[3][w]) % P);
                }
                else
                {
                    int j = b[p[i]];
                    i64 fj = t.ask(j);
                    t.set(0);

                    if (u == v)
                        t.set(j, (fj * g[0][w] + (s - fj + P)*g[2][w]) % P);
                    else if (j == v)
                        t.set(j, (fu * g[1][w] + (s - fu + P)*g[3][w]) % P);
                    else
                        t.set(j, (fj * g[2][w] + fu * g[3][w] + (s - fj - fu + 2 * P)*g[4][w] % P) % P);
                }
            }
            else
            {
                v = b[p[i - 1]];

                if (!b[p[i]])
                {
                    if (u == v)
                        t.mul((g[1][w] - g[3][w] + P) % P), t.add(s * g[3][w] % P);
                    else
                        t.mul((g[3][w] - g[4][w] + P) % P), t.add((fu * g[2][w] + (s - fu + P)*g[4][w]) % P), t.set(v,
                                (fu * g[0][w] + (s - fu + P)*g[2][w]) % P);
                }
                else
                {
                    int j = b[p[i]];
                    i64 fj = t.ask(j);
                    t.set(0);

                    if (u == v)
                        t.set(j, (fj * g[1][w] + (s - fj + P)*g[3][w]) % P);
                    else if (j == v)
                        t.set(j, (fu * g[0][w] + (s - fu + P)*g[2][w]) % P);
                    else
                        t.set(j, (fu * g[2][w] + fj * g[3][w] + (s - fj - fu + 2 * P)*g[4][w] % P) % P);
                }
            }
        }
        else
        {
            u = b[p[i]], fu = t.ask(u);

            if (a[p[i - 1]])
            {
                v = a[p[i - 1]];

                if (u == v)
                    t.mul((g[1][w] - g[3][w] + P) % P), t.add(s * g[3][w] % P);
                else
                    t.mul((g[3][w] - g[4][w] + P) % P), t.add((fu * g[2][w] + (s - fu + P)*g[4][w]) % P), t.set(v,
                            (fu * g[0][w] + (s - fu + P)*g[2][w]) % P);
            }
            else
            {
                v = b[p[i - 1]];

                if (u == v)
                    t.mul((g[0][w] - g[2][w] + P) % P), t.add(s * g[2][w] % P);
                else
                    t.mul((g[2][w] - g[4][w] + P) % P), t.add((fu * g[3][w] + (s - fu + P)*g[4][w]) % P), t.set(v,
                            (fu * g[1][w] + (s - fu + P)*g[3][w]) % P);
            }
        }

        t.set(u, 0);
    }

    if (p[m] == n)
        ans = t.ask();
    else
    {
        int u = n - p[m], w = (g[0][u] + g[1][u] + 2ll * (c - 2) * (g[2][u] + g[3][u]) + (c - 2ll) *
                               (c - 3) % P * g[4][u]) % P;
        ans = t.ask() * w % P;
    }

    printf("%lld\n", ans);
    return 0;
}

ID

2380

时间

3000ms

内存

256MiB

难度

标签

递交数

已通过

上传者

admin

2 条题解

信息

状态

开发

支持

关于

2 条题解

[SDOI2019] 染色

信息

状态

开发

支持

关于

还没有账户？

登录