oj.uz

Submission #19284

# Submission time Handle Problem Language Result Execution time Memory
19284 2016-02-24T03:00:29 Z kaTkaHr 비트 (kriii4_Q) C++14
100 / 100
 1053 ms 1908 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1908 KB Output is correct
2 Correct 60 ms 1908 KB Output is correct
3 Correct 0 ms 1908 KB Output is correct
4 Correct 6 ms 1908 KB Output is correct
5 Correct 91 ms 1908 KB Output is correct
6 Correct 0 ms 1908 KB Output is correct
7 Correct 14 ms 1908 KB Output is correct
8 Correct 47 ms 1908 KB Output is correct
9 Correct 0 ms 1908 KB Output is correct
10 Correct 3 ms 1908 KB Output is correct
11 Correct 20 ms 1908 KB Output is correct
12 Correct 60 ms 1908 KB Output is correct
13 Correct 0 ms 1908 KB Output is correct
14 Correct 34 ms 1908 KB Output is correct
15 Correct 89 ms 1908 KB Output is correct
16 Correct 0 ms 1908 KB Output is correct
17 Correct 13 ms 1908 KB Output is correct
18 Correct 46 ms 1908 KB Output is correct
19 Correct 97 ms 1908 KB Output is correct
20 Correct 0 ms 1908 KB Output is correct

Subtask #2
91.0 / 91.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1908 KB Output is correct
2 Correct 782 ms 1908 KB Output is correct
3 Correct 16 ms 1908 KB Output is correct
4 Correct 122 ms 1908 KB Output is correct
5 Correct 460 ms 1908 KB Output is correct
6 Correct 856 ms 1908 KB Output is correct
7 Correct 37 ms 1908 KB Output is correct
8 Correct 205 ms 1908 KB Output is correct
9 Correct 517 ms 1908 KB Output is correct
10 Correct 88 ms 1908 KB Output is correct
11 Correct 320 ms 1908 KB Output is correct
12 Correct 915 ms 1908 KB Output is correct
13 Correct 16 ms 1908 KB Output is correct
14 Correct 127 ms 1908 KB Output is correct
15 Correct 369 ms 1908 KB Output is correct
16 Correct 0 ms 1908 KB Output is correct
17 Correct 33 ms 1908 KB Output is correct
18 Correct 617 ms 1908 KB Output is correct
19 Correct 6 ms 1908 KB Output is correct
20 Correct 1053 ms 1908 KB Output is correct