제출 #19002

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
19002		kriii	비트 (kriii4_Q)	C++14	100 / 100	205 ms	1912 KiB

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 / 9
• Subtask 2: 91 / 91