10.3

Codeforces Round #746 (Div. 2)

A

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
int a[10000];

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		ll n,h;
		scanf("%lld%lld",&n,&h);
		for(int i=1;i<=n;++i){
			scanf("%d",&a[i]);
		}
		sort(a+1,a+n+1,greater<int>());
		ll t=floor(1.0*h/(a[1]+a[2]));
		if(t*(a[1]+a[2])==h){
			printf("%lld\n",t<<1);
		}else if(t*(a[1]+a[2])+a[1]>=h){
			printf("%lld\n",(t<<1)+1);
		}else{
			printf("%lld\n",(t<<1)+2);
		}
	}
	return 0;
}

B

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int a[N],b[N];

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n,x;
		scanf("%d%d",&n,&x);
		for(int i=1;i<=n;++i){
			scanf("%d",&a[i]);
			b[i]=a[i];
		}
		sort(b+1,b+n+1);
		bool f=1;
		for(int i=1;i<=n;++i){
			if(i+x>n&&i-x<1){
				if(a[i]!=b[i]){
					f=0;
					break;
				}
			}
		}
		puts(f?"YES":"NO");
	}
	return 0;
}

C

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
vector<int> G[N];
int t[N],sm,a[N];

int dfs(int u,int fa){
	t[u]=a[u];
	for(int v:G[u]){
		if(v==fa) continue;
		t[u]^=dfs(v,u);
	}
	return t[u];
}
bool flag;
void find(int u,int fa){
	for(int v:G[u]){
		if(v==fa) continue;
		find(v,u);
		if(t[v]==sm&&!flag){
			flag=1;
			G[u].erase(find(G[u].begin(),G[u].end(),v));
			return;
		}
	}
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n,kk;
		scanf("%d%d",&n,&kk);
		sm=0;
		for(int i=1;i<=n;++i){
			scanf("%d",&a[i]);
			sm^=a[i];
		}
		for(int i=1;i<n;++i){
			int x,y;
			scanf("%d%d",&x,&y);
			G[x].push_back(y);
			G[y].push_back(x);
		}
		if(sm==0){
			puts("YES");
		}
		else if(kk==2){
			puts("NO");
		}
		else{
			dfs(1,0);
			find(1,0);
			if(flag){
				flag=0;
				dfs(1,0);
				find(1,0);
				if(flag){
					puts("YES");
				}else{
					puts("NO");
				}
			}else{
				puts("NO");
			}
			
		}
		for(int i=1;i<=n;++i){
			G[i].clear();
		}
	}
	return 0;
}

10.4

Lindström–Gessel–Viennot lemma，可以用来处理$ $上不相交路径计数等问题。

$\omega(P)$ 表示 $P$ 这条路径上所有边的边权之积。（路径计数时，可以将边权都设为 $1$）（事实上，边权可以为生成函数）

$e(u, v)$ 表示 $u$ 到 $v$ 的$ $ $P$ 的 $\omega(P)$ 之和，即 $e(u, v)=\sum\limits_{P:u\rightarrow v}\omega(P)$。

起点集合 $A$，是有向无环图点集的一个子集，大小为 $n$。

终点集合 $B$，也是有向无环图点集的一个子集，大小也为 $n$。

一组 $A\rightarrow B$ 的不相交路径 $S$：$S_i$ 是一条从 $A_i$ 到 $B_{\sigma(S)_i}$ 的路径（$\sigma(S)$ 是一个排列），对于任何 $i\ne j$，$S_i$ 和 $S_j$ 没有公共顶点。

$N(\sigma)$ 表示排列 $\sigma$ 的逆序对个数。

\[ M = \begin{bmatrix}e(A_1,B_1)&e(A_1,B_2)&\cdots&e(A_1,B_n)\\ e(A_2,B_1)&e(A_2,B_2)&\cdots&e(A_2,B_n)\\ \vdots&\vdots&\ddots&\vdots\\ e(A_n,B_1)&e(A_n,B_2)&\cdots&e(A_n,B_n)\end{bmatrix} \]

\[ \det(M)=\sum\limits_{S:A\rightarrow B}(-1)^{N(\sigma(S))}\prod\limits_{i=1}^n \omega(S_i) \]

其中 $\sum\limits_{S:A\rightarrow B}$ 表示满足上文要求的 $A\rightarrow B$ 的每一组不相交路径 $S$。

