Submission #19202

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19202	2016-02-20T14:15:11 Z	kriii	비트 (kriii4_Q)	C++14	100 / 100	206 ms	1912 KB

Q

#include <stdio.h>
#include <vector>
using namespace std;

const long long mod = 1000000007;

void add(long long &a, long long b)
{
	a = (a + b) % mod;
}

void mult(long long &a, long long b)
{
	a = (a * b) % mod;
}

long long fpow(long long a, long long p)
{
	a %= mod;
	p = (p % (mod - 1) + mod - 1) % (mod - 1);
	long long r = 1;
	while (p){
		if (p & 1) mult(r,a);
		mult(a,a);
		p /= 2;
	}
	return r;
}

vector<long long> gauss(vector<vector<long long> > A)
{
	int n = A.size();

	for (int i=0;i<n;i++){
		bool good = 0;
		for (int j=i;j<n;j++) if (A[j][i]){
			swap(A[i],A[j]);
			good = 1;
			break;
		}
		long long u = fpow(A[i][i],-1);
		for (int j=i;j<=n;j++) mult(A[i][j],u);
		for (int k=0;k<n;k++) if (k != i && A[k][i]){
			u = A[k][i];
			for (int j=i;j<=n;j++) add(A[k][j],mod-A[i][j]*u%mod);
		}
	}

	vector<long long> ret;
	for (int i=0;i<n;i++)
		ret.push_back(A[i][n]);

	return ret;
}

struct matrix{
	matrix(){
		n = 0;
	}
	matrix(int n_){
		n = n_;
		for (int i=0;i<n;i++) for (int j=0;j<n;j++) A[i][j] = 0;
	}
	int n; long long A[101][101];

	matrix operator *(matrix t){
		matrix r(n);
		for (int i=0;i<n;i++) for (int j=0;j<n;j++) for (int k=0;k<n;k++) r.A[i][j] = (r.A[i][j] + A[i][k] * t.A[k][j]) % mod;
		return r;
	}
};

long long prv[101],nxt[101];
long long comb[101][101];

int main()
{
	int N,K; scanf ("%d %d",&N,&K);

	matrix r(N+1);
	for (int i=0;i<=N;i++){
		if (i > 0) r.A[i-1][i] = i;
		if (i < N) r.A[i+1][i] = N - i;
	}

	long long all = fpow(N,K);
	prv[0] = 1;
	while (K){
		if (K & 1){
			for (int i=0;i<=N;i++) nxt[i] = 0;
			for (int i=0;i<=N;i++) for (int j=0;j<=N;j++) nxt[i] = (nxt[i] + r.A[i][j] * prv[j]) % mod;
			for (int i=0;i<=N;i++) prv[i] = nxt[i];
		}
		r = r * r;
		K /= 2;
	}

	for (int i=0;i<=N;i++){
		comb[i][0] = comb[i][i] = 1;
		for (int j=1;j<i;j++) comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % mod;
	}
	for (int i=0;i<=N;i++) prv[i] = prv[i] * fpow(comb[N][i],-1) % mod;
	
	vector<vector<long long> > A = vector<vector<long long> >(N+1,vector<long long>(N+2,0));
	A[0][0] = 1;

	for (int i=1;i<=N;i++){
		for (int j=1;j<=N;j+=2){
			for (int k=max(0,i+j-N);k<=i&&k<=j;k++){
				long long coeff = comb[i][k] * comb[N-i][j-k] % mod;
				long long in = coeff * prv[j] % mod;
				add(A[i][i-k+j-k],mod-in);
				add(A[i][i],in);
				add(A[i][N+1],in);
			}
		}
	}

	vector<long long> res = gauss(A);
	for (int i=1;i<=N;i++) printf ("%lld\n",res[i]);

	return 0;
}

Subtask #1

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1772 KB	Output is correct
2	Correct	7 ms	1780 KB	Output is correct
3	Correct	0 ms	1772 KB	Output is correct
4	Correct	0 ms	1776 KB	Output is correct
5	Correct	10 ms	1908 KB	Output is correct
6	Correct	0 ms	1776 KB	Output is correct
7	Correct	0 ms	1776 KB	Output is correct
8	Correct	5 ms	1776 KB	Output is correct
9	Correct	1 ms	1780 KB	Output is correct
10	Correct	0 ms	1776 KB	Output is correct
11	Correct	2 ms	1772 KB	Output is correct
12	Correct	6 ms	1772 KB	Output is correct
13	Correct	0 ms	1776 KB	Output is correct
14	Correct	4 ms	1780 KB	Output is correct
15	Correct	9 ms	1908 KB	Output is correct
16	Correct	0 ms	1776 KB	Output is correct
17	Correct	1 ms	1772 KB	Output is correct
18	Correct	5 ms	1776 KB	Output is correct
19	Correct	10 ms	1908 KB	Output is correct
20	Correct	0 ms	1772 KB	Output is correct

Subtask #2

91.0 / 91.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	1776 KB	Output is correct
2	Correct	174 ms	1912 KB	Output is correct
3	Correct	4 ms	1780 KB	Output is correct
4	Correct	27 ms	1780 KB	Output is correct
5	Correct	92 ms	1776 KB	Output is correct
6	Correct	177 ms	1908 KB	Output is correct
7	Correct	8 ms	1772 KB	Output is correct
8	Correct	43 ms	1772 KB	Output is correct
9	Correct	118 ms	1776 KB	Output is correct
10	Correct	19 ms	1772 KB	Output is correct
11	Correct	74 ms	1780 KB	Output is correct
12	Correct	194 ms	1912 KB	Output is correct
13	Correct	4 ms	1772 KB	Output is correct
14	Correct	28 ms	1776 KB	Output is correct
15	Correct	86 ms	1776 KB	Output is correct
16	Correct	0 ms	1772 KB	Output is correct
17	Correct	7 ms	1776 KB	Output is correct
18	Correct	140 ms	1912 KB	Output is correct
19	Correct	0 ms	1776 KB	Output is correct
20	Correct	206 ms	1912 KB	Output is correct