1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>

using namespace std;

int k[50];

int main()
{
    int n,m;
    long long t=1,w=0,dw,p;
    cin>>n>>m>>p;
    for(int i=0; i<n; i++){
        t*=m;
    }
    if(n==1){
        cout<<m*(m-1)/2;
        return 0;
    }
    for(int i=0; i<t; i++){
        dw=min(k[0]+1,k[1]+1)*min(k[n-1]+1,k[n-2]+1);
        dw%=p;
        for(int j=1; j<n-1; j++){
            dw*=min(min(k[j-1]+1,k[j]+1),k[j+1]+1);
            dw%=p;
        }
        w+=dw;
        w%=p;
        for(int i=0; i<n; i++){
            k[i]++;
            if(k[i]==m){
                k[i]=0;
            }else{
                break;
            }
        }
    }
    cout<<w;
}