BZOJ1008 (HNOI2008)[越狱]--组合数学_bzoj 1008_Greninja_Wu的博客-程序员秘密

技术标签： -------------数论--------------- BZOJ题解 By Greninja BZOJ题解 -------------题解--------------- 部分常见刷题网站的题解 By Greninja BZOJ 组合数学

【链接】
bzoj1008

【题目大意】
给你n和M，n表示房间的数量，每个房间有一个犯人，m表示宗教的数量，求相邻房间之间有犯人的宗教相同的方案数。

【解题报告】
因为题目中叫我们求相邻房间之间有犯人的宗教相同的方案数，但是这样思考比较复杂。所以可以逆向思考，求相邻房间之间有犯人的宗教相同的方案数不就是求总方案数减去相邻房间之间犯人的宗教都不相同的方案数吗，这样问题就变简单了。总方案数就是 $M^n$ ，相邻房间之间犯人的宗教都不相同的方案数也就是 $M\ast (M-1) ^ {n-1}$ （对于第一个犯人他可以信仰任意一个宗教也就是他可以信仰 $M$ 种宗教，而第二个犯人因为不能信仰与一相同的宗教，所以他可以信仰 $M-1$ 种宗教,其他人也和第二个一样只能信仰 $M-1$ 种宗教）。

#include<cstdio>
#define LL long long
using namespace std;
const int tt=100003;
int m;
LL n;
inline LL Read()
{
    LL res=0;
    char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9') res=res*10+ch-48,ch=getchar();
    return res;
}
LL Qsm(int a,LL b)
{
    LL w=a%tt,sum=1;
    while (b)
    {
        if (b&1) sum=sum*w%tt;
        w=(w*w)%tt; b>>=1;
    }
    return sum;
}
int main()
{
    freopen("1008.in","r",stdin);
    freopen("1008.out","w",stdout);
    m=Read(); n=Read();
    printf("%lld",(Qsm(m,n)-m%tt*Qsm(m-1,n-1)%tt+tt)%tt);
    return 0;
}

本文链接：https://blog.csdn.net/CHNWJD/article/details/74090363

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

SuperMap iClient3D for WebGL教程（空间分析）- 地表开挖及修改_supmap addmodifyregion修改地形_supermapsupport的博客-程序员秘密

地表开挖主要是为了显示出地下的场景，比如地下管网，而地形修改通常是为了让地表平整，便于跟模型匹配，接下来我们分别说说如何实现地表开挖和地形修改。地表开挖1.引用核心样式文件和库文件<script type="text/javascript" src="./js/require.min.js" data-main="js/main"></script><lin...

scikit-learn学习笔记（五）Logistic regression（逻辑回归）_Soyoger的博客-程序员秘密

逻辑函数(logistic function)为了更好地解释逻辑回归，让我们首先了解一下逻辑函数。逻辑函数由于它的S形，有时也被称为sigmoid函数。现在我要引入比值比（odds ratio）的概念，它可以被写成p(1−p)，其中的p代表正事件（positive event）的概率，正事件并不是代表好的方面的概率，而是代表我们想要预测的事件。比如：病人患有某种疾病的概率。我们把正事件

微信支付:请求参数与订单信息不一致_您的请求参数与订单信息不一致_xdRight的博客-程序员秘密

目录问题描述解决方案备注总结问题描述在小程序支付退款调用api(https://api.mch.weixin.qq.com/secapi/pay/refund)时出现您的请求参数与订单信息不一致的问题解决方案常见错误是total_fee、refund_fee金额设定错误，这两个参数单位为分，并且只能为整数，total_fee的值需与原始的订单支付的金额相对应，refund_fee的值不能超过可退款的余额appid 需与小程序id对应退款单out_refund_no不能重复商

路由器设置静态路由，动态获取局域网的IP_smartresister的博客-程序员秘密

背景：局域网中不允许有动态分配ip的路由，想用路由器吧一个网口扩展为多个网口，怎么办？方案：原理：把路由器当作集线器来用；步骤：1）将路由的动态分配ip的功能关掉；2）将路由器的广域网口用胶带封住不用，同时可防止其他人误用；3）将能介入局域网的网口查到任一路由器的局域网口；4）剩余的局域网网口就可以用来连接其它电脑，并能够动态分配到局域网的IP；...

YoloV3学习笔记（三）—— 训练_yolov3　requirement_聪 ~smart的博客-程序员秘密

YoloV3学习笔记（三）YoloV3学习笔记（三）—— 训练一、数据准备二、代码导入三、数据装载四、模型训练1、训练2、测试3、预测总结YoloV3学习笔记（三）—— 训练在经过环境配置和打标签之后，便开始进行我们最终的目标——训练数据集。一、数据准备以下给出了网上红细胞的数据集以及Yolov3的pytorch框架：链接:数据集框架二、代码导入1、将下载好的代码在pycharm中打开，如下图所示2、配置编译环境仅仅依靠我们第二节配置的环境来运行YoloV3是远远不够的，下载的文件夹

LuaLaTeX调用外部Lua程序与C语言编写的动态链接库_「已注销」的博客-程序员秘密

在LuaLaTeX编译方式下，虽然可以直接在tex文件中编写Lua代码，但会受到LaTeX的影响，编写中并不是很便利。所以我在实际使用中一般都把Lua代码的主体部分放在LaTeX的外部，这样可以完全按照以往的编程习惯去编写。我以前所在的公司，曾经在机器人运动控制系统中使用过Lua，但因为我没有负责那一部分，所以只是知道有Lua这么个脚本语言，并没有实际编写过。这几天才开始学习编写Lua代码，所...

随便推点

[转载][路由器] k2p支持ipv6相关设置_ipv6 k2p_Athrun.UW的博客-程序员秘密

设备简介：斐讯的k2p无魔改，只是刷了breed，刷了hankcwf的包，大家称之为padavan具体链接可以看这位大佬的github：https://github.com/hanwckf/rt-n56u开启ipv62.1 打开管理界面，高级设置，外部网络，ipv6按照如图所示设置；2.2 在脚本中添加以下几句命令，具体操作是打开自定义设置，脚本，在路由器启动后执行。modprobe ip6table_mangleebtables -t broute -A BROUTING -p !.

c练习3_明解c语言的练习3-5答案_hardrong的博客-程序员秘密

1.输出菱形#include &lt;stdio.h&gt; #include &lt;Windows.h&gt; int main() { int i = 0; int j = 0; int n = 0; for (i = 0; i &lt; 7; i++) { for (n = 0; n &lt; 6 - i; n...

Cannot resolve method 'makeText(anonymous android.view.View.OnClickListener, java.lang.String, int)_AndroidLiang1的博客-程序员秘密

原因是你传的上下文不正确，你是在内部类里弹吐司，上下文应该写activity.this或别的，如果仅仅是this那么代表的是当前的内部类