Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:请教：这题要是改成旋转后相同不重复计算，该怎么做呢？？

Posted by blackRats at 2013-11-07 00:36:20 on Problem 2411
In Reply To:请教：这题要是改成旋转后相同不重复计算，该怎么做呢？？ Posted by:richardxx at 2007-09-17 21:44:09
```中间对称优化下……即算n/2行即可。
100MS内，状态压缩DP

#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;

#define LL long long
LL dp[12][1<<11];
int n,m;

bool ok(int a,int b)
{
if(a&b) return false;
a|=b;

bool two=false;
int t=m;
while(t--)
{
if(!(a&1))
{
if(two)
two=false;
else
two=true;
}
else if(two)
return false;
a>>=1;
}
if(two) return false;
return true;
}

int main()
{
while(scanf("%d%d",&n,&m),n||m)
{
if( n%2 && m%2 ) { puts("0"); continue; }

memset(dp,0,sizeof(dp));
dp[0][0]=1;

int total=1<<m;
int a=n/2,b=(n-1)/2;
for(int i=1;i<=a;i++)
for(int j=0;j<total;j++) if(dp[i-1][j])
for(int k=0;k<total;k++) if(ok(k,j))
dp[i][k]+=dp[i-1][j];

LL ans=0;
for(int j=0;j<total;j++) if(dp[a][j])
for(int k=0;k<total;k++) if(ok(k,j))
ans+=dp[a][j]*dp[b][k];
printf("%I64d\n",ans);
}
}```

Followed by: