[HNOI2008] 越狱

news/2024/5/14 12:43:24/文章来源:https://blog.csdn.net/weixin_57427186/article/details/131562819

1.介绍

原题链接(回去补上,教练把锣鼓禁了qwq+谴责这种行为！！！)

一句话题意：房间1到房间n中，求存在相邻两个房间的宗教相同的可能性总和

就这？省选？哪个省的？湖南的？~~我想去~~

2.分析

稍稍有点思维能力的都没有问题吧······

(逆序思维)：求相同不太好求，求不同较为好求

∵相同的可能性+不同的可能性=总可能性

∴相同的可能性=总可能性-不同的可能性

问题来了

不同的怎么求？

假设我们先选1号房间

1号房间就有m种可能

然后选2号房间

就有 $m-1$ 种可能（去掉1号房间）

接着是3号

仍然是 $m-1$ 种（去掉2号房间，不去一号房间）

···

最后是n号房间

是m-1种(去掉n-1号房间)

∴不同的总数就是 m*(m-1)*(m-1)* ··· *(m-1) (共n-1个m-1)

即 $m*(n-1)^{m-1}$ (乘法原理)

而总和则是 $n^{m}$ (乘法原理)

相同的个数就是 $n^{m}-m*(n-1)^{m-1}$

如果你直接这么写，那恭喜你：你会WA

康康数据范围： $1\leqslant n\leqslant 10^{8}$ ， $1\leqslant m\leqslant 10^{12}$

标准快速幂呀！

(不会快速幂的请自查)

ll q(ll a,ll p)
{ll res=1;while(p){if(p&1) res=(res*a)%mod;p>>=1;a=(a*a)%mod;}return res;
}

所以总代码就是

3.总代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const int N=1e4+10,mod=1e5+3;
ll q(ll a,ll p)
{ll res=1;while(p){if(p&1) res=(res*a)%mod;p>>=1;a=(a*a)%mod;}return res;
}
long long n,m;int main()
{cin>>m>>n;m%=mod;ll ans;ans=(q(m,n)-m*q(m-1,n-1))%mod;cout<<((ans+mod)%mod);return 0;
}

（这么详细了，点个赞呗！）

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.luyixian.cn/news_show_326384.aspx

如若内容造成侵权/违法违规/事实不符，请联系dt猫网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！