BZOJ 1008: [HNOI2008]越狱【组合】
2024-09-04 06:32:39
很少有的思路秒解。题意可以描述成对长度为n的格子有m种染色方案,问存在相邻两个格子同色的方案数,正难则反易,考虑问题的背面任意两个相邻的格子都不同色,第一个格子可以涂任意一种颜色m种可能,剩下的n-1个格子每个不能和前面一个格子相同固有m-1种可能,总的方案数有m^n种,所以答案就是m^n-m(m-1)^n-1 由于答案取模及幂次较高,因此可以考虑小费马定理或快速幂优化
由于数据太2,一开始用 int读成功贡献了3个WA TAT
#include<iostream>
#include<cstdio>
#include <math.h>
using namespace std;
long long ksm(long long k,long long a)
{
if(k==0)return 1;
if(k==1)return a;
if(k % 2 == 0)return ksm(k/2,a)*ksm(k/2,a) % 100003;
else return (ksm(k-1,a)*a) % 100003;
}
int main()
{
long long m=0,n=0,ans;
scanf("%lld%lld",&m,&n);
ans=(ksm(n,m)-(m*ksm(n-1,m-1))% 100003 +100003)%100003;
printf("%lld",ans);
return 0;
}
最新文章
- 高通平台FastMMI(FFBM模式)简介与进入方法
- uC/OS-II中includes块
- weka 文本分类(1)
- [Angular2 Form] Display Validation and Error Messaging in Angular 2
- 源码分析之struts1自定义方法的使用与执行过程
- 《C++ Primer Plus 6th》读书笔记 - 第十一章 使用类
- [置顶] hdu4747 Mex 线段树
- DELPHI 通過窗口句柄或窗口标题得到进程句柄
- TMG 2010 VPN配置
- mvc之验证IEnumerable<;T>; 类型,多选框验证
- vsphere client 虚拟机安装操系统
- 点击表格的单元格时实现变颜色,通过for循环为每个单元格添加一个onclick事件
- JavaScript定时器及相关面试题
- 【HTML5】HTML5新布局元素
- Ubuntu 安装MyEclipse10
- win10 如何关掉自带的杀毒软件 window defender
- 编辑器测试-TinyMCE
- crunch--字典生成工具
- python入门学习:4.if语句
- 性能调优9:根据WaitType诊断性能