Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- public class Test {
- long mod = (long) 1e9 + 7;
- int MAX = 226;
- long[] getAns(int n, int m) {
- ArrayList<Integer> okay = new ArrayList<>();
- for (int st = 0; st < 1 << n; st++) {
- boolean ok = true;
- for (int i = 0; i < n - 1; i++)
- if (((1 << i) & st) != 0)
- if (((1 << (i + 1)) & st) != 0)
- ok = false;
- if (ok)
- okay.add(st);
- }
- ArrayList<Integer> g[] = new ArrayList[okay.size()];
- for (int i = 0; i < g.length; i++)
- g[i] = new ArrayList<>();
- for (int i = 0; i < okay.size(); i++) {
- int x = okay.get(i);
- for (int j = 0; j < okay.size(); j++) {
- int y = okay.get(j);
- boolean ok = true;
- for (int i1 = 0; i1 < n; i1++)
- if (((1 << i1) & x) != 0)
- for (int dx = -1; dx <= 1; dx++)
- if (i1 + dx >= 0 && i1 + dx < n)
- if (((1 << (i1 + dx)) & y) != 0)
- ok = false;
- if (ok) {
- g[i].add(j);
- }
- }
- }
- int m1 = okay.size();
- long[][] dp = new long[MAX][m1];
- dp[0][0] = 1;
- for (int it = 0; it < m; it++) {
- long[][] dp2 = new long[MAX][m1];
- for (int last = 0; last < m1; last++)
- for (int lastcnt = 0; lastcnt < MAX; lastcnt++)
- if (dp[lastcnt][last] != 0)
- for (int ne : g[last])
- dp2[lastcnt + Integer.bitCount(okay.get(ne))][ne] += dp[lastcnt][last];
- dp = dp2;
- for (int i = 0; i < MAX; i++)
- for (int st = 0; st < m1; st++)
- dp[i][st] %= mod;
- }
- long[] tmp = new long[MAX];
- for (int sz = 0; sz < MAX; sz++) {
- for (int i = 0; i < m1; i++)
- tmp[sz] += dp[sz][i];
- tmp[sz] %= mod;
- }
- return tmp;
- }
- int MM = 15;
- long[][][] res = new long[MM + 1][MM + 1][];
- void realSolve() {
- for (int n = 0; n <= MM; n++)
- for (int m = 0; m <= MM; m++) {
- res[n][m] = getAns(n, m);
- // System.err.println(n + " " + m);
- }
- sol();
- }
- void sol() {
- int te = in.nextInt();
- for (int t = 0; t < te; t++) {
- int n = in.nextInt();
- int m = in.nextInt();
- int k = in.nextInt();
- out.println(res[n][m][k]);
- }
- }
- private class InputReader {
- StringTokenizer st;
- BufferedReader br;
- public InputReader(File f) {
- try {
- br = new BufferedReader(new FileReader(f));
- } catch (FileNotFoundException e) {
- e.printStackTrace();
- }
- }
- public InputReader(InputStream f) {
- br = new BufferedReader(new InputStreamReader(f));
- }
- String next() {
- while (st == null || !st.hasMoreElements()) {
- String s;
- try {
- s = br.readLine();
- } catch (IOException e) {
- return null;
- }
- if (s == null)
- return null;
- st = new StringTokenizer(s);
- }
- return st.nextToken();
- }
- int nextInt() {
- return Integer.parseInt(next());
- }
- double nextDouble() {
- return Double.parseDouble(next());
- }
- boolean hasMoreElements() {
- while (st == null || !st.hasMoreElements()) {
- String s;
- try {
- s = br.readLine();
- } catch (IOException e) {
- return false;
- }
- st = new StringTokenizer(s);
- }
- return st.hasMoreElements();
- }
- long nextLong() {
- return Long.parseLong(next());
- }
- }
- InputReader in;
- PrintWriter out;
- void solve() {
- in = new InputReader(new File("object.in"));
- try {
- out = new PrintWriter(new File("object.out"));
- } catch (FileNotFoundException e) {
- e.printStackTrace();
- }
- realSolve();
- out.close();
- }
- void solveIO() {
- in = new InputReader(System.in);
- out = new PrintWriter(System.out);
- realSolve();
- out.close();
- }
- public static void main(String[] args) {
- Locale.setDefault(Locale.US);
- new Test().solveIO();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement