P2435

发表于 分类于
染色

染色

特判一下第二个点，实际上就是根据奇偶和异或判断一下是否符合输出 0/1 即可。。时间复杂度 $O(m)$。

然后就是这个轮廓线 DP。。。

依旧定义 $f(i,j,k)$ 表示到第 $i$ 行第 $j$ 列，轮廓线状态为 $k$ 的这个方案数。

然后一般 DP 就完了。。。

最后输出指定最后一行状态的 $f(n,m,s_2)$ 就可以了。

然后我被卡魔怔了。。。

尝试取模变减法，减少数组跳跃读取等方法均不能减少这个常数，不知道是为什么。。。

最后 Jwz 让我开 int，于是就过了。。。

Jwz_Txd1

我是什么废物/ll。。。

时间复杂度 $O(nmk^{m+1})$。。。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<iostream>
#include<cstdio>
#define ll int
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;

const ll L=1e5,N=8,M=1e6,mo=376544743;

ll n,m,k,s1,s2;
ll a[L+5],b[L+5],f[2][N+5][M+5];

inline ll Pow(ll b,ll p) {
  ll res=1;while(p) {if(p&1) res=res*b;b=b*b;p>>=1;}return res;
}

inline ll Kch_i(ll s,ll x) {for(ll i=1;i<x;i++) {s/=k;}return s%k;}

inline ll Kass_i(ll s,ll pos,ll x) {
  ll tmppp=Pow(k,pos-1);ll tmpppp=tmppp*k;
  ll tmp1=s%tmppp,tmp2=s/tmpppp*tmpppp;
  return tmp1+tmp2+x*tmppp;
}

int main() {

  n=read();m=read();k=read();
  
  if(n>100) {
    for(ll i=1;i<=m;i++) {a[i]=read();}
    for(ll i=1;i<=m;i++) {b[i]=read();}
    if(n%2==0) {
      ll flg=0;
      for(ll i=1;i<=m;i++) {
        if((a[i]^1)!=b[i]) {flg=1;break;}
      }
      if(flg) write(0);
      else write(1);
    }
    else {
      ll flg=0;
      for(ll i=1;i<=m;i++) {
        if(a[i]!=b[i]) {flg=1;break;}
      }
      if(flg) write(0);
      else write(1);
    }
  }
  else {
    for(ll i=1;i<=m;i++) {a[i]=read();s1=Kass_i(s1,i,a[i]);}
    for(ll i=1;i<=m;i++) {b[i]=read();s2=Kass_i(s2,i,b[i]);}
    f[1][m][s1]=1;ll tmp=Pow(k,m);
    for(ll i=2;i<=n;i++) {
      for(ll p=0;p<tmp;p++) {
        if(f[(i-1)&1][m][p]==0) continue;
        for(ll q=0;q<k;q++) {
          if(q==Kch_i(p,1)) continue;
          ll tmpp=Kass_i(p,1,q);
          f[i&1][1][tmpp]+=f[(i-1)&1][m][p];
          if(f[i&1][1][tmpp]>=mo) f[i&1][1][tmpp]-=mo;
        }
      }
      for(ll j=2;j<=m;j++) {
        for(ll p=0;p<tmp;p++) {
          if(f[i&1][j-1][p]==0) continue;
          ll tmppp=f[i&1][j-1][p];
          for(ll q=0;q<k;q++) {
            if(q==Kch_i(p,j)||q==Kch_i(p,j-1)) continue;
            ll tmpp=Kass_i(p,j,q);
            f[i&1][j][tmpp]+=tmppp;
            if(f[i&1][j][tmpp]>=mo) f[i&1][j][tmpp]%=mo;
          }
        }
      }
      for(ll j=1;j<=m;j++) {
        for(ll p=0;p<tmp;p++) {
          f[(i-1)&1][j][p]=0;
        }
      }
    }
    ll ans=f[n&1][m][s2];
    write(ans);
  }

  return 0;
}