LightOJ 1122 - Digit Count

// Fix a position, put a letter in it. for first idx, try all of the letters, in the same manner for all possible first charcter, try out all possible second character.  Then go to next position try all of the available letters, try putting all of them by a loop inside . continue doing it until you get to the required size of string.

// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define sci(x) scanf("%d", &x)
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define MOD 100007

int ar[30];
int dp[12][12];
int n, sz;

int solve(int i, int digit)
{
    if(i==sz+1) return 1;

    if(dp[i][digit]!=-1) return dp[i][digit];

    dp[i][digit] = 0;

    for(int j=1; j<=n; j++)
    {
        if(i==1)
        {
            dp[i][digit] += solve(i+1, ar[j]);
            continue;
        }
        if(abs(digit - ar[j]) <= 2) dp[i][digit] += solve(i+1, ar[j]);
    }
    return dp[i][digit];
}

int main()
{
    int t, cs=0;
    scanf("%d", &t);
    while(t--)
    {
        mem(dp,-1);
        scanf("%d%d", &n, &sz);
        for(int i=1; i<=n; i++) scanf("%d",&ar[i]);
        int res = solve(1,n+1);
        printf("Case %d: %d\n", ++cs, res);
    }
    return 0;
}