2014
04-04

# A Very Simple Problem

This is a very simple problem. Given three integers N, x, and M, your task is to calculate out the following value:

There are several test cases. For each case, there is a line with three integers N, x, and M, where 1 ≤ N, M ≤ 2*109, and 1 ≤ x ≤ 50.
The input ends up with three negative numbers, which should not be processed as a case.

There are several test cases. For each case, there is a line with three integers N, x, and M, where 1 ≤ N, M ≤ 2*109, and 1 ≤ x ≤ 50.
The input ends up with three negative numbers, which should not be processed as a case.

100 1 10000
3 4 1000
-1 -1 -1

5050
444

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define N 60
#define ll long long
using namespace std;
ll a[N][N];
ll b[N][N];
ll c[N][N];
ll tp[N][N];
//void print(ll pt[N][N],int nb){
//    for (int i=0;i<=nb+1;i++){
//        for (int j=0;j<=nb+1;j++)
//            printf("%I64d ",pt[i][j]);
//        printf("\n");
//    }
//}
int main(){
int n,x;
ll MOD;
while (scanf("%d%d",&n,&x)==2){
cin>>MOD;
if (n<0&&x<0&&MOD<0) break;
for (int i=0;i<=x;i++)
c[i][i]=c[i][0]=1ll;
for (int i=2;i<=x;i++)
for (int j=1;j<i;j++)
c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for (int i=0;i<=x;i++)
for (int j=0;j<=i;j++)
a[j][i]=c[i][j]*x%MOD;
for (int i=0;i<=x;i++)
a[i][x+1]=a[i][x];
a[x+1][x+1]=1ll;
for (int i=0;i<=x+1;i++)
b[0][i]=x;
n=n-1;
while (n>0){
if (n%2){
memset(tp,0,sizeof(tp));
for (int i=0;i<=x+1;i++)
for (int j=0;j<=x+1;j++)
for (int k=0;k<=x+1;k++)
tp[i][j]=(tp[i][j]+b[i][k]*a[k][j])%MOD;
memcpy(b,tp,sizeof(tp));
}
n=n/2;
memset(tp,0,sizeof(tp));
for (int i=0;i<=x+1;i++)
for (int j=0;j<=x+1;j++)
for (int k=0;k<=x+1;k++)
tp[i][j]=(tp[i][j]+a[i][k]*a[k][j])%MOD;
memcpy(a,tp,sizeof(tp));
}
cout<<b[0][x+1]<<endl;
}
return 0;
}


1. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

2. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？