oj.uz

Submission #19283

# Submission time Handle Problem Language Result Execution time Memory
19283 2016-02-24T02:59:43 Z kaTkaHr 비트 (kriii4_Q) C++14
9 / 100
 2000 ms 2596 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 44 ms 2596 KB Output is correct
2 Correct 129 ms 2596 KB Output is correct
3 Correct 0 ms 2596 KB Output is correct
4 Correct 14 ms 2596 KB Output is correct
5 Correct 196 ms 2596 KB Output is correct
6 Correct 4 ms 2596 KB Output is correct
7 Correct 29 ms 2596 KB Output is correct
8 Correct 100 ms 2596 KB Output is correct
9 Correct 0 ms 2596 KB Output is correct
10 Correct 7 ms 2596 KB Output is correct
11 Correct 42 ms 2596 KB Output is correct
12 Correct 129 ms 2596 KB Output is correct
13 Correct 0 ms 2596 KB Output is correct
14 Correct 72 ms 2596 KB Output is correct
15 Correct 191 ms 2596 KB Output is correct
16 Correct 0 ms 2596 KB Output is correct
17 Correct 24 ms 2596 KB Output is correct
18 Correct 96 ms 2596 KB Output is correct
19 Correct 209 ms 2596 KB Output is correct
20 Correct 7 ms 2596 KB Output is correct

Subtask #2
0.0 / 91.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 2596 KB Output is correct
2 Correct 1605 ms 2596 KB Output is correct
3 Correct 32 ms 2596 KB Output is correct
4 Correct 257 ms 2596 KB Output is correct
5 Correct 937 ms 2596 KB Output is correct
6 Correct 1756 ms 2596 KB Output is correct
7 Correct 76 ms 2596 KB Output is correct
8 Correct 421 ms 2596 KB Output is correct
9 Correct 1056 ms 2596 KB Output is correct
10 Correct 180 ms 2596 KB Output is correct
11 Correct 658 ms 2596 KB Output is correct
12 Correct 1895 ms 2596 KB Output is correct
13 Correct 29 ms 2596 KB Output is correct
14 Correct 259 ms 2596 KB Output is correct
15 Correct 757 ms 2596 KB Output is correct
16 Correct 0 ms 2596 KB Output is correct
17 Correct 66 ms 2596 KB Output is correct
18 Correct 1272 ms 2596 KB Output is correct
19 Correct 11 ms 2596 KB Output is correct
20 Execution timed out 2000 ms 2596 KB Program timed out