UVa 10541 - Stripe

//\\__ hr1212 __//\\

import java.io.*;
import java.math.*;
import java.util.*;

public class Main{

static int n,m,z,x,y,k,l,r,i,j,t;
static int a[]=new int[500];;
static String s,p[],q;
static int MAX=1000010;
static BigInteger dp[][]=new BigInteger[500][500];;

public static void main(String[] args) throws IOException{
InputReader in=new InputReader(System.in);
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
PrintWriter out=new PrintWriter(System.out);

t=Integer.parseInt(br.readLine());
for(k=0;k<t;k++){
for(i=0;i<500;i++){
for(j=0;j<500;j++)
dp[i][j]=BigInteger.valueOf(-1);
}
s=br.readLine();
p=s.split(" ");

m=Integer.parseInt(p[0]);
n=Integer.parseInt(p[1]);
for(i=0;i<n;i++){
a[i]=Integer.parseInt(p[i+2]);
}
System.out.println(solve(1,0));
}

out.close();

}

static BigInteger solve(int i,int j){
if(j==n && i<=m+2)
return BigInteger.ONE;
if(j>=n || i>m)
return BigInteger.ZERO;
z=dp[i][j].compareTo(BigInteger.valueOf(-1));
if(z!=0)
return dp[i][j];
return dp[i][j]=solve(i+1,j).add(solve(i+a[j]+1,j+1));
}

static class InputReader {

private InputStream stream;
private byte[] buf = new byte[8192];
private int curChar;
private int snumChars;
private SpaceCharFilter filter;

public InputReader(InputStream stream) {
this.stream = stream;
}

public int snext() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}

public int nextInt() {
int c = snext();
while (isSpaceChar(c))
c = snext();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = snext();
}

int res = 0;

do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = snext();
} while (!isSpaceChar(c));

return res * sgn;
}

public long nextLong() {
int c = snext();
while (isSpaceChar(c))
c = snext();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = snext();
}

long res = 0;

do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = snext();
} while (!isSpaceChar(c));

return res * sgn;
}

public String readString() {
int c = snext();
while (isSpaceChar(c))
c = snext();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = snext();
} while (!isSpaceChar(c));
return res.toString();
}

public boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}

public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
}