路径计数时，$\omega(S_i)=1$,故$\prod\limits_{i=1}^n \omega(S_i)=1$。

例题题意：有一个 $n\times n$ 的棋盘，棋子只能向下向右走，有 $m$ 个棋子，一开始第 $i$ 个棋子放在 $(1, a_i)$，最终要到 $(n, b_i)$，路径要两两不相交，求方案数。

观察到如果路径不相交就一定是 $a_i$ 到 $b_i$，因此 LGV 引理中一定有 $\sigma(S)_i=i$，不需要考虑符号问题。边权设为 $1$，直接套用引理即可。

从 $(1, a_i)$ 到 $(n, b_j)$ 的路径条数相当于从 $n-1+b_j-a_i$ 步中选 $n-1$ 步向下走，所以 $e(A_i, B_j)=\binom{n-1+b_j-a_i}{n-1}$。

const int M=105,N=2e6+6;
ll fact[N],mt[M][M],a[M],b[M];
const ll mod=998244353;
void exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1,y=0;return;
    }
    exgcd(b,a%b,x,y);
    ll t=x;x=y;y=t-a/b*y;
}
ll inv(ll a){
    ll x,y;
    exgcd(a,mod,x,y);
    return (x+mod)%mod;
}
ll C(ll n,ll m){
    return fact[n]*inv(fact[m])%mod*inv(fact[n-m])%mod;
}
int main(){
    int T;scanf("%d",&T);
    fact[0]=1;
    for(int i=1;i<N;++i){
        fact[i]=(fact[i-1]*i)%mod;
    }
    while(T--){
        ll n,m;
        scanf("%lld%lld",&n,&m);
        for(int i=1;i<=m;++i){
            scanf("%lld%lld",&a[i],&b[i]);//(ai,1)->(bi,n)
        }
        for(int i=1;i<=m;++i){
            for(int j=1;j<=m;++j){
                if(a[i]<=b[j]){
                    mt[i][j]=C(n-1+b[j]-a[i],n-1);
                }else{
                    mt[i][j]=0;
                }
            }
        }
        ll ans=1;
        for(int i=1;i<=m;++i){
            for(int j=i+1;j<=m;++j){
                while(mt[j][i]){
                    ll t=mt[i][i]/mt[j][i];
                    for(int k=i;k<=m;++k){
                        mt[i][k]=(mt[i][k]-t*mt[j][k]%mod+mod)%mod;
                        swap(mt[i][k],mt[j][k]);
                    }
                    ans=mod-ans;
                }
            }
            ans=ans*mt[i][i]%mod;
        }
        printf("%lld\n",(ans+mod)%mod);
    }
    return 0;
}

10.5

P5905【模板】Johnson 全源最短路

用于处理$ $的多源最短路问题。套用斐波那契堆优化的Dijkstra时间复杂度为$O(V^2logV+VE)$,套用二叉堆优化的Dijkstra时间复杂度$O(VElogE)$。

（稠密图$V^2\approx E$，使用Floyd算法即可，无负边权直接做$V$次Dijkstra。）

设虚拟结点，与其他点建边权为0的边，从虚拟结点跑spfa得$h_i$，重建图赋值$(u, v)$边权$w(u, v)$为$w(u, v)+h_u-h_v$，这保证了最短路径不变而且所有权重均非负，跑n次Dijkstra求最短路，算法求得距离为$dis(s, t)$，非不可达点的实际距离为$dis(s, t)-(h_s-h_t)$。

