Codeforces 1342 E Placing Rooks —— 第二类斯特林数

This way

题意:

现在有一个n*n的棋盘,n个棋子,你要放置这些棋子使得他们满足以下条件:
每个格子都能被某个棋子打到
共有k对棋子能够打到对方
如果一个格子所处的这一行或这一列有一个棋子,那么这个格子就能被打到。两个棋子处在同一行或同一列并且它们之间没有别的棋子,这两个棋子被视为可以能够打到对方。

题解:

这个就是第二类斯特林数的模板题,

第一类斯特林数:

你有n个不同棋子,要让他构成m个环,有多少种组成方法
环是有序的,你每次要么让一个棋子自成一格环,要么让它加入某个棋子的左边,于是
可以写出这样的方程:

dp[i][j]=dp[i-1][j-1]+dp[i-1][j-1]*i

第二类斯特林数:

你有n个不同的棋子,要将他们分成m个集合,有多少种组成方法
集合是无序的,它的方程式是这样的:
S(n,m)=1m!i=0m(1)iCmi(mi)nS(n,m)=\frac{1}{m!}\sum_{i=0}^{m}(-1)^i*C_{m}^{i}*(m-i)^n
那么这道题,首先要么每行都有一个棋子,要么每列都有一个棋子,行和列的考虑是相同的,所以最后*2即可。
由于有k对棋子可以打到对方,所以有n-k列含有1个或多个棋子,剩下的列一个棋子都没有。所以这里的情况数是CnnkC_{n}^{n-k}
然后就是S(n,nk)S(n,n-k)
由于所有棋子的行是不一样的,所以n-k列是一个排列数:(nk)!(n-k)!
最后的答案就是CnnkS(n,nk)(nk)!C_{n}^{n-k}*S(n,n-k)*(n-k)!
=>Cnnki=0nk(1)iCnki(nki)n=>C_{n}^{n-k}*\sum_{i=0}^{n-k}(-1)^i*C_{n-k}^{i}*(n-k-i)^n

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+5;
const ll mod=998244353;
ll fac[N],inv[N],p[N];
ll qpow(ll a,ll b){ll ans=1;for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;return ans;}
ll c(ll n,ll m){
    if(m==0||m==n)return 1;
    if(m>n||m<0)return 0;
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    fac[0]=p[0]=1;
    if(k>n-1)
        return 0*printf("0\n");
    for(ll i=1;i<=n;i++)
        fac[i]=fac[i-1]*i%mod;
    inv[n]=qpow(fac[n],mod-2);
    for(ll i=n-1;i;i--)
        inv[i]=inv[i+1]*(i+1)%mod;
    ll ans=0,f=1;
    for(int i=0;i<=n-k;i++)
        ans=(ans+f*c(n-k,i)*qpow(n-k-i,n)%mod+mod)%mod,f*=-1;
    (ans*=c(n,n-k))%=mod;
    if(k!=0)ans=ans*2%mod;
    printf("%lld\n",ans);
    return 0;
}

热门文章

暂无图片
编程学习 ·

安卓安全那点事

本文旨在对于一个安卓app的安全知识做一个较为泛泛的总结,为开发出更安全的应用提供思路。内容比较粗略,仅起到抛砖引玉的效果,还望大家见谅。Android应用的安全 意义 在维基百科上有一个关于计算机安全的定义: 计算机安全(computer security)是计算机与网络领域的信息安…
暂无图片
编程学习 ·

人脸活体离线识别摇头点头张嘴眨眼动作活体算法源码解析

活体识别要求最近我们公司的项目需要做一个活体识别的功能,要求如下: 1.离线识别,本地识别活体,这样速度快1s内完成。需要识别出人脸,并判断是否在摇头 ,点头,张嘴,眨眼等动作,进而判断是否活体,准确率要求90%即可,可以去破解相信没有任何一个项目能完全规避的,哪怕…
暂无图片
编程学习 ·

IDEA 新建spring boot项目 提示cannot resolve springbootapplication

想写一个spring boot的demo试试,建完项目之后总提示cannot resolve springbootapplication我一脸懵圈啊,idea是我刚下载的,而且是按照网上说的步骤新建的项目,啥都没改,所有文件不都是自动生成的吗第一反应是这是什么辣鸡软件网上试了很多方法,什么下jar包改maven配置的我…
暂无图片
编程学习 ·

nginx 通过域名代理tcp端口

