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;
}

热门文章

暂无图片
编程学习 ·

Shell编程_echo/printf

目录一、Shell echo/printf 命令1、Shell显示命令-echo2、printf 命令操作常用的一些格式化字符二、test命令一、Shell echo/printf 命令Shell echo/printf 命令1、Shell显示命令-echo打印普通字符串[root@master ~]# echo "hello shell" hello shell创建和清空文件1…
暂无图片
编程学习 ·

C++核心准则ES.40:避免复杂的表达式

ES.40: Avoid complicated expressionsES.40:避免复杂的表达式Reason(原因)Complicated expressions are error-prone.复杂的表达式容易引发错误。Example(示例)// bad: assignment hidden in subexpression while ((c = getc()) != -1)// bad: two non-local variables as…
暂无图片
编程学习 ·

二、21【设计模式】之状态模式

今天的博客主题设计模式 ——》 设计模式之状态模式状态模式 SP (State Pattern)定义允许对象在内部状态发生改变时改变它的行为,看起来好像修改了它的类。类的行为是由状态决定的,不同的状态下该类有不同的行为。就是一个对象在其内部改变的时候,它的行为也随之改变。核心…
暂无图片
编程学习 ·

leetcode718. 最长重复子数组/动态规划,滑动窗口

文章目录题目:leetcode718. 最长重复子数组/动态规划基本思想1:动态规划基本思想2:滑动窗口基本思想3:暴力 题目:leetcode718. 最长重复子数组/动态规划 给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。 示例 1: 输入: A: [1,2,3,2,1] B: [3,2,1…
暂无图片
编程学习 ·

Day 11 武装飞船

《外星人入侵》游戏要实现的是:玩家控制一艘出现在屏幕底部中央的飞船,可以使用箭头左右移动飞船,还可以使用空格来进行射击,游戏开始时候一群外星人出现在天空,他们在屏幕中向下移动,玩家的任务是射杀这些外星人,玩家将所有外星人都消灭干净后,会出现一群新的外星人,…
暂无图片
编程学习 ·

后台开发核心技术(11):多线程

背景介绍 进程:以前,进程是最小的执行单位。进程是包含程序指令和相关资源的集合,每个进程和其他进程一起参与调度,竞争CPU、内存等资源。每次进程的切换,都存在着进程资源的保存和恢复动作,这称为上下文切换。 发现问题:比如一个简单的GUI程序,为了有更好的交互性,通…
暂无图片
编程学习 ·

IDEA常用快捷键或修改为Eclipse快捷键风格

Ctrl + Y 删除当前行 Ctrl + D 复制当前行到下一行 Ctrl + Z 撤销 Alt+Enter 导入包,自动修正 Ctrl+F 查找文本 Ctrl+U 大小写切换 Ctrl+W 选中代码,连续按会扩大范围 Ctrl+R 替换文本快捷键改为eclipse快捷键风格Ctrl+Alt+S 或者打开File选择Settings这就完成了
暂无图片
编程学习 ·

大数据分析的作用有哪些

大数据分析的出现不但可以让老百姓的生活更加便捷,同时也可以提高企业的竞争力,无论是哪个行业以及具体的企业都会有与之对应的大数据分析,而今天就来说说大数据分析对于企业有哪些帮助。数据分析目的1:分类检查未知分类或暂时未知分类的数据,目的是预测数据属于哪个类别或…
暂无图片
编程学习 ·

带你全面了解蓝牙定位原理,蓝牙定位方案种类-新导智能

蓝牙定位服务是蓝牙技能领域增加最快的解决方案,现在已经被越来越多的运用于寻物、室内定位、室内导航以及财物追寻等领域。蓝牙联盟也在不断的迭代蓝牙技能,使得定位技能的精度越来越高,从最早的朴实基于信号强度的Beacon定位,到蓝牙5.1支撑的多天线视点定位等。从方案视点…
暂无图片
编程学习 ·

防火墙部署,功能及数据包分析。

防火墙部署方式的应用路由模式虚拟线模式部署透明模式(交换模式)访问控制和地天融信防火墙抓包 路由模式 防火墙的路由模式,主要是用于网络的出口位置,也就是防火墙的设备有一个网口配置公网地址。多出口加上多入口,有时也叫上下联(上联口向外网方向,下联口向内网方向)…
暂无图片
编程学习 ·

redis 缓存击穿,穿透,雪崩及解决方案

一、前言在我们日常的开发中,无不都是使用数据库来进行数据的存储,由于一般的系统任务中通常不会存在高并发的情况,所以这样看起来并没有什么问题,可是一旦涉及大数据量的需求,比如一些商品抢购的情景,或者是主页访问量瞬间较大的时候,单一使用数据库来保存数据的系统会…
暂无图片
编程学习 ·

小甲鱼python听课笔记p11-p15

p11 7.1 列表1 = 打了激素的数组列表可以存放不同类型的数,还可以创建空列表append():向列表里面添加数据末尾添加一个元素但是只能一次插入一个数据extend():扩张的方式来扩展列表末尾添加多个元素,但要求已列表的格式添加[x,x,x,x]用一个列表来扩展另一个列表,所以他…
暂无图片
编程学习 ·

随笔 弹窗 二维码生成及图片下载

一、qrcode-vue模块该模块是用来动态生成二维码的vue模块插件,<qrcode-vue></qrcode-vue>的底层其实是一个<canvas></canvas>标签。要想使用qrcode.vue插件,需要用vue的脚手架安装这个插件安装指令npm install qrcode --save-dev,在这里我举一个例子…
暂无图片
编程学习 ·

设计模式一——创建型模式(笔记)

简要描述 这些设计模式提供了一种方式:在创建对象的时候隐藏创建逻辑。(不是使用new运算符直接实例化对象) 带来的效果:使得程序在判断针对某个给定实例需要创建哪些对象时更加灵活。 包括:工厂模式,抽象工厂模式,单例模式,建造者模式,原型模式。 设计模式的六大原则:…
暂无图片
编程学习 ·

php 一句话木马简介

一句话木马就是一段简单的代码,就这短短的一行代码,就能做到和大马相当的功能。一句话木马短小精悍,而且功能强大,隐蔽性非常好,在入侵中始终扮演着强大的作用。一句话木马工作原理<?php @eval($_POST[shell]);?> 这是php的一句话后门中最普遍的一种。它的工作原理…
暂无图片
编程学习 ·

jdk源码解析二之HashMap

这里写自定义目录标题HashMapputremovereplaceget扩容resize迭代器总结什么时候采用红黑树?为什么每次扩容后,是2的幂次方?为什么扩容后,相同的在原位置保存,而不同的则当前索引+之前原位置索引保存?为啥用尾插法?为什么线程不安全? HashMap HashMap的loadFactor为什么是0…
暂无图片
编程学习 ·

Java NIO(Netty,Redis,Zookeeper高并发实战整理)

Java NIO NIO与OIO的对比 1.OIO事面向流的,NIO是面向缓冲区的。OIO是面向字节流或字符流的,在一般的OIO操作中,一流式的方法顺序地从一个流中读取一个或多个字节,因此,不能随意地改变读取指针的位置。NIO中引入了Channel(通道)和Buffer(缓冲区)的概念。读取和写入,只需…
暂无图片
编程学习 ·

pandas下-综合练习

综合练习端午节的淘宝粽子交易 端午节的淘宝粽子交易 (1) 请删除最后一列为缺失值的行,并求所有在杭州发货的商品单价均值。 df=pd.read_csv(F:\Datewheel资料\pandas组队学习\Pandas(下)综合练习数据集\端午粽子数据.csv) df.head()df.info()#查看列名 df.columns()注意列名…
暂无图片
编程学习 ·

String常用API

这里写目录标题什么是JDK API文档注释规范字符串String以及常用的APIString常量池String常用APIStringBuilderStringBuffer 什么是JDK APIJDK中包含大量打API类库,所谓API(Application Programming Interface,应用程序编程接口)就是一些已写好.可供直接调用的功能(在Java语言中…