제출 #19284

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
19284		kaTkaHr	비트 (kriii4_Q)	C++14	100 / 100	1053 ms	1908 KiB

Q

#include <stdio.h>
#include<vector>
#include <algorithm>
#include <map>

using namespace std;

typedef long long ll;

const int MX = 105, MM = 1000000007;

ll pw(ll A, ll B){
  ll R = 1;
  while(B){
    if( B&1 ) R = R * A % MM;
    A = A * A % MM; B /= 2;
  }
  return R;
}


ll rv(ll A){ return pw(A, MM-2); }
/*
struct frac{
  ll A, B;
		frac(ll A):A(A), B(1){}
  frac(ll a, ll b){
    A = (a%MM+MM) % MM;
    B = (b%MM+MM) % MM;
  }
  frac(){A = 0, B = 1;}
  frac operator+ (const frac &l)const{
    return frac((A * l.B + B * l.A) % MM, B * l.B % MM);
  }
  frac operator*(const frac &l)const{
    return frac(A*l.A % MM, B*l.B % MM);
  }
  frac operator/(const frac &l)const{
    return frac(A*l.B % MM, B*l.A % MM);
  }
  frac operator- (const frac &l)const{
    return frac((A*l.B - B*l.A%MM + MM) % MM, B*l.B % MM);
  }
  ll v(){ return A * rv(B) % MM; }
};/ */
//*
struct frac{
  ll A;
		frac(ll A):A((A%MM+MM)%MM){}
  frac(ll a, ll b){
			a = (a%MM+MM)%MM;
			b = (b%MM+MM)%MM;
			A = rv(b) * a % MM;
  }
  frac(){A = 0;}
  frac operator+ (const frac &l)const{
			return l.A + A >= MM? l.A + A - MM: l.A + A;
  }
  frac operator*(const frac &l)const{
			return l.A * A % MM;
  }
  frac operator/(const frac &l)const{
			return A * rv(l.A) % MM;
  }
  frac operator- (const frac &l)const{
			return A >= l.A? A-l.A: A-l.A + MM;
  }
  ll v(){ return A; }
};// */

frac pw(frac A, ll B){
  frac R = 1;
  while(B){
    if( B&1 ) R = R * A;
    A = A * A; B /= 2;
  }
  return R;
}

frac D[MX][MX], I[MX][MX], A[MX][MX], R[MX][MX], S[MX][MX];
int N, K;

void mat_multi(frac C[MX][MX], frac A[MX][MX], frac B[MX][MX])
{
	static frac tmp[MX][MX];
	for(int i = 0; i <= N; i++){
		for(int j = 0; j <= N; j++){
			tmp[i][j] = 0;
			for(int k = 0; k <= N; k++){
				tmp[i][j] = tmp[i][j] + A[i][k] * B[k][j];
			}
		}
	}
	for(int i = 0; i <= N; i++){
		for(int j = 0; j <= N; j++){
			C[i][j] = tmp[i][j];
		}
	}
}


void make_matrix(frac A[MX][MX])
{
	static frac X[MX][MX], R[MX][MX];
	for(int i = 0; i <= N; i++){
		R[i][i] = 1;
		if( i <= N-2 ) A[i][i+1] = frac(i+1, N);
	  if( i >= 1) A[i][i-1] = frac(N-i+1, N);
	}
	for(int i = 0; i <= N; i++){
		if( i <= N-1 ) X[i][i+1] = frac(i+1, N);
	  if( i >= 1) X[i][i-1] = frac(N-i+1, N);
	}
	int k = K-1;
	while(k){
		if( k&1 ) mat_multi(R, R, X);
		k /= 2; mat_multi(X, X, X);
	}
	mat_multi(A, R, A);
}

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

	make_matrix(A);

  for(int i = 0; i <= N; i++){
		I[i][i] = 1;
		for(int j = 0; j <= N; j++){
			if( i != j ) D[i][j] = frac(0, 1) - A[i][j];
			else D[i][i] = 1;
    }
  }
  for(int i = 0; i <= N; i++){
    for(int j = i+1; j <= N; j++){
      frac p = D[j][i] / D[i][i];
      for(int k = 0; k <= N; k++){
        D[j][k] = D[j][k] - D[i][k] * p;
        I[j][k] = I[j][k] - I[i][k] * p;
      }
    }
  }
  for(int i = N; i >= 0; i--){
    for(int j = i-1; j >= 0; j--){
      frac p = D[j][i] / D[i][i];
      for(int k = N; k >= 0; k--){
        D[j][k] = D[j][k] - D[i][k] * p;
        I[j][k] = I[j][k] - I[i][k] * p;
      }
    }
  }
  for(int i = 0; i <= N; i++){
    frac p = frac(1, 1) / D[i][i];
    for(int j = 0; j <= N; j++){
      D[i][j] = D[i][j] * p;
      I[i][j] = I[i][j] * p;
    }
  }

	for(int i = 0; i <= N; i++){
		for(int j = 0; j <= N; j++){
			R[i][j] = 0;
			for(int k = 0; k <= N; k++){
				R[i][j] = R[i][j] + I[i][k] * A[k][j];
			}
		}
	}
	
	for(int i = 0; i <= N; i++){
		for(int j = 0; j <= N; j++){
			S[i][j] = 0;
			for(int k = 0; k <= N; k++){
				S[i][j] = S[i][j] + R[i][k] * I[k][j];
			}
		}
	}

	for(int i = N-1; i >= 0; i--){
	  printf("%lld\n", S[N][i].v());
	}
}

• Subtask 1: 9 / 9
• Subtask 2: 91 / 91