[cf461D]Appleman and Complicated Task

假设该矩形是aij，那么有a(i,j)=a(i-1,j-1)^a(i-1,j+1)^a(i-2,j)，不断递归下去可以发现a(i,j)=a(1,y-x+1)^a(1,y-x+3)^……^a(1,x+y-1)。

那么，对第一行处理前缀和，Si=S(i-2)^a(1,i)，即给出了两个数S的异或，只需将每一个点裂点为i和i’，然后若Si^Sj=0，并查集上连边(i,j)(i’,j’)，否则连(i,j’)(i’,j)，最后只需判断i和i’是否相连，相连即为0（这个可以理解为i表示i上是1，i’表示i上是0）。

最后，统计出有多少联通块，设有S个，则答案是$2^{(S-4)/2}$（如果没有约束，答案是$2^{n}=2^{2n+4-4)/2$）

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 int n,m,x,y,ans,f[200005];

 4 char s[11];

 5 int find(int k){

 6     if (k==f[k])return k;

 7     return f[k]=find(f[k]);

 8 }

 9 void add(int x,int y){

10     if (find(x)!=find(y))f[find(x)]=find(y);

11 }

12 int main(){

13     scanf("%d%d",&n,&m);

14     for(int i=1;i<=2*n+3;i++)f[i]=i;

15     for(int i=1;i<=m;i++){

16         scanf("%d%d%s",&x,&y,s);

17         x-=y;

18         y=min(x+2*y,2*n-x-2*y+2);

19         x=max(x,-x);

20         if (s[0]=='x'){

21             add(2*y,2*x);

22             add(2*y+1,2*x+1);

23         }

24         else{

25             add(2*y+1,2*x);

26             add(2*x+1,2*y);

27         }

28     }

29     for(int i=0;i<=n+1;i++)

30         if (find(2*i)==find(2*i+1)){

31             printf("0");

32             return 0;

33         }

34     int s=0;

35     for(int i=0;i<=2*n+3;i++)s+=(find(i)==i);

36     s=s/2-2;

37     ans=1;

38     for(int i=1;i<=s;i++)ans=ans*2%1000000007;

39     printf("%d",ans);

40 }

巴特西

[cf461D]Appleman and Complicated Task

最新文章

热门文章