P3736 [HAOI2016] 字符合并
有一个长度为 \(n\) 的 \(01\) 串，你可以每次将相邻的 \(k\) 个字符合并，得到一个新的字符并获得一定分数。
得到的新字符和分数由这 \(k\) 个字符确定。你需要求出你能获得的最大分数。
-
\(1≤n≤300\)，\(1<k≤8\)。
-
\(c_i∈{0,1}\)，\(1≤w_i≤10^9\)。
对于最大分数，则尽量合并更多的字符，考虑\(k\le8\)可以对\(k\)状压，设计\(f_{l,r,t}\)为区间\([l,r]\)中最终被合并的状态是\(t\)的最大分数，易得这些区间不会相交，则枚举中间的断点\(mid\in [l,r]\)，打表很明显能够发现当串的长度为\(a(k-1)+1\)时该串最后生成串的长度一定为\(1\)，则当串的长度为\(len\)时，我们考虑\(S\)的最后一位是怎么来的，最后该串的长度为\((len-1) \mod {(k-1)}+1\)
则转移如下：
-
\(dp[i][j][S]= dp[i][mid][S>>1] + dp[mid+1][j][S\&1]\)
-
对于长度为\(1\)的区间单独讨论
c++
#include"bits/stdc++.h"
using namespace std;
const int N = 310,K = 8;
#define inl inline
#define reg register
#define regi register int
#define PII pair<int,int>
#define ll long long
const int INF = 1e9 + 10;
ll n,k,a[N],c[1 << K],w[1 << K],f[N][N][1 << K];
inl ll read(void)
{
ll x = 0,f = 1;char ch = getchar();
while(!isdigit(ch)) f = ch == '-' ? - 1 : f,ch = getchar();
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0',ch = getchar();
return x * f;
}
int main(void)
{
n = read(),k = read();
for(regi i = 1;i <= n;i ++) a[i] = read();
for(regi i = 0;i < (1 << k);i ++) c[i] = read(),w[i] = read();
for (regi i = 1;i <= n;i ++)
for (regi j = 1;j <= n;j ++)
for (regi z = 0;z < (1 << k);z ++)
f[i][j][z] = - INF;
for(regi i = n;i >= 1;i --)
{
for(regi j = i;j <= n;j ++)
{
if(i == j)
{
f[i][j][a[i]] = 0;
continue;
}
ll len = j - i;
len %= k - 1;
if(!len) len = k - 1;
for(regi mid = j;mid > i;mid -= k - 1)
{
for(regi S = 0;S < (1 << len);S ++)
{
f[i][j][S << 1] = max(f[i][j][S << 1],f[i][mid - 1][S] + f[mid][j][0]);
f[i][j][S << 1 | 1] = max(f[i][j][S << 1 | 1],f[i][mid - 1][S] + f[mid][j][1]);
}
}
if(len == k - 1)
{
ll g[2];
g[0] = g[1] = - INF;
for(regi S = 0;S < (1 << k);S ++) g[c[S]] = max(g[c[S]],f[i][j][S] + w[S]);
f[i][j][0] = g[0],f[i][j][1] = g[1];
}
}
}
ll ans = - INF;
for(regi i = 0;i < (1 << k);i ++) ans = max(ans,f[1][n][i]);
printf("%lld",ans);
return 0;
}
P5336 [THUSC2016] 成绩单
就是给出一个序列 \(a[1...n]\) 还有\(A\)和\(B\)
每次从序列里抽出连续的一段，这一段的代价为
\(A+B∗(max−min)^2\)
\(n≤50，a≤1500，b≤10，w_i≤1000。\)
设 \(f_{l,r}\)为区间\([l,r]\)成绩单全部被发放所需要的最小代价，\(g_{l,r,mn,mx}\)为区间\([l,r]\)最小值\(mn\)最大值\(mx\)最小代价
易得 \(f_{l,r}=min{\{g_{l,r,mn,mx}+a+b\times(mx-mn)^2\}}\)
1.保留第\(r+1\)张成绩单不取走，未来与 \([l,r]\) 中的成绩单共同取走： \(g_{l,r+1,min(mn,w[r+1]),max(mx.w[r+1])}=min(g_{l,r,mn,mx})\)
- 2.枚举 \(k\)，将 \([r+1,k]\) 这段区间的成绩单共同取走
\(g_{l,k,mn,mx}=min(g_{l,r,mn,mx}+f_{r+1,k})\)
可以转化为：
\(g_{l,r,mn,mx}=min(g_{l,k,mn,mx}+f_{k+1,r})\)
c++
#include"bits/stdc++.h"
using namespace std;
const int N = 60;
#define inl inline
#define reg register
#define regi register int
#define PII pair<int,int>
//#define ll long long
int n,a,b,w[N],f[N][N],g[N][N][N][N],d[N];
int tot;
inl int read(void)
{
int x = 0,f = 1;char ch = getchar();
while(!isdigit(ch)) f = ch == '-' ? - 1 : f,ch = getchar();
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0',ch = getchar();
return x * f;
}
int main(void)
{
n = read(),a = read(),b = read();
for(regi i = 1;i <= n;i ++) w[i] = read(),d[i] = w[i];
sort(d + 1, d + n + 1);tot = unique(d + 1,d + n + 1) - d - 1;
for(regi i = 1;i <= n;i ++) w[i] = lower_bound(d + 1,d + tot + 1,w[i]) - d,f[i][i] = a;
memset(g,0x3f,sizeof g);memset(f,0x3f,sizeof f);
for(regi i = 1;i <= n;i ++) g[i][i][w[i]][w[i]] = 0;
for(regi len = 1;len <= n;len ++)
for(regi l = 1,r = len;r <= n;l ++,r ++)
for(regi mn = 1;mn <= tot;mn ++)
{
for(regi mx = mn;mx <= tot;mx ++)
{
for(regi k = l;k < r;k ++) g[l][r][mn][mx] = min(g[l][k][mn][mx] + f[k + 1][r],g[l][r][mn][mx]);
g[l][r + 1][min(mn,w[r + 1])][max(mx,w[r + 1])] = min(g[l][r + 1][min(mn,w[r + 1])][max(mx,w[r + 1])],g[l][r][mn][mx]);
f[l][r] = min(f[l][r],g[l][r][mn][mx] + a + b * (d[mx] - d[mn]) * (d[mx] - d[mn]));
}
}
printf("%d",f[1][n]);
return 0;
}
P3349 [ZJOI2016] 小星星
抽象化题意：
一个\(n\)个节点的树，和一个\(n\)个节点的图，要求给树上的每个节点编号，使得编号是一个\(1\)到\(n\)的排列，并且要满足树上任意一条边\((u,v)\)，图中一定要有边\((x_u,x_v)\)（\(x_u\)表示点\(u\)的编号），求方案数。
\(n≤17\)，\(m≤\frac{1}{2}n(n-1)\)。
考虑暴力：设\(f_{i,j,S}\)为节点\(i\)编号为\(j\)，\(i\)的子树内的编号集合为\(S\)的方案数。这样转移时间复杂度为\(O(n^3\times3^n)\)肯定过不去
考虑去掉\(S\)这一维\(f_{i,j}\)为节点\(i\)编号为\(j\)的方案数
如果出现重复的编号，考虑容斥
\(2^n\)枚举\(\{1,2,3...n\}\)的一个子集\(S\)，显然容斥系数是\((-1)^{n-|S|}\)
c++
#include"bits/stdc++.h"
using namespace std;
const int N = 20;
#define inl inline
#define reg register
#define regi register int
#define PII pair<int,int>
#define ll long long
ll n,m,tot,f[N],exi[N];
ll dp[N][N],ans;
vector ver[N];
struct node
{
ll v,net;
}edge[N << 1];
inl ll read(void)
{
ll x = 0,f = 1;char ch = getchar();
while(!isdigit(ch)) f = ch == '-' ? - 1 : f,ch = getchar();
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0',ch = getchar();
return x * f;
}
inl void dfs(int u,int fa)
{
for(regi i = 1;i <= n;i ++) dp[u][i] = 1;
for(regi i = f[u];i;i = edge[i].net)
{
int v = edge[i].v;
if(v == fa) continue;
dfs(v,u);
for(regi j = 1;j <= n;j ++)
{
ll s = 0;
for(regi l = 0;l < ver[j].size();l ++)
{
int k = ver[j][l];
s += dp[v][k] * (exi[j] & exi[k]);
}
dp[u][j] *= s;
}
}
}
int main(void)
{
n = read(),m = read();
for(regi i = 1;i <= m;i ++)
{
int u = read(),v = read();
ver[u].push_back(v);
ver[v].push_back(u);
}
for(regi i = 2;i <= n;i ++)
{
int u = read(),v = read();
edge[++ tot] = node{v,f[u]},f[u] = tot;
edge[++ tot] = node{u,f[v]},f[v] = tot;
}
for(regi i = 0;i < (1 << n);i ++)
{
int x = n;
memset(dp,0,sizeof dp);
memset(exi,0,sizeof exi);
for(regi j = 1;j <= n;j ++) if(i & (1 << j - 1)) exi[j] = 1,x --;
dfs(1,0);
for(regi j = 1;j <= n;j ++) ans += dp[1][j] * (x % 2 ? - 1 : 1);
}
printf("%lld",ans);
return 0;
}
P4516 [JSOI2018] 潜入行动
给一棵 \(n\) 个点的树，试选取 \(k\) 个点，使得树中的每一个点都至少与该 \(k\) 个点中的一个点直接相连。( \(k\) 个点中的点不与自身相连 ）
\(n≤10^5,k≤100\)
很明显，要跑背包
\(dp[x][i][0/1][0/1]\)表示以\(x\)为根的子树中共放了\(i\)个监听装置，其中\(x\)点放没放装置，\(x\)点有没有被监听到的方案数
\(dp[x][i+j][0][0]=∑dp[x][i][0][0]∗dp[v][j][0][1]\)
\(dp[x][i+j][1][0]=∑dp[x][i][1][0]∗(dp[v][j][0][0]+dp[v][j][0][1])\)
\(dp[x][i+j][0][1]=∑(dp[x][i][0][1]∗(dp[v][j][0][1]+dp[v][j][1][1])+dp[x][i][0][0]∗dp[v][j][1][1])\)
\(dp[x][i+j][1][1]=∑(dp[x][i][1][0]∗(dp[v][j][1][0]+dp[v][j][1][1])+dp[x][i][1][1]∗(dp[v][j][0][0]+dp[v][j][0][1]+dp[v][j][1][0]+dp[v][j][1][1]))\)
c++
#include"bits/stdc++.h"
using namespace std;
#define inl inline
#define reg register
#define regi register int
#define ll long long
#define PII pair<int,int>
const int N=100015,P=1e9+7,M=101;
inl int read(void)
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
int n,K;
int f[N][M][2][2],tmp[M][2][2];
int sz[N];
int ver[N<<1],net[N<<1],cnt,head[N];
void addedge(int u,int v){ver[++cnt]=v,net[cnt]=head[u],head[u]=cnt;}
void dfs(int u,int fa)
{
sz[u]=1,f[u][0][0][0]=f[u][1][1][0]=1;
for(int i=head[u];i;i=net[i])
{
int v=ver[i];
if(v==fa) continue;
dfs(v,u);
for(int j=0;j<=sz[u]&&j<=K;j++)
for(int k=0;k<=sz[v]&&j+k<=K;k++)
{
if(f[u][j][0][1])
(tmp[j+k][0][1]+=1ll*f[u][j][0][1]*(f[v][k][0][1]+f[v][k][1][1])%P)%=P;
if(f[u][j][1][0])
(tmp[j+k][1][0]+=1ll*f[u][j][1][0]*(f[v][k][0][0]+f[v][k][0][1])%P)%=P,
(tmp[j+k][1][1]+=1ll*f[u][j][1][0]*(f[v][k][1][0]+f[v][k][1][1])%P)%=P;
if(f[u][j][0][0])
(tmp[j+k][0][0]+=1ll*f[u][j][0][0]*f[v][k][0][1]%P)%=P,
(tmp[j+k][0][1]+=1ll*f[u][j][0][0]*f[v][k][1][1]%P)%=P;
if(f[u][j][1][1])
{
int res=0;
(res+=f[v][k][0][0])%=P,(res+=f[v][k][0][1])%=P,
(res+=f[v][k][1][0])%=P,(res+=f[v][k][1][1])%=P,
(tmp[j+k][1][1]+=1ll*f[u][j][1][1]*res%P)%=P;
}
}
sz[u]+=sz[v];
for(int j=0;j<=sz[u]&&j<=K;j++)
f[u][j][0][0]=tmp[j][0][0],tmp[j][0][0]=0,
f[u][j][0][1]=tmp[j][0][1],tmp[j][0][1]=0,
f[u][j][1][0]=tmp[j][1][0],tmp[j][1][0]=0,
f[u][j][1][1]=tmp[j][1][1],tmp[j][1][1]=0;
}
}
signed main(void)
{
n=read(),K=read();
for(int i=1,u,v;i<=n-1;i++) u=read(),v=read(),addedge(u,v),addedge(v,u);
dfs(1,0);
int ans=(f[1][K][0][1]+f[1][K][1][1])%P;
printf("%d",ans);
return 0;
}
CF1442D Sum
给定 \(n\) 个不降的数组。有一个值 \(ans\)，初始为 \(0\)。你需要进行如下操作 \(k\) 次：
- 选择一个数组，把 \(ans\) 加上数组的第一个元素，之后把它删除。
请求出 \(ans\) 最大是多少。
所有数组的元素总个数 \(\leq 10^6\)，\(n,k\leq 3000\)。
对于所有序列，显然选部分的序列个数 \(≤1\)，其它全选或全不选。
有了上述结论，我们只要枚举哪个选部分，其余数列当做 \(01\) 背包问题即可。
-
对于区间 \([l,r]\)，找到一个中间点 \(mid\)。
-
先将 \([l,mid]\) 中的物品插入到背包中，然后 \(solve(mid+1,r)\)。
-
将背包还原，再将 \([mid+1,r]\) 中的物品插入到背包中，然后 \(solve(l,mid)\)。
-
这样一来，如果当前的区间是 \([l,r]\)，可以发现此时背包中的物品恰为 \([1,l−1]∪[r+1,n]\) 中的物品！
-
因此，当 \(l=r\) 时我们得到的就是想要的答案。
时间复杂度为\(O(knlogn)\)轻松过
c++
#include"bits/stdc++.h"
using namespace std;
const int N = 3010;
#define inl inline
#define reg register
#define regi register int
#define PII pair<int,int>
#define int long long
using namespace std;
inl int read(void)
{
int x = 0,f = 1;char ch = getchar();
while(!isdigit(ch)) f = ch == '-' ? - 1 : f,ch = getchar();
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0',ch = getchar();
return x * f;
}
int n,k,x,t[N],sum[N],ans,dp[N];
vector a[N];
void solve(int l,int r)
{
int mid = (l + r) >> 1;
if(l == r)
{
int now = 0;
for(int i = 0;i <= min(t[l],k);i ++)
{
ans = max(ans,now + dp[k - i]);
now += a[l][i];
}
return;
}
for(regi i = mid + 1;i <= r;i ++)
for(regi j = k;j >= t[i];j --)
dp[j] = max(dp[j],dp[j - t[i]] + sum[i]);
solve(l,mid);
for(regi i = 0;i <= k;i ++) dp[i] = f[i];
for(regi i = l;i <= mid;i ++)
for(regi j = k;j >= t[i];j --)
dp[j] = max(dp[j],dp[j - t[i]] + sum[i]);
solve(mid + 1,r);
}
signed main(void)
{
n = read(),k = read();
for(regi i = 1;i <= n;i ++)
{
t[i] = read();
for(regi j = 1,tmp;j <= t[i];j ++)
{
tmp = read();
a[i].push_back(tmp);
sum[i] += tmp;
}
}
solve(1,n);
printf("%lld",ans);
return 0;
}
P6773 [NOI2020] 命运
题意
给定一棵 \(n\) 个点的树和 \(m\) 条限制，你可以给树上的每一条边赋一个 \(0\) 或 \(1\) 的权值。对于所有限制 \((u,v)\)（保证 \(v\) 为 \(u\) 的祖先） 你需要保证 \(u\) 到 \(v\) 上至少有一条边的权值为 \(1\)，求赋值方案数。
Data Range:\(1≤n,m≤5×10^5\)
设\(f_{i,j}\)表示\(i\)往上第一条权值为\(1\)的边的深度为\(j\)时，子树的方案数，那么对于每一条限制\((x=>y)\)，相当于令\(y\)的\(f_{y,p}=0(p\in[dep_x,n])\)，不妨记\(lim_i\)表示\(i\)往上最远的权值为\(1\)的边至多深度为多浅
转移时，考虑自己与儿子之间的边为\(1\)还是\(0\)，可以得到：
\[f_{i,j}=\prod_{y \in son}{f_{y,j}+f_{y,dep_y}} \]用线段树合并来优化，在计算贡献之前令所有儿子的\(f_{y,j}\)加上\(f_{y,dep_y}\)，贡献时恰好是让自己的第\(j\)位贡献父亲的第\(j\)位，这完全是对应的，用线段树维护第二维，维护区间加和区间乘
c++
#include"bits/stdc++.h"
using namespace std;
const int N=5e5+15,P=998244353;
#define inl inline
#define reg register
#define regi register int
#define PII pair<int,int>
#define ll long long
#define int long long
inl int read(void)
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
vector v[N];
int n,m;
void mod(ll &x){x%=P;}
struct node
{
int ls,rs;
int s,mul;
#define mul(p) tr[p].mul
#define ls(p) tr[p].ls
#define rs(p) tr[p].rs
#define s(p) tr[p].s
}tr[N<<6];
void pushdown(int p)
{
if(ls(p))
s(ls(p))=s(ls(p))*mul(p)%P,mul(ls(p))=mul(ls(p))*mul(p)%P;
if(rs(p))
s(rs(p))=s(rs(p))*mul(p)%P,mul(rs(p))=mul(rs(p))*mul(p)%P;
mul(p)=1;
}
int head[N],ver[N<<1],net[N<<1],cnt,dep[N];
void addedge(int a,int b)
{
ver[++cnt]=b,net[cnt]=head[a],head[a]=cnt;
}
ll query(int p,int l,int r,int x)
{
if(!p||r<=x) return s(p);
int mid=l+r>>1;ll s=0;
pushdown(p);
if(mid<=x-1) mod(s+=query(rs(p),mid+1,r,x));
mod(s+=query(ls(p),l,mid,x));
return s;
}
int tot;
void change(int &p,int l,int r,int x)
{
p=++tot,s(p)=mul(p)=1;
if(l==r) return ;
int mid=l+r>>1;
if(x<=mid) change(ls(p),l,mid,x);
else change(rs(p),mid+1,r,x);
}
int merge(int x,int y,int l,int r,ll &s1,ll &s2)
{
if(!x&&!y) return 0;
if(!x||!y)
{
if(!x)
{
mod(s1+=s(y));
mul(y)=mul(y)*s2%P,s(y)=s(y)*s2%P;
return y;
}
mod(s2+=s(x));
s(x)=s(x)*s1%P,mul(x)=mul(x)*s1%P;
return x;
}
if(l==r)
{
ll tx=s(x),ty=s(y);mod(s1+=ty);
s(x)=(s(x)*s1+s(y)*s2)%P;
mod(s2+=tx);
return x;
}
pushdown(x),pushdown(y);
int mid=l+r>>1;
ls(x)=merge(ls(x),ls(y),l,mid,s1,s2);
rs(x)=merge(rs(x),rs(y),mid+1,r,s1,s2);
s(x)=(s(ls(x))+s(rs(x)))%P;
return x;
}
int boring[N];
void dfs(int x,int fa)
{
dep[x]=dep[fa]+1;int res=0;
for(auto t:v[x]) res=max(res,dep[t]);
change(boring[x],0,n,res);
for(int i=head[x];i;i=net[i])
{
int y=ver[i];
if(y==fa) continue;
dfs(y,x);
ll S=query(boring[y],0,n,dep[x]),S_=0;
boring[x]=merge(boring[x],boring[y],0,n,S,S_);
}
}
signed main(void)
{
n=read();
for(int i=1,u,v;i<=n-1;i++)
u=read(),v=read(),addedge(u,v),addedge(v,u);
m=read();
for(int i=1,x,y;i<=m;i++)
x=read(),y=read(),v[y].push_back(x);
dfs(1,0);
printf("%lld",query(boring[1],0,n,0));
return 0;
}
P4590 [TJOI2018] 游园会
题目大意
令 \(f(i)\) 为满足下面几条限制的字符串个数：
- 长度为 \(n\)，字符集为 \({N,O,I}\)。
- 不包含子串 \(NOI\)。
- 与模式串 \(s\) 的最长公共子序列\(（lcs）\)长度为 \(i\)。
对于 \(i∈[0,k]\)，求出 \(f_i\) 的值，对 \(10^9+7\) 取模。
\(DP\) 套 \(DP\) 板子题
所谓 \(dp\) 套 \(dp\) ，实际上就是在说求解一个 \(dp\) 的过程中，我们用另一个 \(dp\) 求解出他应该从某个状态转移到另一个状态。
设求 \(LCS\) 的 \(dp:\) \(dp_{i,j}=max{\{dp_{i-1,j},dp_{i,j-1},dp_{i-1,j-1}+[s_i=t_i]\}}\)
显然当\(i\)一定时，\(dp_{i,j}\)时单调不降的，且相邻两个数的差\(\in[0,1]\)，通过状压把 \(LCS\) 数组的状态设到转移方程里
设\(f_{i,S,0/1/2}\)表示当考虑了串的前\(i\)位的时候，\(LCS\)的\(dp\)式子的状态为\(S\)，最后几位同"\(NOI\)"的匹配到了第\(k\)位\((k\in[0,2])\)，此时的方案数
设\(sta_{S,j}\)表示\(LCS\)的\(dp\)式子在状态为\(S\)时新加入一位\(j\)后的\(dp\)式子状压下来的情况，设\(nxt_{x,y}\)表示下一个"\(NOI\)"匹配的状态，初始状态\(f_{0,0,0}=1\)，
\[f_{i,sta_{S,x},nxt_{y,x}}\to f_{i,sta_{S,x},nxt_{y,x}}+f_{i-1,S,y} \]时间复杂度为\(O(n2^k+k2^k)\)
c++
#include"bits/stdc++.h"
using namespace std;
const int N = 1010,mod = 1e9 + 7;
#define inl inline
#define reg register
#define regi register int
#define PII pair<int,int>
//#define ll long long
inl int read(void)
{
int x = 0,f = 1;char ch = getchar();
while(!isdigit(ch)) f = ch == '-' ? - 1 : f,ch = getchar();
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0',ch = getchar();
return x * f;
}
int n,m,f[2][N],a[N],b[N];
int nxt[3][3]={{1,0,0},{1,2,0},{1,0,3}};
int dp[5][100010][5],sta[100010][5];
int ans[N],now;
char ch[N];
inl void init()
{
for(int p = 0;p < (1 << m);p ++)
{
for(int k = 0;k < m;k ++) f[0][k + 1] = f[0][k] + ((p >> k) & 1);
for(int j = 0;j <= 2;j ++)
{
for(int k = 1;k <= m;k ++)
{
f[1][k] = max(f[1][k - 1],f[0][k]);
if(b[k] == j) f[1][k] = max(f[1][k],f[0][k - 1] + 1);
}
int t = 0;
for(int i = 1;i <= m;i ++) if(f[1][i] > f[1][i - 1]) t |= (1 << (i - 1));
sta[p][j] = t;
}
}
}
int main(void)
{
n = read(),m = read();
cin >> (ch + 1);
for(int i = 1;i <= m;i ++)
{
if(ch[i] == 'N') b[i]=0;
if(ch[i] == 'O') b[i]=1;
if(ch[i] == 'I') b[i]=2;
}
init();
dp[0][0][0] = 1;
for(regi i = 1;i <= n;i ++)
{
memset(dp[now ^ 1],0,sizeof(dp[now ^ 1]));
for(regi p = 0;p < (1 << m);p ++)
{
for(regi j = 0;j <= 2;j ++)
{
for(regi k = 0;k <= 2;k ++)
{
if(j == 2 && k == 2) continue;
int fa = nxt[j][k];
dp[now ^ 1][sta[p][k]][fa] += dp[now][p][j];
dp[now ^ 1][sta[p][k]][fa] %= mod;
}
}
}
now ^= 1;
}
for(regi p = 0;p < (1 << m);p ++)
{
for(regi j = 0;j <= 2;j ++)
{
int fa = 0,le = p;
while(le){
if(le %2 == 1) fa ++;
le /= 2;
}
ans[fa] += dp[now][p][j];
ans[fa] %= mod;
}
}
for(regi i = 0;i <= m;i++) printf("%d\n",ans[i]);
return 0;
}
标签：std,ch,int,long,一些,dp,define From： https://www.cnblogs.com/empty-space/p/18515658