1122 - Digit Count(LightOJ)

#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int,int> pii;
typedef vector< pii > vii;

#define ll          long long
#define ff          first
#define ss          second
#define pb          push_back
#define mkp         make_pair
#define sz          size()

#define forf(a,b,c)    for(int i=a;i<=b;i+=c)
#define forr(a,b,c)    for(int i=a;i>=b;i-=c)
#define all(a)      a.begin(),a.end()
#define mem(a,b)    memset(a,b,sizeof(a))
#define pi          2*acos(0.0)
#define End         return 0;
#define nl endl

#define scan1(a)    scanf("%d",&a)
#define scan2(a,b)  scanf("%d %d",&a,&b)
#define scan3(a,b,c)  scanf("%d %d %d",&a,&b,&c)
#define scanl(a)    scanf("%lld",&a)
#define scanll(a,b) scanf("%lld %lld",&a,&b)
#define scanlll(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)

#define print1(a)    printf("%d",a)
#define print2(a,b)  printf("%d %d",a,b)
#define print3(a,b,c)  printf("%d %d %d",a,b,c)
#define printl(a)    printf("%lld",a)
#define printll(a,b) printf("%lld %lld",a,b)
#define printlll(a,b,c) printf("%lld %lld %lld",a,b,c)

#define MAXN        100000007
#define INF 0x3f3f3f3f
bool mark[100005];vi prime;
void seive(ll N){for(int i=2;i<=N;i++){if(mark[i]==false){prime.pb(i);for(int j=i+i;j<N;j+=i)mark[j]=true;}}}
//freopen("input.txt", "r", stdin);

long long res=0;
long long DP[100][100];
int m,n;
vi v(11);
long long func(int digit, int cntn)
{
    if(cntn==n)    return 1;


    for(int i=0;i<m;i++){
            if(abs(digit-v[i])<=2) {

                    if(DP[v[i]][cntn+1]!=0) DP[digit][cntn]+=DP[v[i]][cntn+1];
                //cout<<v[i]<<" ";
                else
                DP[digit][cntn]+= func(v[i],cntn+1);
            }
    }
    return DP[digit][cntn];
}


int main()
{
   ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
   int t,cases=0; cin>>t;
   while(t--)
   {
       memset(DP,0,sizeof(DP));
        cin>>m>>n;

       for(int i=0;i<m;i++) cin>>v[i];

        for(int i=0;i<m;i++)
            DP[v[i]][0]=func(v[i],1);

    res=0;
    for(int i=0;i<m;i++) res+=DP[v[i]][0];

    cout<<"Case "<<++cases<<": "<<res<<endl;
   }

}