BISHI69 [HNOI2008]越狱

这个问题可以通过计算“总方案数”减去“不越狱方案数”来得出结果。

总分配方案数：
每个房间有M MM种宗教选择，共有N NN个房间。
总数 =M × M × ⋯ × M = M N M \times M \times \dots \times M = M^NM×M×⋯×M=MN。

不越狱方案数:
第 1 个房间有M MM种选择；
第 2 个房间为了不与第 1 个重复，有M − 1 M-1M−1种选择；
第 3 个房间为了不与第 2 个重复，有M − 1 M-1M−1种选择；
以此类推，剩下的N − 1 N-1N−1个房间每个都有M − 1 M-1M−1种选择。
不越狱总数 =M × ( M − 1 ) N − 1 M \times (M-1)^{N-1}M×(M−1)N−1。

可能发生越狱的方案数：
越狱方案 = 总方案数 - 不越狱方案数
结果 =M N − M × ( M − 1 ) N − 1 M^N - M \times (M-1)^{N-1}MN−M×(M−1)N−1

流程图

代码实现

privatestaticfinallongMOD=100003L;publicstaticvoidmain(String[]args)throwsIOException{// 使用BufferedReader读取输入，PrintWriter输出结果BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));PrintWriterout=newPrintWriter(newOutputStreamWriter(System.out));String[]str=br.readLine().split("\\s+");longM=Long.parseLong(str[0]);longN=Long.parseLong(str[1]);longtotal=mypower(M,N,MOD);longsafe=M*mypower(M-1,N-1,MOD)%MOD;longans=(total-safe+MOD)%MOD;out.println(ans);out.flush();out.close();br.close();}privatestaticlongmypower(longbase,longexp,longmod){longans=1%mod;while(exp>0){if(exp%2==1){ans=(ans*base)%mod;}base=(base*base)%mod;exp/=2;}returnans;}