首页 > 其他分享 >DTOJ-2022-11-10-测试-题解

DTOJ-2022-11-10-测试-题解

时间:2022-11-18 12:12:45浏览次数:89  
标签:11 10 int 题解 ll 路径 斯坦纳 ge

题目链接

A B C

A

这个套路已经出现了很多次了

就是两条线之间的网格图路径数,做法呢就是容斥

题意

求满足以下条件的 \(n\times m\) 的矩阵的个数对 \(10^9+7\) 取模

对于矩阵中的第 \(i\) 行第 \(j\) 列的元素 \(x_{i,j}\) 都有

  • \(x_{i,j}< x_{i,j+1}\)
  • \(x_{i,j}< x_{i-1,j+1}\)
  • \(0\le x_{i,j} \le m\)

题解

首先注意到每一行都有 \(m\) 个数,是单增的,而且每个数 \(\in [0,m]\)

这说明每一行一定是从 \(0,\dots,m\) 删去一个数

我们记 \(a_i\) 表示每一行删去的数

现在我们考虑 \(x_{i,j}< x_{i-1,j+1}\) 这个条件

画几张图就可以看出, \(x_{i,j}< x_{i-1,j+1} \Leftrightarrow a_{i+1}\ge a_i-1\)

也就是说,原问题被转换成了这样子:

有一个长度为 \(n\) 的序列 \(\{a_i\}\) ,求满足 \(a_i\in [0,m]\) 且 \(a_{i+1}\ge a_i-1\) 的序列数

如果把题目改成 \(a_{i+1}\ge a_i\),这个比较好做

这样一个 \(a_i\) 序列可以与一条从 \((1,0)\) 到 \((n+1,m)\) 的单调路径一一对应

(就直接让 \(a_i\) 取 \(1,\dots, n\) 处路径的最大值就好啦)

那么序列数就是 \(\displaystyle\binom{n+m}{m}\).

那我们来考虑原问题,原问题其实也可以转化为类似的问题

我们定义 \(b_i=a_i+i\) 这样是不是就是 \(b_{i+1}\ge {b_i}\)

但是这个时候, \(b_i \in [i,m+i]\)

也就是说,我们求的是 \((1,0)\) 到 \((n+1,n+m+1)\) 的路径数

而且路径不能越过 $y=x-1 $ 和 $ y=m$

转换到从原点开始,就是 $(0,0) \rightarrow (n,n+m+1) $ 的路径数

不能越过 \(y=x\) 和 \(y=m+1\)

然后呢,就是容斥,具体看这篇博客(!!还没补)

代码很好写

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e6+5, P = 1e9+7;
int n,m,fc[N],fci[N];
int ksm(int a, int b)
{
	int res=1;
	for(; b; b>>=1,a=(ll)a*a%P) if(b&1) res=(ll)a*res%P;
	return res;
}
int C(int x, int y)
{
	if(x<0 or y<0 or x<y) return 0;
	return (ll)fc[x]*fci[y]%P*fci[x-y]%P;
}
struct point { int x,y; }; //点
void refl(point &p, int b) { point q={p.y-b,p.x+b}; p=q; } //点沿着直线 y=x+b 反射

int main()
{
	fc[0]=1;
	for(int i=1; i<N; i++) fc[i]=(ll)fc[i-1]*i%P;
	fci[N-1]=ksm(fc[N-1],P-2);
	for(int i=N-1; i; i--) fci[i-1]=(ll)fci[i]*i%P;
	//for(int i=0; i<=10; i++) printf("%d %d\n",fc[i],fci[i]);
	scanf("%d%d",&n,&m);
	point p={n,n+m+1};
	ll res=C(p.x+p.y,p.x);
	point q=p;
	for(int i=-1; ; i=-i)
	{
		if(i<0) refl(q,-1); //y=x-1
		else refl(q,m+2); //y=m+2
		if(q.x<0 or q.y<0) break;
		res=(res+i*C(q.x+q.y,q.x)+P)%P; //容斥
	}
	q=p;
	for(int i=-1; ; i=-i)
	{
		if(i>0) refl(q,-1);
		else refl(q,m+2);
		if(q.x<0 or q.y<0) break;
		res=(res+i*C(q.x+q.y,q.x)+P)%P;
	}
	printf("%lld\n",res);
	return 0;
}

B

一道斯坦纳树的板子题

(为什么斯坦纳没有发起进攻,因为他去学信竞了\bushi)

斯坦纳树的学习笔记看这里(!!!还没补)

标签:11,10,int,题解,ll,路径,斯坦纳,ge
From: https://www.cnblogs.com/copper-carbonate/p/16902763.html

相关文章

  • 2022-11-17 纳斯达克指数,5分钟三段式上涨回补跳空缺口。
    30分钟中枢下  5分钟三段式上涨,回补向下跳空缺口 ......
  • 【转载】Oracle11gR2 RAC primary+Single standby DG配置实践
    很久之前做的实验,今天在CSDN存档一下:说明:RACprimary和Singlestandby配置2节点RAC和1个singleinstance组成的dataguard环境。 1.环境介绍Primarydatabase是一个......
  • win10安装cuda、cuDNN和pytorch笔记
    特别注意:由于自己安装时没有做记录,所以下面大部分安装步骤图片都是参考的网络图,但不影响阅读,每一步都讲得很详细1.安装CUDA1.1查看自己显卡最高支持的CUDA版本在桌面......
  • 2022-11-17 纳斯达克指数,1分钟级别笔的开始结束
    所有的结构都是从1分钟发出来的。如何判定1分钟笔的结束,掌握之后,也可以用于判定5分钟级别甚至日线级别笔的结束。日线:已经有顶分型30分钟:中枢形成5分钟:处于中枢中1分钟......
  • win11不更新系统设置教程
    https://pcedu.pconline.com.cn/1501/15015038.html有用户不想更新自己的win11系统,但是不知道win11不更新系统如何设置,其实我们可以通过服务或者组策略来关闭更新。方法......
  • win10安装LLVM
    1、缺少fastBPE在https://github.com/glample/fastBPE下载并拷贝到文件夹下2、安装libclangwin10下安装llvm和clang前提条件:Windows10环境下VS2015已安装,WindowsSDK已......
  • MBR10200FAC-ASEMI塑封肖特基二极管MBR10200FAC
    编辑:llMBR10200FAC-ASEMI塑封肖特基二极管MBR10200FAC型号:MBR10200FAC品牌:ASEMI封装:ITO-220AC特性:肖特基二极管正向电流:10A反向耐压:200V恢复时间:5ns引脚数量:2芯片个数:1芯片......
  • MBR10200FAC-ASEMI塑封肖特基二极管MBR10200FAC
    编辑:llMBR10200FAC-ASEMI塑封肖特基二极管MBR10200FAC型号:MBR10200FAC品牌:ASEMI封装:ITO-220AC特性:肖特基二极管正向电流:10A反向耐压:200V恢复时间:5ns引脚数量:2芯......
  • Debian 11上安装MongoDB 5
    关闭numa和transparent_hugepage$sudovi/etc/default/grub添加GRUB_CMDLINE_LINUX_DEFAULT="quietinuma=offtransparent_hugepage=never"$sudogrub-mkconfig......
  • Java新特性(2):Java 10以后
    您好,我是湘王,这是我的博客园,欢迎您来,欢迎您再来~ 虽然到目前为止Java的版本更新还没有什么惊天动地的改变,但总是会冒出一些有趣的小玩意。前面列举了Java9和Java10的一些......