luogu P3197 [HNOI2008]越狱

构造长度为n的串，给定m种颜色，求使得相邻两位的颜色相同的方案数 显然可以看出长度为n的串染m种颜色的总方案数为$m^{n}$ 然后来考虑相邻两位颜色不同的方案

对于第一位，有m种选择

对于剩余的n-1位，有m-1种选择

所以相邻两位颜色不同的方案数就是 $m*(m-1)^{n-1}$ 最后就可以快乐的用快速幂求答案了

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; template<class T>void read(T &x){ int f=0;x=0;char ch=getchar(); while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x=f?-x:x; } typedef long long ll; const int mod=100003; ll n,m; inline ll ksm(ll a,ll b){ ll base=a%mod,ans=1ll; while(b){ if(b&1) ans=(ans*base)%mod; base=(base*base)%mod; b>>=1; } return ans; } int main(){ read(m),read(n); printf("%lld\n",(ksm(m,n)-m*ksm(m-1,n-1)%mod+mod)%mod); return 0; }

转载于:https://www.cnblogs.com/Peper/p/9954055.html

相关资源：各显卡算力对照表！