SCOI2016 乱做

看了第一题之后感觉上去没那么毒瘤,于是决定开坑。。

也没咕多久吧。。

背单词

原题链接:loj-2012

一个串肯定得在它的后缀都被填入后再填入,我们建出这些串的反串的 Trie,现在得到一棵树形结构,其上有若干个关键点,要求给这些关键点赋权($[n]$ 的全排列),满足对于任意关键点的权小于其子树内的关键点的权,然后最小化题目里求的那个东西。

由于我们仅需考察关键点,我们直接建一棵新树,新树的节点都是原来的 Trie 上的关键点以及 Trie 的根,每个节点的父亲是它在 Trie 上离他最近的一个祖先关键点。

理性分析一下,我们发现我们一定是按某个 dfs 序给这些点定权,换句话说就是一个子树内的权一定是一段连续的取值。

设 $u$ 子树大小为 $s(u)$,$f(u)$ 表示仅考虑 $u$ 的子树时,用 $[s(u)]$ 的全排列给 $u$ 的子树内的点赋权得到的最小答案。将权的值域从 $[1,s(u)]$ 转到到 $[1+\Delta,s(u)+\Delta]$ 的过程实际上就是给 $f(u)$ 加上 $\Delta$,因为子树内的点除了 $u$ 都是 $?-?$ 的形式,两边同加 $\Delta$ 后值不变。

现在来考虑转移,除去点 $u$ 的贡献以及让儿子的赋权偏移和将 $v$ 接在 $u$ 后减去 $u$ 的权 $1$,接下来实际上是考虑如何排列 $u$ 的儿子,当我们将某个儿子 $v$ 填在第 $k$ 位时,它会让后面的儿子的赋权偏移 $s(v)$,也就是产生额外的贡献 $s(v)\bigg{(}|son(u)|-k\bigg{)}$。由于无论如何排列,$f(v)$ 总是不变的,我们只需最小化额外的贡献,这是一个经典的贪心问题,我们让 $s(v)$ 小的尽量靠前即可。

正常计算后,取根的 $f$ 减 $1$ 即可。

