pendant.java

第四届百度杯编程大赛final解题报告+标程

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

class Matrix {
	static final int M = 1234567891;
	public int a[][];
	public int n;

	Matrix(int _n, int f) {
		n = _n;
		a = new int[n][n];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				if (i == j)
					a[i][j] = f;
				else
					a[i][j] = 0;
	}

	Matrix add(Matrix b) {
		Matrix ret = new Matrix(n, 0);
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				ret.a[i][j] = (a[i][j] + b.a[i][j]) % M;
		return ret;
	}
	
	Matrix multiply(Matrix b) {
		Matrix ret = new Matrix(n, 0);
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				for (int k = 0; k < n; k++)
					ret.a[i][j] = (int)((ret.a[i][j] + (long)(a[i][k]) * b.a[k][j]) % M);
		return ret;
	}
	
	Matrix pow(int p) {
		Matrix ret = new Matrix(n, 1);
		Matrix t = this;
		while (p != 0) {
			if ((p & 1) != 0) ret = ret.multiply(t);
			p >>= 1;
			t = t.multiply(t);
		}
		return ret;
	}
}

public class Pendant {
	public static void main(String args[]) throws Exception {
		Scanner cin = new Scanner(System.in);
                int ca;
                ca = cin.nextInt();
                for (int c = 0; c < ca; c++) {
			int n = cin.nextInt();
			int k = cin.nextInt();
			Matrix g = new Matrix(2 * (k + 1), 1);
			for (int i = 0; i <= k; i++) {
				g.a[i][i] = i;
				if (i - 1 >= 0)
					g.a[i][i - 1] = k - i + 1;
			}
			for (int i = 0; i <= k; i++) {
				g.a[k + 1 + i][i] = 1;
			}
			
			Matrix gg = g.pow(n);
			System.out.println(gg.a[2 * k + 1][1] * (long)k % 1234567891);
		}
	}
}