N久没做sgu了。。。
这道题意思是说给你一个n*m的棋盘每个数或为1或为0，每一个2*2的子矩阵的和都是2。。
求方法数。。
n和m那么大肯定是有公式的。。
先是写了状压DP算了一下。。看出公式是2^m+2^n-2。。
我是这么推导的。。
因为第一行有2^m种放法。。其中除了010101和101010之外。。
第一行一确定其他行也都确定了。。于是就有2^m-2种。。
又如果第一行是010101或101010。。那么第二行也只能选这两种。。
每一行都有两种选择。。于是就是2^n种。。
加一下就是答案了。。。
#include<iostream>
#include<cstring>
using namespace std;
const int maxl=1000;
struct bignum
{
int Q[maxl],last;
bignum()
{
memset(Q,0,sizeof(Q));last=0;
}
void set(int a)
{               
Q[last]=a;
}
int& operator[](int v){return Q[v];}
bignum operator+(bignum&x)
{
bignum ans;ans.last=max(last,x.last);int d=0;
for(int i=0;i<=ans.last;i++)
{
d+=x[i]+Q[i];
ans[i]=d%10;
d/=10;
}
if(d)ans[++ans.last]=d;
return ans;
}
void operator-=(int x)
{   
for(int i=0;i<=last;i++)
{
if(Q[i]>=x) {Q[i]-=x;return;}
else{Q[i]=10+Q[i]-x;x=1;}
}
}
bignum operator*(int x)
{
int d=0;bignum ans;ans.last=last;
for(int i=0;i<=ans.last;i++)
{
d+=Q[i]*x;
ans[i]=d%10;
d/=10;
}
while(d)
{
ans[++ans.last]=d%10;
d/=10;
}
return ans;
}
void operator=(const bignum&x)
{
memmove(Q,x.Q,sizeof(Q));
last=x.last;
}
void print()
{
for(int i=last;i>=0;i–)
cout<<Q[i];
}
}a,b;
int main()
{
int n,m;cin>>n>>m;
if(n<m){int t=n;n=m;m=t;}
b.set(1);
for(int i=1;i<=n;i++)
{
b=b*2;
if(i==m) a=b;
}
a=a+b;
a-=2;
a.print();cout<<endl;
}