2722 - 二货分西瓜
时间限制 : 2 秒
内存限制 : 128 MB
n(2<=n<=10^6)个二货围成一个圈分西瓜，并且这群二货都特别喜欢自己是独特的，所以他们都需要他们的西瓜跟他们所能看到的人是不同的，但是呢，因为是二货，所以只能看到自己旁边两人。 现在让你来发西瓜，西瓜的大小有m(1<=m<=10^6)种，请问有多少种分法。
题目输入
多组输入，每组输入一个n和m。
题目输出
每组输出一个数表示有多少种分发，因为数字可能过大所以对11080302取余
输入/输出样例
输入格式
4 3
输出格式
18
C语言解答
#include <stdio.h> #include <string.h> const long long mod=11080302; long long a[1000005]; int main() { long long n,m; while(scanf("%lld%lld",&n,&m)!=EOF) { a[0]=0; a[1]=m-1; for(int i=2;i<n;i++) a[i]=((m-1)*a[i-2]+(m-2)*a[i-1])%mod; printf("%lld\n",m*a[n-1]%mod); } return 0; }
C++解答
#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #define mod 11080302 using namespace std; long long a[1000005]; int main() { //freopen("E input.txt","r",stdin); //freopen("E output.txt","w",stdout); long long n,m; while(cin>>n>>m) { a[1]=0; a[2]=(m%mod)*((m-1)%mod)%mod; for(int i=3;i<=n;i++) { a[i]=(m-2)*a[i-1]+(m-1)*a[i-2]; a[i]%=mod; } cout<<a[n]<<endl; } }