1. 首页
2. 数位DP
3. 本页

Hdu 5642 King's Order (数位DP)

dp[i][j] 表示长度为i，重复的个数为j

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static BigInteger[][] dp = new BigInteger[2500][5];
	static BigInteger MOD = BigInteger.valueOf(1000000007);;

	public static void solve() {
		for (int i = 0; i < 2005; ++i) {
			Arrays.fill(dp[i], BigInteger.ZERO);
		}
		dp[0][1] = BigInteger.valueOf(26);
		dp[0][2] = BigInteger.ZERO;
		for (int i = 1; i < 2005; ++i) {
			dp[i][2] = dp[i - 1][1].mod(MOD);
			dp[i][3] = dp[i - 1][2].mod(MOD);
			dp[i][1] = dp[i - 1][1].add(dp[i - 1][2].add(dp[i - 1][3]));
			dp[i][1] = dp[i][1].multiply(BigInteger.valueOf(25));
			dp[i][1] = dp[i][1].mod(MOD);
		}
	}

	public static void main(String[] args) {
		InputReader in = new InputReader();
		PrintWriter out = new PrintWriter(System.out);
		int t, n;
		t = in.nextInt();
		solve();
		while (t > 0) {
			t--;
			n = in.nextInt();
			out.println((dp[n - 1][1].add(dp[n - 1][2].add(dp[n - 1][3])))
					.mod(MOD));
		}
		out.close();
	}

}

class InputReader {
	BufferedReader buf;
	StringTokenizer tok;

	InputReader() {
		buf = new BufferedReader(new InputStreamReader(System.in));
	}

	boolean hasNext() {
		while (tok == null || !tok.hasMoreElements()) {
			try {
				tok = new StringTokenizer(buf.readLine());
			} catch (Exception e) {
				return false;
			}
		}
		return true;
	}

	String next() {
		if (hasNext())
			return tok.nextToken();
		return null;
	}

	int nextInt() {
		return Integer.parseInt(next());
	}

	long nextLong() {
		return Long.parseLong(next());
	}

	double nextDouble() {
		return Double.parseDouble(next());
	}

	BigInteger nextBigInteger() {
		return new BigInteger(next());
	}

	BigDecimal nextBigDecimal() {
		return new BigDecimal(next());
	}
}