codeforces 461 D Appleman and Complicated Task

NO IMAGE
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

Descritpion


這裡寫圖片描述

Solution


這題和之前沒改出來的矩陣遊走思想是類似的,即唯一確定的第一行確定了整個矩陣。那麼可以設第一行為未知數,討論一下其餘位置的取值情況。可以發現(0,k)能影響到的點滿足是連續的奇數或連續的偶數。那麼抽出奇偶點然後就能用字首異或和做了。
題目轉化為:給定一些限制條件形如sum[l-1]^sum[r]=0或1,求可行方案數
可以回想2sat的做法,把點i拆為i和i’表示i取0或1,討論一下並查集合並判無解就ok

Code


#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#define rep(i,st,ed) for (int i=st;i<=ed;  i)
#define fill(x,t) memset(x,t,sizeof(x))
typedef long long LL;
const int MOD=1000000007;
const int N=200005;
int fa[N],a[N],b[N];
LL ksm(LL x,LL dep) {
if (dep==0) return 1;
if (dep==1) return x;
LL tmp=ksm(x,dep/2);
if (dep%2) return tmp*tmp%MOD*x%MOD;
return tmp*tmp%MOD;
}
int get_father(int now) {
return (fa[now]==-1)?(now):(fa[now]=get_father(fa[now]));
}
bool merge(int x,int y) {
x=get_father(x); y=get_father(y);
if (x==get_father(x^1)) return false;
if (y==get_father(y^1)) return false;
if (x!=y) fa[x]=y;
return true;
}
bool check(int x,int y,int z) {
if (z==0) {
return merge(x*2,y*2)&&merge(x*2 1,y*2 1);
} else if (z==1) {
return merge(x*2,y*2 1)&&merge(x*2 1,y*2);
}
}
int main(void) {
fill(fa,-1);
int n,m; scanf("%d%d",&n,&m);
rep(i,1,m) {
int x,y; scanf("%d%d",&x,&y);
x-=1; y-=1;
char ch[2]; scanf("%s",ch);
int l=std:: abs(x-y);
int r=std:: min(x y,2*(n-1)-(x y));
if (!check(l,r 2,ch[0]=='o')) {
puts("0");
return 0;
}
}
LL ans=0;
rep(i,0,n*2 3) if (get_father(i)==i) ans  ;
LL prt=ksm(2,ans/2-2);
printf("%lld\n", prt);
return 0;
}

相關文章

程式語言 最新文章