const int M=6e3+5,N=3e3+5,inf=1e9;
struct Edge{
    int t,n,v;
}e[M+N];
int hd[N];
int cnt,n,m;
inline void build(int f,int t,int v){
    e[++cnt]=(Edge){t,hd[f],v};
    hd[f]=cnt;
}
bool inq[N],vis[N];
int h[N],t[N];
bool spfa(){
    static queue<int> q;
    q.push(0);//虚拟结点定为0 
    h[0]=0;inq[0]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        inq[u]=0;
        for(int i=hd[u];i;i=e[i].n){
            int v=e[i].t;
            if(h[v]>h[u]+e[i].v){
                h[v]=h[u]+e[i].v;
                if(!inq[v]){
                    ++t[v];
                    if(t[v]==n+1) return 0;//入队n+1次，有负环 
                    q.push(v);
                    inq[v]=1;
                }
            }
        }
    }
    return 1;
}
int dis[N][N];
bool cho[N];
typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii> > q;
void dij(int S){
    for(int i=1;i<=n;++i){
        dis[S][i]=inf;
        cho[i]=0;
    }
    dis[S][S]=0;
    q.push(pii(0,S));
    while(!q.empty()){
        pii t=q.top();
        q.pop();
        int u=t.second;
        if(cho[u]) continue;
        cho[u]=1;
        for(int i=hd[u];i;i=e[i].n){
            int v=e[i].t;
            if(dis[S][v]>dis[S][u]+e[i].v){
                dis[S][v]=dis[S][u]+e[i].v;
                q.push(pii(dis[S][v],v));
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int a,b,v;
        scanf("%d%d%d",&a,&b,&v);
        build(a,b,v);
    }
    for(int i=1;i<=n;++i){
        h[i]=inf;
        build(0,i,0);//虚拟结点到其他点建边权为0的边 
    }
    if(!spfa()){
        puts("-1");
        return 0;
    }
    for(int u=1;u<=n;++u){
        for(int i=hd[u];i;i=e[i].n){
            e[i].v+=h[u]-h[e[i].t];
        }
    }
    for(int i=1;i<=n;++i){
        dij(i);
    }
    for(int i=1;i<=n;++i){
        long long ans=0;
        for(int j=1;j<=n;++j) ans+=(long long)j*(dis[i][j]-(dis[i][j]==inf?0:(h[i]-h[j])));
        printf("%lld\n",ans);
    }
    return 0;
}

10.7

$ $:给定域$F$，$F$上的向量空间$V$是一个集合，其上定义加法和数乘运算且这两个运算满足八个公理。

$ $:对于向量空间中$V$上$n$个元素的向量组$(_1, , _n)$,若存在不全为$0$的数$a_i \in F$满足 \[ a_{1}\mathbf{v}_{1}+a_{2}\mathbf {v}_{2}+\ldots +a_{n}\mathbf{v}_{n} = 0 \]

则称这$n$个向量线性相关（linearly dependent），否则称为线性无关（linearly independent）。

$ $:对于向量空间中 VV 上 nn 个元素的向量组$(_1, , _n)$，其线性组合（linear combination）是如下形式的向量

\[ a_{1}\mathbf{v}_{1} + a_{2}\mathbf {v} _{2}+\ldots +a_{n}\mathbf {v} _{n} \] 其中$a_1, \ldots, a_n \in F$

一组向量线性无关 $\Leftrightarrow$没有向量可用有限个其他向量的线性组合所表示

$ $:对于向量空间中 $V$ 上 $n$ 个元素的向量组 $(\mathbf{v}_1, \ldots, \mathbf{v}_n)$，其所有线性组合所构成的集合称为 $(\mathbf{v}_1, \ldots, \mathbf{v}_n)$的张成（span），记为 $\mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v}_n)$

$ $:若向量空间 $V$ 中向量组 $\mathfrak{B}$ 既是线性无关的又可以张成 $V$，则称其为$V$ 的基（basis）。

$\mathfrak{B}$中的元素称为基向量。如果基中元素个数有限，就称向量空间为有限维向量空间，将元素的个数称作向量空间的维数。

设 $\mathfrak {B}$ 是向量空间 $V$ 的基。则$\mathfrak {B}$具有以下性质：

1.$V$ 是 $\mathfrak {B}$的极小生成集，就是说只有$\mathfrak {B}$能张成$V$，而它的任何真子集都不张成全部的向量空间。

2.$\mathfrak {B}$ 是 $V$ 中线性无关向量的极大集合，就是说 $\mathfrak {B}$ 在$V$ 中是线性无关集合，而且$V$ 中没有其他线性无关集合包含它作为真子集。

3.$V$ 中所有的向量都可以按唯一的方式表达为$\mathfrak {B}$ 中向量的线性组合。

$ $

