https://codeforces.com/problemset/problem/1239/A
思路:
如果真在考场一时间自己又推不出来性质,打表找找规律
nm复杂度不能接受,那么如果结论的话应该到Log或者o1.
这个范围就猜一手横纵坐标独立。
先打表观察。
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=50;
typedef int LL;
inline LL read(){LL x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
LL a[maxn][maxn];
LL dx[4]={1,0,-1,0};
LL dy[4]={0,1,0,-1};
LL ans=0;
LL check(LL n,LL m){
for(LL i=1;i<=n;i++){
for(LL j=1;j<=m;j++){
LL t0=0;LL t1=0;
for(LL k=0;k<4;k++){
LL nx=i+dx[k];LL ny=j+dy[k];
if(nx<1||nx>n||ny<1||ny>m) continue;
if(a[nx][ny]==0) t0++;
if(a[nx][ny]==1) t1++;
}
if(a[i][j]==0&&t0>1) return 0;
if(a[i][j]==1&&t1>1) return 0;
}
}
return 1;
}
void dfs(LL x,LL y,LL n,LL m){
if(x==n+1){
ans+=check(n,m);
return;
}
for(LL i=0;i<=1;i++){
a[x][y]=i;
LL nx=x;LL ny=y;
if(ny==m){
dfs(nx+1,1,n,m);
}
else dfs(nx,ny+1,n,m);
}
}
int main(void)
{
///cin.tie(0);std::ios::sync_with_stdio(false);
for(LL i=1;i<=5;i++){
for(LL j=1;j<=5;j++){
ans=0;
memset(a,0,sizeof(a));
dfs(1,1,i,j);
cout<<ans<<"\n";
}
}
return 0;
}
/// 2 4 6 10 16
/// 4 6 8 12 18
/// 6 8 10 14 20
///10 12 14 18 24
///16 18 20 24 30
第一列满足一个广义斐波那契
然后每一行也遵守一个增量为2,2,4,6,10的广义斐波那契
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e5+1000;
typedef long long LL;
const LL mod=1e9+7;
inline LL read(){LL x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
LL dp[maxn];
LL row[maxn];
/// 2 4 6 10 16
/// 4 6 8 12 18
/// 6 8 10 14 20
///10 12 14 18 24
///16 18 20 24 30
int main(void)
{
cin.tie(0);std::ios::sync_with_stdio(false);
LL n,m;cin>>n>>m;
row[1]=2;row[2]=4;row[3]=6;
for(LL i=4;i<maxn;i++) row[i]=(row[i-1]%mod+row[i-2]%mod)%mod;
dp[1]=2;dp[2]=2;dp[3]=4;
for(LL i=4;i<maxn;i++) dp[i]=(dp[i-1]%mod+dp[i-2]%mod)%mod;
LL ans=row[n];
for(LL i=2;i<=m;i++){
ans=(ans%mod+dp[i-1]%mod)%mod;
}
cout<<ans%mod<<"\n";
return 0;
}