时间复杂度 $O(n\log n)$。

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
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
inline void read(int& x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
inline void read(ll& x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}

const int N=6e5+10,M=1e5+10;

int n;
char str[N];
namespace Trie{
int tot;
struct Tree{int ed,ch[26];}t[N];
inline void Init(){tot=1;}
inline void Insert(char *str){
int now=1,len=strlen(str);
for(int i=len-1;~i;--i){
if(!t[now].ch[str[i]-'a']) t[now].ch[str[i]-'a']=++tot;
now=t[now].ch[str[i]-'a'];
}
t[now].ed=1;
}
}

using namespace Trie;

int cnt=1;
vector<int> Edge[M];

void dfs(int now,int top){
if(t[now].ed) Edge[top].pb(++cnt),top=cnt;
for(int c=0;c<26;++c)
if(t[now].ch[c]) dfs(t[now].ch[c],top);
}

int siz[M];
ll F[M];
void PreCalc(int now){
siz[now]=1;
for(int v:Edge[now]) PreCalc(v),siz[now]+=siz[v];
sort(Edge[now].begin(),Edge[now].end(),[](const int &lhs,const int &rhs)->bool{return siz[lhs]<siz[rhs];});
}
void Calc(int now){
int deg=Edge[now].size();
F[now]=1;
for(int i=0;i<deg;++i) Calc(Edge[now][i]),F[now]+=F[Edge[now][i]]+1ll*siz[Edge[now][i]]*(deg-i-1);
}

void Work(){
read(n),Init();
for(int i=1;i<=n;++i) scanf("%s",str),Insert(str);
dfs(1,1),PreCalc(1),Calc(1);
printf("%lld\n",F[1]-1);
}

int main(){Work();}

幸运数字

原题链接:loj-2013

倍增维护某个点到其 $2^k$ 级祖先(我的实现是到 $2^k-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
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
inline void read(int& x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
inline void read(ll& x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}

const int N=2e4+10,U=60,logN=16;

struct LinBas{
ll A[U+5];
int cnt;
LinBas(){memset(A,0,sizeof A),cnt=0;}
void Insert(ll x){
if(cnt==U) return;
for(int i=U;~i;--i){
if(!x) return;
if(!(x&(1ll<<i))) continue;
if(A[i]) x^=A[i];
else{
for(int j=0;j<i;++j) if(x&(1ll<<j)) x^=A[j];
for(int j=i+1;j<=U;++j) if(A[j]&(1ll<<i)) A[j]^=x;
A[i]=x,++cnt;
return;
}
}
}
};

LinBas Merge(LinBas lhs,LinBas rhs){
LinBas res;
if(lhs.cnt<rhs.cnt) swap(lhs,rhs);
res=lhs;
if(res.cnt==U) return res;
for(int i=U;~i;--i)
if(rhs.A[i]) res.Insert(rhs.A[i]);
return res;
}

ll QueryMax(LinBas lhs){
ll res=0;
for(int i=0;i<=U;++i) res^=lhs.A[i];
return res;
}

int n,q;
ll val[N];
vector<int> Edge[N];
int fat[N][logN+5];
LinBas _fa[N][logN+5];
int _log2[N],dep[N];

void dfs(int now,int fa){
dep[now]=dep[fa]+1;
_fa[now][0].Insert(val[now]),fat[now][0]=fa;
for(int i=1;i<logN;++i) fat[now][i]=fat[fat[now][i-1]][i-1],_fa[now][i]=Merge(_fa[now][i-1],_fa[fat[now][i-1]][i-1]);
for(int v:Edge[now])
if(v^fa) dfs(v,now);
}

void Work(){
read(n),read(q);
for(int i=2;i<=n;++i) _log2[i]=_log2[i>>1]+1;
for(int i=1;i<=n;++i) read(val[i]);
for(int i=1;i<n;++i){
int u,v;read(u),read(v);
Edge[u].pb(v),Edge[v].pb(u);
}
dfs(1,1);
while(q--){
int x,y;read(x),read(y);
LinBas res;
if(dep[x]<dep[y]) swap(x,y);
while(dep[x]>dep[y]) res=Merge(res,_fa[x][_log2[dep[x]-dep[y]]]),x=fat[x][_log2[dep[x]-dep[y]]];
for(int i=logN-1;~i;--i)
if(fat[x][i]!=fat[y][i]) res=Merge(res,Merge(_fa[x][i],_fa[y][i])),x=fat[x][i],y=fat[y][i];
if(x==y) res.Insert(val[x]),printf("%lld\n",QueryMax(res));
else res.Insert(val[x]),res.Insert(val[y]),res.Insert(val[fat[x][0]]),printf("%lld\n",QueryMax(res));
}
}

int main(){Work();}

萌萌哒

原题链接:loj-2014

一个简单的想法是用并查集维护颜色必须相等的集合,这样答案就很好算,但是直接连边是 $O(n^2)$ 的。

考虑对于将每个点拆成 $\log$ 个点,每个点表示从该位置开始,长度为 $2^k$ 的区间,这样我们可以将一个区间拆成 $\log$ 个区间,然后对于两个区间将它们拆成的 $\log$ 个区间对应地连在一起,这样连边的复杂度就正确了。

至于计算答案,类似于标记下传,假如 $[l,l+2^k-1]$ 的父亲是 $[l’,l’+2^k-1]$,那么连 $[l,l+2^{k-1}-1]\rightarrow [l’,l’+2^{k-1}-1]$,$[l+2^{k-1},l+2^k-1]\rightarrow[l’+2^{k-1},l’+2^k-1]$ 即可。

时间复杂度 $O(n\log^2 n)$,有一个 $\log$ 是并查集的。

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
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
inline void read(int& x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
inline void read(ll& x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}

const int N=2e4+10,U=60,logN=16;

struct LinBas{
ll A[U+5];
int cnt;
LinBas(){memset(A,0,sizeof A),cnt=0;}
void Insert(ll x){
if(cnt==U+1) return;
for(int i=U;~i;--i){
if(!x) return;
if(!(x&(1ll<<i))) continue;
if(A[i]) x^=A[i];
else{
for(int j=0;j<i;++j) if(x&(1ll<<j)) x^=A[j];
for(int j=i+1;j<=U;++j) if(A[j]&(1ll<<i)) A[j]^=x;
A[i]=x,++cnt;
return;
}
}
}
};

LinBas Merge(LinBas lhs,LinBas rhs){
LinBas res;
if(lhs.cnt<rhs.cnt) swap(lhs,rhs);
res=lhs;
if(res.cnt==U+1) return res;
for(int i=U;~i;--i)
if(rhs.A[i]) res.Insert(rhs.A[i]);
return res;
}

ll QueryMax(LinBas lhs){
ll res=0;
for(int i=0;i<=U;++i) res^=lhs.A[i];
return res;
}

int n,q;
ll val[N];
vector<int> Edge[N];
int fat[N][logN+5];
LinBas _fa[N][logN+5];
int _log2[N],dep[N];

void dfs(int now,int fa){
dep[now]=dep[fa]+1;
_fa[now][0].Insert(val[now]),fat[now][0]=fa;
for(int i=1;i<logN;++i) fat[now][i]=fat[fat[now][i-1]][i-1],_fa[now][i]=Merge(_fa[now][i-1],_fa[fat[now][i-1]][i-1]);
for(int v:Edge[now])
if(v^fa) dfs(v,now);
}

void Work(){
read(n),read(q);
for(int i=2;i<=n;++i) _log2[i]=_log2[i>>1]+1;
for(int i=1;i<=n;++i) read(val[i]);
for(int i=1;i<n;++i){
int u,v;read(u),read(v);
Edge[u].pb(v),Edge[v].pb(u);
}
dfs(1,1);
while(q--){
int x,y;read(x),read(y);
LinBas res;
if(dep[x]<dep[y]) swap(x,y);
while(dep[x]>dep[y]) res=Merge(res,_fa[x][_log2[dep[x]-dep[y]]]),x=fat[x][_log2[dep[x]-dep[y]]];
for(int i=logN-1;~i;--i)
if(fat[x][i]!=fat[y][i]) res=Merge(res,Merge(_fa[x][i],_fa[y][i])),x=fat[x][i],y=fat[y][i];
if(x==y) res.Insert(val[x]),printf("%lld\n",QueryMax(res));
else res.Insert(val[x]),res.Insert(val[y]),res.Insert(val[fat[x][0]]),printf("%lld\n",QueryMax(res));
}
}

int main(){Work();}

妖怪

原题链接:loj-2015

容易发现最大化攻击和防御是两个独立的过程。

假设某个环境 $(a,b)$,某个怪物 $(c,d)$,那么它的战斗力应该是 $c+\frac{ad}{b}+d+\frac{bc}{a}$,化简一下,它就是:$c+d+\frac{a^2d+b^2c}{ab}$。

考虑二分 $mid$,判定是否对于任意 $(a,b)$,总存在一个 $(c,d)$ 的战斗力大于 $mid$。

在这个过程中,我们仅关注 $a,b$ 的比值,那么转而考虑是否任意正实数 $k$,总存在一个 $(c,d)$ 使得 $(1+\frac{1}{k})c+(1+k)d>mid$。

把上式化开,即 $\frac{c}{k}+dk> mid-c-d$。

由于 $c,d,k$ 都是正数,故 $\frac{c}{k}+dk\ge 2\sqrt{cd}$,这要求对于 $(c,d)$,应满足 $mid\ge c+d+2\sqrt{cd}$。

但是不能直接取最大值,因为有可能出现对于每个 $(c,d)$ 它们解集的交集为空的情况。对于某个 $(c,d)$,可行的 $k$ 应是一个区间,判它们有没有交集就好了。

时间复杂度 $O(n\log U)$,看起来有更高明的 $O(n\log n)$ 的计算几何做法,但是我又菜又懒,还是不想了。

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
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
inline void read(int& x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
inline void read(ll& x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
inline void chkmax(double &x,double y){if(y>x)x=y;}
inline void chkmin(double &x,double y){if(y<x)x=y;}

const int N=1e6+10;
const double eps=1e-6;
int n;
int C[N],D[N];

inline bool chk(double mid){
double L=0,R=1e14;
for(int i=1;i<=n;++i){
double l=mid-C[i]-D[i];
if(l*l<4.0*C[i]*D[i]) continue;
double Left=l/D[i],Right=sqrt(Left*Left-4.0*C[i]/D[i]);
double nowL=(Left-Right);
double nowR=(Left+Right);
if(nowL>R) return true;
if(L>nowR) return true;
chkmax(L,nowL),chkmin(R,nowR);
}
return false;
}

void Work(){
read(n);
double l=0,r=1e10,mid;
for(int i=1;i<=n;++i) read(C[i]),read(D[i]),chkmax(l,1.0*C[i]+1.0*D[i]+2.0*sqrt(1.0*C[i]*D[i]));
while(r-l>eps){
mid=(l+r)/2;
if(chk(mid)) l=mid;
else r=mid;
}
printf("%.4lf\n",l);
}

int main(){Work();}

美味

原题链接:loj-2016

从高到低依次考虑每一位。

因为有了加法,01Trie 就很难处理,我们回顾没有加法的时候是怎么应用 01Trie 的:每次走到一个节点,表示它确定了这个数的前几位,后几位还不确定,这其实就是值域上的一个区间。

那么如果有加法之后我们应该如何处理?我们发现直接将上面的那个区间平移就好了。

使用主席树维护这个走儿子的过程即可。

时间复杂度 $O(n\log n+q\log n\log a)$。

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
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
inline void read(int& x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
inline void read(ll& x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}

const int N=2e5+10,U=2e5;
int n,q;

#define ls(now) (t[now].lson)
#define rs(now) (t[now].rson)
int rt[N],_tot;
struct Tree{int lson,rson,val;}t[N*40];
void Build(int &now,int l,int r){
now=++_tot;
if(l==r) return;
const int mid=(l+r)>>1;
Build(ls(now),l,mid),Build(rs(now),mid+1,r);
}
void Insert(int pre,int &now,int l,int r,int _val){
t[now=++_tot]=t[pre],t[now].val++;
if(l==r) return;
const int mid=(l+r)>>1;
if(mid>=_val) Insert(ls(pre),ls(now),l,mid,_val);
else Insert(rs(pre),rs(now),mid+1,r,_val);
}
int Ask(int L,int R,int l,int r,int x,int y){
if(x>y||l>r) return 0;
if(l>=x&&r<=y) return t[R].val-t[L].val;
const int mid=(l+r)>>1;
int res=0;
if(mid>=x) res+=Ask(ls(L),ls(R),l,mid,x,y);
if(mid<y) res+=Ask(rs(L),rs(R),mid+1,r,x,y);
return res;
}

void Work(){
read(n),read(q);
int a,b,x,l,r;
Build(rt[0],0,U);
for(int i=1;i<=n;++i) read(a),Insert(rt[i-1],rt[i],0,U,a);
while(q--){
read(b),read(x),read(l),read(r),--l;
int res=0;
for(int B=18;~B;--B){
if(b&(1<<B)){
int L=max(res-x,0),R=res+(1<<B)-1-x;
if(!Ask(rt[l],rt[r],0,U,L,R)) res|=(1<<B);
}
else{
int L=max(res+(1<<B)-x,0),R=res+(1<<(B+1))-1-x;
if(Ask(rt[l],rt[r],0,U,L,R)) res|=(1<<B);
}
}
printf("%d\n",res^b);
}
}

int main(){Work();}

围棋

原题链接:loj-2017

首先肯定是容斥,考虑计算一个棋盘怎么也没法匹配模板的情况。

然后不会了,瞄了一眼题解,轮廓线 DP……然后又不会了……然后又会了……

首先模板只有两行,这是好的,于是状态只和当前行及上一行有关,考虑轮廓线。

再仔细观察,我们发现棋盘当前行怎么填只和上一行是否匹配有关。

对于轮廓线上的格子,我们并不在意它填的具体是什么,我们只需要知道它是否可以和模板匹配就行了,所以一个位置是 $1$ 当且仅当棋盘中以它为末尾的一个串可以和模板第一行匹配。注意这里即使是当前行的轮廓线,也是和模板第一行匹配。

设 $F_{i,j,S,a,b}$ 表示当前正在填第 $i$ 行第 $j$ 列,轮廓线状态为 $S$,当前行已经匹配到了模板第一行的第 $a$ 位,当前行已经匹配到了模板第二行的第 $b$ 位。

首先填初值 $F_{1,1,0,0,0}=1$。

接着考虑如何将 $F_{i,j,S,a,b}$ 转移至 $F_{i,j+1}$。

分析填上一个数会对 $S,a,b$ 产生什么影响,如果填对了数(特别地如果 $a$ 或 $b$ 等于 $c$ 了,那么它填什么数都是错的),那么它会加一,否则应该不停跳 border,直到下一位可以匹配填的下个数,这部分可以 KMP 求。至于 $S$,看看 $a$ 是否会变为 $c$ 就可以了。

当然如果 $S$ 中表示 $j$ 的那一位为 $1$,且 $b$ 将变成 $c$,那么这时是无法转移的。

最后要求的是 $\sum_SF_{n+1,1,S,0,0}$。

跳 border 的过程可以预处理出来。

具体实现中,由于前 $c-1$ 列肯定无法匹配,所以 $S$ 实际上是整体右移使得第 $0$ 位表示的是第 $c$ 列。

滚动数组优化一下空间就好了。

时间复杂度 $O(nm2^{m-c+1}c^2)$,空间复杂度 $O(2^{m-c+1}c^2)$。

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
99
100
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
inline void read(int &x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
inline void read(ll &x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}

const int Mod=1e9+7;
void Add(int &x,int y){(x+=y)>=Mod?x-=Mod:x;}
int Pow(int a,int b){
int res=1;
while(b){
if(b&1) res=1ll*res*a%Mod;
a=1ll*a*a%Mod,b>>=1;
}
return res;
}

int n,m,c,q,All;
char st[2][15];
int str[2][15],Bord[2][15],nxt[2][15][3];

void Init(){
for(int B:{0,1}) scanf("%s",st[B]+1);
#define TRANS(i,j) str[i][j]=(st[i][j]=='X'?2:(st[i][j]=='B'))
for(int i=1;i<=c;++i)
for(int B:{0,1}) TRANS(B,i);
#undef TRANS
for(int B:{0,1}){
str[B][0]=str[B][c+1]=-1;
for(int i=2;i<=c;++i){
int now=Bord[B][i-1];
while(now&&str[B][i]!=str[B][now+1]) now=Bord[B][now];
if(str[B][i]==str[B][now+1]) ++now;
Bord[B][i]=now;
}
for(int i=0;i<=c;++i)
for(int ch:{0,1,2}){
int now=i;
while(now&&str[B][now+1]!=ch) now=Bord[B][now];
if(str[B][now+1]==ch) ++now;
nxt[B][i][ch]=now;
}
}
}

int DP[2][1030][15][15];

void Solve(){
Init();
int _S=(1<<(m-c+1));
int now=0;
memset(DP,0,sizeof DP);
DP[0][0][0][0]=1;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
memset(DP[now^1],0,sizeof DP[now^1]);
#define FOR \
for(int S=0;S<_S;++S)\
for(int a=0;a<=c;++a)\
for(int b=0;b<=c;++b)\
for(int ch:{0,1,2})
FOR{
int _nxtS,_nxta=nxt[0][a][ch],_nxtb=nxt[1][b][ch];
if(j<c) _nxtS=S;
else{
_nxtS=S|(1<<(j-c));
if(_nxta^c) _nxtS^=1<<(j-c);
}
if(_nxtb==c&&(S&(1<<(j-c)))) continue;
if(j==m) Add(DP[now^1][_nxtS][0][0],DP[now][S][a][b]);
else Add(DP[now^1][_nxtS][_nxta][_nxtb],DP[now][S][a][b]);
}
now^=1;
#undef FOR
}
int Ans=0;
for(int S=0;S<_S;++S) Add(Ans,DP[now][S][0][0]);
Ans=(All-Ans+Mod)%Mod;
printf("%d\n",Ans);
}

void Work(){
read(n),read(m),read(c),read(q);
All=Pow(3,n*m);
while(q--) Solve();
}

int main(){Work();}
#
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×