碰到一种场景,使用nginx进行反向代理tcp端口,网上大部门的设置都是一个端口代理一个端口,没有一个端口通过域名代理后端多个端口的情况。 在sf上面看到一个设置教程,记录下 只需要修改nginx.conf,添加如下配置即可, stream {map $ssl_preread_server_name $name {mysql.t…
暂无图片
郑州普通话 ·

学习笔记六——循环神经网络

一、RNN 前馈神经网络&#xff1a;信息往一个方向流动。包括MLP和CNN 循环神经网络&#xff1a;信息循环流动&#xff0c;网络隐含层输出又作为自身输入&#xff0c;包括RNN、LSTM、GAN等。 RNN模型结构如下图所示&#xff1a; 展开之后相当于堆叠多个共享隐含层参数的前馈…
暂无图片
代理记账 ·

学习笔记六——循环神经网络

一、RNN 前馈神经网络&#xff1a;信息往一个方向流动。包括MLP和CNN 循环神经网络&#xff1a;信息循环流动&#xff0c;网络隐含层输出又作为自身输入&#xff0c;包括RNN、LSTM、GAN等。 RNN模型结构如下图所示&#xff1a; 展开之后相当于堆叠多个共享隐含层参数的前馈…
暂无图片
cgfy ·

学习笔记六——循环神经网络

一、RNN 前馈神经网络&#xff1a;信息往一个方向流动。包括MLP和CNN 循环神经网络&#xff1a;信息循环流动&#xff0c;网络隐含层输出又作为自身输入&#xff0c;包括RNN、LSTM、GAN等。 RNN模型结构如下图所示&#xff1a; 展开之后相当于堆叠多个共享隐含层参数的前馈…
暂无图片
coreui ·

Heap Sort 讲解

Heap Sort sorts a group of unordered elements using the Heap data structure. The sorting algorithm using a Min Heap is as follows: Heapify all elements into a Min HeapRecord and delete the top elementPut to top element into an array T that stores all so
暂无图片
未来博客 ·

Heap Sort 讲解

Heap Sort sorts a group of unordered elements using the Heap data structure. The sorting algorithm using a Min Heap is as follows: Heapify all elements into a Min HeapRecord and delete the top elementPut to top element into an array T that stores all so
暂无图片
建站日记 ·

[react] 你觉得react上手快不快?它有哪些限制?

[react] 你觉得react上手快不快&#xff1f;它有哪些限制&#xff1f; 相对vue来说不快。 限制 需要学习JSX需要工程化的配置需要对原生JavaScript有相当的掌握react只是一个UI层面的库&#xff0c;像vue内置了动画处理、keep-alive等功能&#xff0c;react则需要去找第三方库…
暂无图片
mfbz ·

学习笔记六——循环神经网络

一、RNN 前馈神经网络&#xff1a;信息往一个方向流动。包括MLP和CNN 循环神经网络&#xff1a;信息循环流动&#xff0c;网络隐含层输出又作为自身输入&#xff0c;包括RNN、LSTM、GAN等。 RNN模型结构如下图所示&#xff1a; 展开之后相当于堆叠多个共享隐含层参数的前馈…
暂无图片
mfbz ·

AOV网是否存在回路-拓扑排序-C++

拓扑排序是对测试AOV网是否存在回路的方法&#xff01; 拓扑排序的过程中&#xff0c;由于需要查找所有以某顶点为尾的弧&#xff0c;即找到该顶点的所有出边&#xff0c;故图要采用邻接表的存储方式。但拓扑排序较邻接表的存储方式有一点不同&#xff0c;由于要查找入度为0的点…
暂无图片
珊珊日记 ·

学习笔记六——循环神经网络

一、RNN 前馈神经网络&#xff1a;信息往一个方向流动。包括MLP和CNN 循环神经网络&#xff1a;信息循环流动&#xff0c;网络隐含层输出又作为自身输入&#xff0c;包括RNN、LSTM、GAN等。 RNN模型结构如下图所示&#xff1a; 展开之后相当于堆叠多个共享隐含层参数的前馈…
暂无图片
珊珊日记 ·

AOV网是否存在回路-拓扑排序-C++

拓扑排序是对测试AOV网是否存在回路的方法&#xff01; 拓扑排序的过程中&#xff0c;由于需要查找所有以某顶点为尾的弧&#xff0c;即找到该顶点的所有出边&#xff0c;故图要采用邻接表的存储方式。但拓扑排序较邻接表的存储方式有一点不同&#xff0c;由于要查找入度为0的点…