Submission #19002

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19002	2016-02-17T02:53:46 Z	kriii	비트 (kriii4_Q)	C++14	100 / 100	205 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;
		}
		if (!good){fprintf (stderr,"nope");}
		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][i-1] = i;
		if (i < N) r.A[i][i+1] = 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;
	}
	
	vector<vector<long long> > A = vector<vector<long long> >(N+1,vector<long long>(N+2,0));
	for (int i=0;i<A.size();i++) A[i][i] = A[i][N+1] = all;
	A[0][N+1] = 0;

	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=1;i<=N;i++){
		for (int j=1;j<=N;j+=2){
			for (int k=0;k<=i&&k<=j;k++){
				if (N-i >= j-k){
					long long coeff = comb[i][k] * comb[N-i][j-k] % mod;
					add(A[i][i-k+j-k],mod-coeff*prv[j]%mod);
				}
			}
		}
	}

	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	1776 KB	Output is correct
2	Correct	6 ms	1780 KB	Output is correct
3	Correct	0 ms	1776 KB	Output is correct
4	Correct	0 ms	1780 KB	Output is correct
5	Correct	9 ms	1904 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	1780 KB	Output is correct
9	Correct	0 ms	1776 KB	Output is correct
10	Correct	0 ms	1772 KB	Output is correct
11	Correct	0 ms	1776 KB	Output is correct
12	Correct	6 ms	1776 KB	Output is correct
13	Correct	0 ms	1772 KB	Output is correct
14	Correct	4 ms	1772 KB	Output is correct
15	Correct	9 ms	1904 KB	Output is correct
16	Correct	0 ms	1776 KB	Output is correct
17	Correct	2 ms	1780 KB	Output is correct
18	Correct	5 ms	1780 KB	Output is correct
19	Correct	10 ms	1908 KB	Output is correct
20	Correct	0 ms	1776 KB	Output is correct

Subtask #2

91.0 / 91.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	1776 KB	Output is correct
2	Correct	173 ms	1912 KB	Output is correct
3	Correct	4 ms	1772 KB	Output is correct
4	Correct	27 ms	1780 KB	Output is correct
5	Correct	92 ms	1772 KB	Output is correct
6	Correct	179 ms	1908 KB	Output is correct
7	Correct	8 ms	1780 KB	Output is correct
8	Correct	43 ms	1780 KB	Output is correct
9	Correct	118 ms	1776 KB	Output is correct
10	Correct	19 ms	1772 KB	Output is correct
11	Correct	75 ms	1780 KB	Output is correct
12	Correct	193 ms	1908 KB	Output is correct
13	Correct	4 ms	1780 KB	Output is correct
14	Correct	25 ms	1772 KB	Output is correct
15	Correct	86 ms	1776 KB	Output is correct
16	Correct	0 ms	1776 KB	Output is correct
17	Correct	7 ms	1776 KB	Output is correct
18	Correct	141 ms	1908 KB	Output is correct
19	Correct	0 ms	1772 KB	Output is correct
20	Correct	205 ms	1912 KB	Output is correct