940 C. How Does the Rook Move?(dp)

简介: 940 C. How Does the Rook Move?(dp)

Problem - C - Codeforces

参考一下题解,我们先将已经固定的棋子查找出来,并且计数,从而求出我们需要放的自由棋子的数量,这样我们就我们不必考虑黑白棋子的位置,我们只考虑我们可以自由摆放的棋子的个数,每当增加新的一行和一列的时候我们能需要考虑两种情况

1.我们可以在新的增加的一行一列中的中剪,也就是i,i 位置添加一种棋子,这是dp[i-1]

2.也可以在i,j位置添加一种棋子,这样需要占用两行两列,并且有i-1种位置可以添加,并且是黑白2种棋子,这是2*(i-1)*dp[i-2]

#include<iostream>
#include<algorithm>
#include<cstring>
 
using namespace std ;
const int N = 3e5+10 ,M = 1e9 + 7 ;
 
int dp[N]  ;
int t , n , q ;
 
int main(){
  cin >> t ;
  while(t  --){
    memset(dp,0,sizeof(dp)) ;//每一次进行清零 
    cin >> n >> q ;
    int ans = 0 ;
    while(q --){
      int x , y ;
      cin >> x >> y ;
      ans += (2 - (x==y)) ;//记录我们已经用过的行和列 
    }
    dp[0] = 1 ; //初始化,当没有空余的行和列的时候我们只能等于本来的已经固定的棋子方案书
    //dp[1] = 1 ; //当只有一行一列的时候我们只能添加  i,i  这种方式  
    int m = n - ans ;
    for(int i = 2 ; i <= m ; i++){
      dp[i] =(dp[i-1] % M + ((long long)2*(i-1)*dp[i-2]) % M) %M ;
    }
    cout << dp[m] << endl ;
  }
  return 0 ;
} 
目录
相关文章
|
16天前
|
缓存 容器 Perl
【Azure Container App】Container Apps 设置延迟删除 (terminationGracePeriodSeconds) 的解释
terminationGracePeriodSeconds : 这个参数的定义是从pod收到terminated signal到最终shutdown的最大时间,这段时间是给pod中的application 缓冲时间用来处理链接关闭,应用清理缓存的;并不是从idel 到 pod被shutdown之间的时间;且是最大时间,意味着如果application 已经gracefully shutdown,POD可能被提前terminated.
|
4月前
|
存储 Kubernetes 调度
在K8S中,⼀个pod的不同container能够分开被调动到不同的节点上吗?
在K8S中,⼀个pod的不同container能够分开被调动到不同的节点上吗?
|
7月前
|
Python
GEE—关于RSEI生态遥感指数中出现的问题 Layer error: Image.rename: The number of names (1) must match the number of..
GEE—关于RSEI生态遥感指数中出现的问题 Layer error: Image.rename: The number of names (1) must match the number of..
209 0
135Echarts - 路径图(Use lines to draw 1 million ny streets.)
135Echarts - 路径图(Use lines to draw 1 million ny streets.)
37 0
LeetCode Contest 178-1368. 使网格图至少有一条有效路径的最小代价 Minimum Cost to Make at Least One Valid Path in a Grid
LeetCode Contest 178-1368. 使网格图至少有一条有效路径的最小代价 Minimum Cost to Make at Least One Valid Path in a Grid
2019EC Final E-Flow(贪心 dfs)
2019EC Final E-Flow(贪心 dfs)
98 0
|
数据库 容器
SAP QM 检验批上的‘容器数’
SAP QM 检验批上的‘容器数’
SAP QM 检验批上的‘容器数’
|
网络协议 Unix 网络安全