对于数 $a_0, a_1, \ldots, a_n$，将 $a_i$的二进制表示$ (b_{m}b_0)_2$ 看作一个向量。向量组 $\mathbf{a}_1, \ldots, \mathbf{a}_n$可以张成一个向量集合 $\mathrm{span}(\mathbf{a}_1, \ldots, \mathbf{a}_n)$，加上我们的异或运算和乘法运算（显然满足 8 条公理），即可形成一个向量空间 $V = (\{0, 1\}, \mathrm{span}(\mathbf{a}_1, \ldots, \mathbf{a}_n), \oplus, \cdot)$

设集合$S$中最大的数在二进制意义下有$L$位，我们使用一个 $[0\dots L]$的数组$a$来储存线性基。

这种线性基的构造方法保证了一个特殊性质，对于每一个$i$,$a_i$有以下两种可能：

（如果排成矩阵，形成一个下三角矩阵）

typedef long long ll;
const int MAXL=60;
ll a[MAXL+1];int lbsiz;
void insert(ll t){//高斯消元解出的对角矩阵的非零行构成的向量组 
    for(int j=MAXL;j>=0;--j){// 逆序枚举二进制位
        if(!((t>>j)&1)) continue;// 如果 t 的第 j 位为 0，则跳过
        if(a[j]) t^=a[j];
        else{// 找到可以插入 a[j] 的位置
            // 用 a[0...j - 1] 消去 t 的第 [0, j) 位上的 1
// 如果某一个a[k]=0也无须担心，因为这时候第k位不存在于线性基中，不需要保证t的第k位为 0	
            for(int k=0;k<j;++k) if((t>>k)&1) t^=a[k];
            // 用 t 消去 a[j + 1...L] 的第 j 位上的 1
            for(int k=j+1;k<=MAXL;++k) if((a[k]>>j)&1) a[k]^=t;
                // 插入到 a[j] 的位置上
            a[j]=t;++lbsiz;
            return;// 不要忘记，结束插入过程
        }
    }
}

最大异或和：将线性基中所有向量异或起来得到的向量所对应的数。

ll querymax(){
    ll res=0;
    for(int i=0;i<=MAXL;++i) res^=a[i];
    return res;
}

集合任选大于1个元素异或出的第k大数

vector<ll> v;
bool zero;int n;//zero: 是否能异或出0
void init(){
    lbsiz=0;
    v.clear();
    memset(a,0,sizeof a);
}
void prepare(){
    zero=(lbsiz!=n);
    for(int i=0;i<=MAXL;++i){
        if(a[i]) v.push_back(a[i]);
    }
}
ll query(ll k){
    if(zero) --k;
    if(k>=(1ll<<v.size())) return -1;
    ll res=0;
    for(int i=MAXL;i>=0;--i) if((k>>i)&1) res^=v[i];
    return res;
}
int main(){
    int T;
    scanf("%d",&T);
    for(int ttt=1;ttt<=T;++ttt){
        init();
        scanf("%d",&n);ll t;
        for(int i=1;i<=n;++i){
            scanf("%lld",&t);
            insert(t);
        }
        prepare();
        printf("Case #%d:\n",ttt);
        int q;scanf("%d",&q);
        while(q--){
            scanf("%lld",&t);
            printf("%lld\n",query(t));
        }
    }
    return 0;
}

10.8

P4151 [WC2011]最大XOR和路径

异或路径问题：转化成任意一条路径，和任意个圈的异或。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int M=200000+5,N=50000+5,MAXL=60;
struct Edge{
	int t,n;
	ll v;
}e[M];
int hd[N],cnt;
inline void build(int f,int t,ll v){
	e[++cnt]=(Edge){t,hd[f],v};
	hd[f]=cnt;
}
ll a[MAXL+3],dis[N];
bool vis[N];
void insert(ll t){
	for(int j=MAXL;j>=0;--j){
		if(!((t>>j)&1)) continue;
		if(a[j]) t^=a[j];
		else{
			for(int k=0;k<j;++k){
				if((t>>k)&1) t^=a[k];
			}
			for(int k=j+1;k<=MAXL;++k){
				if((a[k]>>j)&1){
					a[k]^=t;
				}
			}
			a[j]=t;
			return;
		}
	}
}
int n,m;
void dfs(int u,ll now){
	dis[u]=now;vis[u]=1;
	for(int i=hd[u];i;i=e[i].n){
		int v=e[i].t;
		if(!vis[v]){
			dfs(v,now^e[i].v);
		}else{
			insert(now^e[i].v^dis[v]);
		}
	}
}
ll query(ll x){
	for(int i=MAXL;i>=0;--i){
		if((x^a[i])>x){
			x^=a[i];
		}
	}
	return x;
}
int main(){
	scanf("%d%d",&n,&m);
	int a,b;ll d;
	for(int i=1;i<=m;++i){
		scanf("%d%d%lld",&a,&b,&d);
		build(a,b,d);
		build(b,a,d);
	}
	dfs(1,0);
	printf("%lld",query(dis[n]));
	return 0;
}

