Codeforces 704C - Black Widow（dp）
2024-09-04 00:33:31
u1s1 感觉这种题被评到 *2900 是因为细节太繁琐了，而不是题目本身的难度，所以我切掉这种题根本不能说明什么……
首先题目中有一个非常喜闻乐见的条件那就是 \(k_i\le 2\)，因此我们考虑将每个布尔型变量看作一个点，对于出现在同一组的两个布尔型变量 \(x,y\) 连边 \((x,y)\)，那么显然得到的图一定是一堆环、一堆链以及一堆孤立点。
考虑对于每个环及每个链分别跑一遍 DP。对于链我们就设 \(dp_{i,j,k}\) 表示考虑到链上第 \(i\) 个点，第 \(i\) 个点对应的布尔变量的取值为 \(j\)，当前所有布尔表达式的值异或起来为 \(k\) 的方案数，转移就枚举上一个布尔变量的值即可。对于环我们就多开一维 \(dp_{i,j,k,fst}\)，\(fst\) 表示环上第一个数为 \(fst\)，然后我们最后就强制从 \(j=fst\) 的 \(dp\) 计算答案即可。最后再套一个大背包，\(f_{i,j}\) 表示考虑到前 \(i\) 个连通块（环+链），这些连通块中所有表达式异或起来为 \(j\) 的方案数，这个同样可以 \(\mathcal O(1)\) 转移，总复杂度线性。
程序大致框架就这么多，不过此题细节实在是太太太多了，如果能 1A 就真的是神仙了，这里列出几个容易犯的错误：
- 对于 \(x_i\lor\lnot x_i\) 的表达式，不论 \(x_i\) 取什么该表达式的值都是 \(1\)，我们考虑随时维护一个 \(goal\) 变量表示我们最终希望所有布尔表达式异或起来是多少，初始 \(goal=1\)，我们每遇到一个这样的表达式都令 \(goal\leftarrow goal\oplus 1\)，最终输出 \(f_{\text{连通块个数},goal}\) instead of \(f_{\text{连通块个数},1}\) 即可。
- 对于 \(x_i\lor x_i\) 或者 \(\lnot x_i\lor\lnot x_i\) 的表达式，显然其等效于一个孤立点。对于每个孤立点，我们也可以将其看作一个连通块，\(f_{i,0}=f_{i,1}=f_{i-1,0}+f_{i-1,1}\)，其中 \(i\) 为该孤立点对应的连通块的编号。
- 对于单一变量的布尔表达式，我们记录一个 \(msk_i\)，取值范围 \(\{-1,0,1\}\)，\(msk_i=-1\) 表示 \(i\) 以 \(\lnot x_i\) 的形式计入答案，\(msk_i=1\) 表示 \(i\) 以 \(x_i\) 的形式计入答案，\(msk_i=0\) 表示 \(i\) 不计入答案。显然我们每遇到一个单一变量的布尔表达式都可以 \(\mathcal O(1)\) 更新 \(msk_i\)。最后对于所有对于图上的孤立点，若 \(msk_i=\pm 1\)，则我们可将其视作一个连通块，\(f_{i,0}=f_{i,1}=f_{i-1,0}+f_{i-1,1}\)。否则你这个变量爱取 \(1\) 就取 \(1\)，爱取 \(0\) 就取 \(0\)，对异或值没有任何影响，答案乘 \(2\)。
- 对于每条链，若其端点以单一变量的形式计入答案，即 \(msk_i\ne 0\)，以 \(msk_i=1\) 为例，那么我们就在 \(dp\) 时候令 \(dp\) 初值为 \(dp_{0,x_i,x_i}=1\) instead of \(dp_{0,x_i,0}=1\) 即可；\(msk_i=-1\) 就令 \(dp_{0,x_i,\lnot x_i}=1\)。结尾处也同理，就在根据结尾处的 \(dp\) 值转移 \(f_{i,j}\) 时稍微改几个细节即可。
总而言之是一道阿巴细节题。
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,63,sizeof(a))
#define pb push_back
#define ppb pop_back
#define mp make_pair
template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}
template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;
namespace fastio{
#define FILE_SIZE 1<<23
char rbuf[FILE_SIZE],*p1=rbuf,*p2=rbuf,wbuf[FILE_SIZE],*p3=wbuf;
inline char getc(){return p1==p2&&(p2=(p1=rbuf)+fread(rbuf,1,FILE_SIZE,stdin),p1==p2)?-1:*p1++;}
inline void putc(char x){(*p3++=x);}
template<typename T> void read(T &x){
x=0;char c=getchar();T neg=0;
while(!isdigit(c)) neg|=!(c^'-'),c=getchar();
while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(neg) x=(~x)+1;
}
template<typename T> void recursive_print(T x){if(!x) return;recursive_print(x/10);putc(x%10^48);}
template<typename T> void print(T x){if(!x) putc('0');if(x<0) putc('-'),x=~x+1;recursive_print(x);}
void print_final(){fwrite(wbuf,1,p3-wbuf,stdout);}
}
const int MAXN=1e5;
const int MOD=1e9+7;
void add(int &x,int y){x+=y;if(x>=MOD) x-=MOD;}
int n,m,msk[MAXN+5],deg[MAXN+5];bool vis[MAXN+5];
int sgn(int x){return (x>0)?0:1;}
struct edge{
int u,v,su,sv,id;
edge(int _u,int _v,int _su,int _sv,int _id):u(_u),v(_v),su(_su),sv(_sv),id(_id){}
};
vector<edge> g[MAXN+5];
int f[MAXN+5][2];
vector<pair<int,pii> > ch;
void dfs(int x,int pre,int rt){
vis[x]=1;
for(int i=0;i<g[x].size();i++){
int y=g[x][i].v,sx=g[x][i].su,sy=g[x][i].sv,id=g[x][i].id;
if(id==pre) continue;ch.pb(mp(y,mp(sx,sy)));
if(y^rt){dfs(y,id,rt);return;}
}
}
int main(){
scanf("%d%d",&m,&n);int goal=1;
memset(msk,-1,sizeof(msk));int mul=1;
f[0][0]=1;int grp_n=0;
for(int i=1;i<=m;i++){
int k;scanf("%d",&k);
if(k==1){
int x;scanf("%d",&x);
if(!~msk[abs(x)]) msk[abs(x)]=sgn(x);
else{
if(msk[abs(x)]^sgn(x)) goal^=1;
msk[abs(x)]=-1;
}
} else {
int u,v;scanf("%d%d",&u,&v);
if(u==v){
vis[abs(u)]=1;grp_n++;
f[grp_n][0]=f[grp_n][1]=(f[grp_n-1][0]+f[grp_n-1][1])%MOD;
} else if(u+v==0) goal^=1,vis[abs(u)]=1,mul=2ll*mul%MOD;
else if(u+v!=0){
g[abs(u)].pb(edge(abs(u),abs(v),sgn(u),sgn(v),i));
g[abs(v)].pb(edge(abs(v),abs(u),sgn(v),sgn(u),i));
deg[abs(u)]++;deg[abs(v)]++;
}
}
}
for(int i=1;i<=n;i++){
if(!deg[i]){
if(!~msk[i]&&!vis[i]) mul=2ll*mul%MOD;
else if(!vis[i]){
grp_n++;
f[grp_n][0]=f[grp_n][1]=(f[grp_n-1][0]+f[grp_n-1][1])%MOD;
}
} else if(deg[i]==1&&!vis[i]){
ch.clear();ch.pb(mp(i,mp(0,0)));dfs(i,0,0);vector<int> dp[2][2];
for(int j=0;j<2;j++) for(int k=0;k<2;k++) dp[j][k].resize(ch.size());
if(~msk[i]) for(int j=0;j<2;j++) dp[j][j^msk[i]][0]=1;
else for(int j=0;j<2;j++) dp[j][0][0]=1;
for(int j=1;j<ch.size();j++){
int su=ch[j].se.fi,sv=ch[j].se.se;
for(int o=0;o<2;o++) for(int p=0;p<2;p++) for(int q=0;q<2;q++){
add(dp[o][((p^su)|(o^sv))^q][j],dp[p][q][j-1]);
}
} grp_n++;int lst=ch.back().fi;
for(int o=0;o<2;o++) for(int p=0;p<2;p++){
int res=o;if(~msk[lst]) res^=(p^msk[lst]);
add(f[grp_n][0],1ll*f[grp_n-1][res]*dp[p][o].back()%MOD);
add(f[grp_n][1],1ll*f[grp_n-1][res^1]*dp[p][o].back()%MOD);
}
// printf("Group %d:\n",grp_n);
// for(int j=0;j<ch.size();j++) printf("%d %d %d\n",ch[j].fi,ch[j].se.fi,ch[j].se.se);
// for(int j=0;j<ch.size();j++) printf("%d %d %d %d\n",dp[0][0][j],dp[0][1][j],dp[1][0][j],dp[1][1][j]);
// printf("%d %d %d\n",i,f[grp_n][0],f[grp_n][1]);
}
}
for(int i=1;i<=n;i++) if(deg[i]==2&&!vis[i]){
ch.clear();ch.pb(mp(i,mp(0,0)));dfs(i,0,i);vector<int> dp[2][2][2];
for(int j=0;j<2;j++) for(int k=0;k<2;k++) for(int l=0;l<2;l++) dp[j][k][l].resize(ch.size());
for(int j=0;j<2;j++) dp[j][0][j][0]=1;
for(int j=1;j<ch.size();j++){
int su=ch[j].se.fi,sv=ch[j].se.se;
for(int o=0;o<2;o++) for(int p=0;p<2;p++)
for(int q=0;q<2;q++) for(int r=0;r<2;r++){
add(dp[o][((p^su)|(o^sv))^q][r][j],dp[p][q][r][j-1]);
}
} grp_n++;int lst=ch.back().fi;
for(int o=0;o<2;o++) for(int p=0;p<2;p++){
add(f[grp_n][0],1ll*f[grp_n-1][o]*dp[p][o][p].back()%MOD);
add(f[grp_n][1],1ll*f[grp_n-1][o^1]*dp[p][o][p].back()%MOD);
}
// printf("Group %d:\n",grp_n);
// for(int j=0;j<ch.size();j++) printf("%d %d %d\n",ch[j].fi,ch[j].se.fi,ch[j].se.se);
// printf("%d %d %d\n",i,f[grp_n][0],f[grp_n][1]);
}
printf("%d\n",1ll*f[grp_n][goal]*mul%MOD);
return 0;
}
/*
8 10
1 -5
2 4 -6
2 -2 -6
2 -7 9
2 10 -1
2 3 -1
2 -8 9
2 5 8
*/
最新文章
- RESTful API URI 设计: 查询（Query）和标识（Identify）
- Python实践所遇问题记录
- DIV的不能包住子集解决办法
- JAVA - ATM机程序
- JS基础---->js中ajax的使用
- Myeclipse优化篇
- longblogV1.0——我的静态博客发布系统
- Eclipse下设置github开发环境
- 【转】Windows环境下.NET 操作Oracle问题
- meta 属性
- 当执行游戏0xc000007b错误的解决方法
- Java面向对象 继承（下）
- Unexpected error from external database driver (1)
- 牛客国庆集训派对Day6 B.Board
- jquery删除onclick属性和设置onclick属性--获取验证码
- day26(分页查询)
- Linux FFmpeg（含x264、lame插件）安装记录
- max，min无法使用的问题
- ZT A2DP协议笔记
- web测试－－数据分层测试