《深入浅出进阶篇》洛谷P3197 越狱——集合

2023-12-09 23:53

本文主要是介绍《深入浅出进阶篇》洛谷P3197 越狱——集合,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 洛谷P3197 越狱

题目大意:

监狱有 n 个房间,每个房间关押一个犯人,有 m 种宗教,每个犯人会信仰其中一种。如果相邻房间的犯人的宗教相同,就可能发生越狱,求有多少种状态可能发生越狱。

答案对100,003 取模。

对于 100% 的数据,保证1≤m≤10^8,1≤n≤10^12。

 学啥用啥!!!

要求有多少种状态可能发生越狱,我们可以求所有的安排牢房的状态 ,也就是全集。

 然后再算出所有的不会越狱的状态,也就是集合A。

用全集减去集合A,得到补集,这就是答案。

全集如何求?   

由乘法原理可知,每个牢房都可以安排m种宗教,也就是有m种选择,一共有n个牢房,那么全集就是:m^{n}

接下来我们要求,所有不会越狱的状况,集合A。

也就是要使得每个相邻的房间宗教不同。

第一个房间的选择有m种,第二个房间的选择只要满足不和前面的房间相同即可,m-1种

第三个房间只要满足与第二个房间不同,也就是m-1种。

这样下来,每个房间都与自己前一个房间的宗教不同,从而使得每个相邻的房间宗教不同。

答案就是  m \cdot (m-1)^{n-1}

所以最终答案就是      m^{n}-m \cdot (m-1)^{n-1}  mod ( 100003 )

用快速幂即可

(千万记住先输入m再输入n,我被这个卡了好久!!!!)

然后别忘了特判   

m^{n}-m \cdot (m-1)^{n-1} 快速幂之和可能会小于0,再加上100003即可

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<cctype>
#include<map>
#include<set>
#include<queue>
#include<numeric>
#include<iomanip>
using namespace std;
const long long MOD = 100003;
typedef long long ll;
ll qpow(ll m, ll n) {ll s = 1;while (n) {if (n & 1)s = s * m % MOD;m = m * m % MOD;n >>= 1;}return s;
}
ll n, m,ans,cns,bns;int main() {cin >> m >> n;ans = qpow(m, n);bns = (m * qpow(m - 1, n - 1))%MOD;cns = (ans - bns)%MOD;if (cns < 0)cns += MOD;cout << cns;
}

这篇关于《深入浅出进阶篇》洛谷P3197 越狱——集合的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/475461

相关文章

Python容器类型之列表/字典/元组/集合方式

《Python容器类型之列表/字典/元组/集合方式》:本文主要介绍Python容器类型之列表/字典/元组/集合方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 列表(List) - 有序可变序列1.1 基本特性1.2 核心操作1.3 应用场景2. 字典(D

Java集合中的List超详细讲解

《Java集合中的List超详细讲解》本文详细介绍了Java集合框架中的List接口,包括其在集合中的位置、继承体系、常用操作和代码示例,以及不同实现类(如ArrayList、LinkedList和V... 目录一,List的继承体系二,List的常用操作及代码示例1,创建List实例2,增加元素3,访问元

C#比较两个List集合内容是否相同的几种方法

《C#比较两个List集合内容是否相同的几种方法》本文详细介绍了在C#中比较两个List集合内容是否相同的方法,包括非自定义类和自定义类的元素比较,对于非自定义类,可以使用SequenceEqual、... 目录 一、非自定义类的元素比较1. 使用 SequenceEqual 方法(顺序和内容都相等)2.

基于Redis有序集合实现滑动窗口限流的步骤

《基于Redis有序集合实现滑动窗口限流的步骤》滑动窗口算法是一种基于时间窗口的限流算法,通过动态地滑动窗口,可以动态调整限流的速率,Redis有序集合可以用来实现滑动窗口限流,本文介绍基于Redis... 滑动窗口算法是一种基于时间窗口的限流算法,它将时间划分为若干个固定大小的窗口,每个窗口内记录了该时间

uva 11178 计算集合模板题

题意: 求三角形行三个角三等分点射线交出的内三角形坐标。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <

Java基础回顾系列-第六天-Java集合

Java基础回顾系列-第六天-Java集合 集合概述数组的弊端集合框架的优点Java集合关系图集合框架体系图java.util.Collection接口 List集合java.util.List接口java.util.ArrayListjava.util.LinkedListjava.util.Vector Set集合java.util.Set接口java.util.HashSetjava

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(

java集合的概述

集合就是一个容器,我们可以把多个对象放入的容器中。就像水杯(假设容量可以不断扩大)一样,你可以往水杯中不断地添加水,既然是水杯,你就不能往里添加沙子,也就是说集合中添加的对象必须是同一个类型的(引用类型,而不能是基本类型)。 看到集合的介绍会让我们的想起数组,那么集合和数组有什么区别呢? 首先,数组的大小是固定的,而集合理论上大小是不限的。 其次,数组既可以存储基本数据类型的数据,也可以存储

hutool 集合相关交集、差集

开发过程中会遇到集合之间的对比之类的需求,之前经常会自己写个工具类来实现,目前hutool可以帮助我们解决很多问题,接下来我们就来实践下。 相关jar包 <dependency><groupId>cn.hutool</groupId><artifactId>hutool-all</artifactId><version>RELEASE</version><scope>compile</sco

高精度计算(代码加解析,洛谷p1601,p1303)除法待更新

目录 高精度加法 高精度减法 高精度乘法 高精度加法 我们知道在c++语言中任何数据类型都有一定的表示范围。当两个被加数很大时,正常加法不能得到精确解。在小学,我们做加法都采用竖式方法。那么我们也只需要按照加法进位的方式就能得到最终解。 8 5 6+ 2 5 5-------1 1 1 1 加法进位: c[i] = a[i] + b[i];if(c[i] >=