P4301 [CQOI2013] 新Nim游戏

#include<bits/stdc++.h>
using namespace std;

const int N=105;
int a[40],d[N];

int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&d[i]);
	}
	sort(d+1,d+n+1,greater<int>());
	long long ans=0;
	for(int i=1;i<=n;++i){
		int t=d[i];
		for(int j=31;j>=0;--j){
			if(!((t>>j)&1)) continue;
			if(a[j]) t^=a[j];
			else{
				a[j]=t;
				break;
			}
		}
		if(!t) ans+=d[i];
	}
	printf("%lld",ans);
	return 0;
}

P3292 [SCOI2016]幸运数字

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=20000+5,MAXL=61;
struct Edge{
	int t,n;
}e[N<<1];
int hd[N],cnt;
inline void build(int f,int t){
	e[++cnt]=(Edge){t,hd[f]};
	hd[f]=cnt;
}
struct Lbasis{//Linear Basis 
	ll a[MAXL+1];
	Lbasis(){memset(a,0,sizeof a);}
	Lbasis(const Lbasis& b){memcpy(a,b.a,sizeof a);} 
	void insert(ll t){
		for(int j=MAXL;j>=0;--j){
			if(!((t>>j)&1)) continue;
			if(a[j]) t^=a[j];
			else{
				for(int k=0;k<j;++k){
					if((t>>k)&1) t^=a[k];
				}
				for(int k=j+1;k<=MAXL;++k){
					if((a[k]>>j)&1){
						a[k]^=t;
					}
				}
				a[j]=t;
				return;
			}
		}
	}
	void merge(const Lbasis &b){
		for(int i=MAXL;i>=0;--i){
			if(b.a[i]){
				insert(b.a[i]);
			}
		}
	}
	ll max(){
		ll res=0;
		for(int i=0;i<=MAXL;++i){
			res^=a[i];
		}
		return res;
	}
}b[20][N];
int dep[N],anc[20][N];
ll val[N];
void dfs(int u,int f){
	dep[u]=dep[f]+1;
	anc[0][u]=f;
	b[0][u].insert(val[u]);
	for(int i=1;anc[i-1][u];++i){
		anc[i][u]=anc[i-1][anc[i-1][u]];
		b[i][u]=b[i-1][u];
		b[i][u].merge(b[i-1][anc[i-1][u]]);
	}
	for(int i=hd[u];i;i=e[i].n){
		int v=e[i].t;
		if(v==f) continue;
		dfs(v,u);
	}
}
ll ask(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	int dd=dep[x]-dep[y];
	Lbasis res;
	for(int i=19;i>=0;--i){
		if(dd&(1<<i)){
			res.merge(b[i][x]);
			x=anc[i][x];
		}
	}
	if(x==y){
		res.insert(val[x]);
		return res.max();
	}
	for(int i=19;i>=0;--i){
		if(anc[i][x]!=anc[i][y]){
			res.merge(b[i][x]);res.merge(b[i][y]);
			x=anc[i][x];y=anc[i][y];
		}
	}
	res.insert(val[x]);res.insert(val[y]);res.insert(val[anc[0][x]]);
	return res.max();
}
int n;
int main(){
	int q;
	scanf("%d%d",&n,&q);
	int a,b;
	for(int i=1;i<=n;++i){
		scanf("%lld",&val[i]);
	}
	for(int i=1;i<n;++i){
		scanf("%d%d",&a,&b);
		build(a,b);build(b,a);
	}
	dfs(1,0);
	while(q--){
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%lld\n",ask(x,y));
	}
	return 0;
}

10.9

Codeforces Round #747 (Div. 2)

A

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		ll n;
		scanf("%lld",&n);
		printf("%lld %lld\n",-(n-1),n);
	}
	return 0;
}

