1957C - How Does the Rook Move?

本文主要是介绍1957C - How Does the Rook Move?，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：How Does the Rook Move?

如图：

因为每行每列都只能放一个棋子，因此我们用绿点来表示下的棋子，发现一个规律，当红色格子都被绿线划过时，那么就不能下棋子。当这个白色点放在x=y这个点，也就是横纵坐标相等时，红色这个点只占了一个，而当x！=  y时，占了两个红色格子，然后剩余我们可以填的就是剩下的蓝色格子，和两个红色格子没填，因此转化一下形成了右图。

再看如下图：

首先我们可以得知，每个棋子先下哪里后下哪里最后的结果不变，说的通俗一点，假设给你看别人刚下完的围棋，你知道白棋哪个位置是第一次下的吗？

因此最后的结果跟顺序无关，那么我们可以从最后一个点枚举，我们一次操作可以占一个红色格子，可以占两个红色格子，那么假设占一个格子，最后剩余的红点就是n-1，如果取两个格子，那么我们要从蓝色的区域里面取，也就是从( n - 1 )个格子里面选一个，又因为这是镜像的，所以我们可以选白棋也可以选黑棋，因此要×2.

所以最后的结论就是：
f(n)=f(n-1) + 2*(n-1)*f(n-2) 

代码附上：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N =3e5+5;
const int mod = 1e9+7;
int f[N];
int n,k;void solve(){cin>>n>>k;int m=n;for(int i=1;i<=k;i++){int x,y;cin>>x>>y;if(x==y)m-=1;else m-=2; }memset(f,0,sizeof(f));f[0]=f[1]=1;for(int i=2;i<=m;i++){f[i]=(f[i-1]+(2*(i-1)*f[i-2])%mod)%mod;}cout<<f[m]<<"\n";
}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t;cin>>t;while(t--){solve();}return 0;
}

这篇关于1957C - How Does the Rook Move?的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---