B

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod=1e9+7;
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		ll n,k;
		scanf("%lld%lld",&k,&n);
		ll ans=0,pw=1;
		while(n){
			if(n&1){
				ans=(ans+pw)%mod;
			}
			pw=(pw*k)%mod;
			n>>=1;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

C

#include<bits/stdc++.h>
using namespace std;

const int N=5e5+5;
char s[N];

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n;char tar[5];
		scanf("%d%s%s",&n,tar,s+1);
		char c=tar[0];
		bool eq=1;
		for(int i=1;i<=n;++i){
			if(c!=s[i]){
				eq=0;
				break;
			}
		}
		if(eq){
			puts("0");
			continue;
		}
		int ans=-1;
		for(int i=2;i<=n;++i){
			bool f=1;
			for(int j=i;j<=n;j+=i){
				if(s[j]!=c){
					f=0;
					break;
				}
			}
			if(f){
				ans=i;
				break;
			}
		}
		if(ans!=-1){
			printf("1\n%d\n",ans);
		}else{
			printf("2\n%d %d\n",n-1,n);
		}
	}
	return 0;
}

E1

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod=1e9+7,p=mod;
void exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
	    x=1,y=0;return;
	}
	exgcd(b,a%b,x,y);
	ll t=x;x=y;y=t-a/b*y;
}
ll inv(ll a){
    ll x,y;
    exgcd(a,p,x,y);
    return (x+p)%p;
} 
ll iv;
ll f(ll n){
	if(n==1) return 6;
	ll t=f(n-1)*iv%mod;
	return t*t%mod*96ll%mod;
}

int main(){
	ll n;
	iv=inv(6);
	cin>>n;
	cout<<f(n);
	return 0;
}

E2


#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod=1e9+7;
ll qpow(ll a,ll p){
    ll ans=1;
    a%=mod;
    while(p){
        if(p&1){
            ans=(ans*a)%mod;
        }
        a=(a*a)%mod;
        p>>=1;
    }
    return ans%mod;
}
int color[10][10]={{1,2,4,5},{0,2,3,5},{0,1,3,4},{1,2,4,5},{0,2,3,5},{0,1,3,4}};
map<ll,int> label;
ll dp[7][(60*10000)+5];
int c[(60*10000)+5];
vector<vector<int> > G;
ll dfs(int u,int cl){
	if(c[u]!=-1&&c[u]!=cl){
		return 0;
	}
	if(~dp[cl][u]){
		return dp[cl][u];
	}
	if(G[u].empty()){
		return dp[cl][u]=1;
	}
	ll sum[2]={0,0};
	for(int i=0;i<4;++i){
		for(int j=0;j<G[u].size();++j){
			sum[j]=(sum[j]+dfs(G[u][j],color[cl][i]))%mod;
		}
	}
	if(G[u].size()==1){
		sum[1]=1;
	}
	return dp[cl][u]=(sum[0]*sum[1])%mod;
}
int main(){
    map<string,ll>mp;
    mp["white"] = 0;
    mp["blue"] = 1;
    mp["red"] = 2;
    mp["yellow"] = 3;
    mp["green"] = 4;
    mp["orange"] = 5;
    ll k,n;cin>>k>>n;
    map<ll,int> ar;
    ll totno=(1ll<<k)-1;
    int lab=0;
    for(int i=1;i<=n;++i){
    	ll x;string s;
    	cin>>x>>s;
    	ar[x]=mp[s];
    	ll cur=x;
    	while(cur>=1&&!label.count(cur)){
    		label[cur]=++lab;
    		--totno;
    		cur/=2;
    	}
    }
    memset(dp,-1,sizeof dp);
    memset(c,-1,sizeof c);
    G.assign(lab+5,vector<int>());
    for(auto x:label){
    	if(ar.count(x.first)){
    		c[x.second]=ar[x.first];
    	}
    	if(label.count(x.first<<1)){
    		G[x.second].push_back(label[x.first<<1]);
    	}
    	if(label.count(x.first<<1|1)){
    		G[x.second].push_back(label[x.first<<1|1]);
    	}
    }
    ll ans=0;
    for(int i=0;i<6;++i)
    	ans=(ans+dfs(label[1],i))%mod;
    ans=(ans*qpow(4,totno))%mod;
    cout<<ans;
	return 0;
}

MinamiMelon

十月第一周学习记录