oj.uz

Submission #19282

# Submission time Handle Problem Language Result Execution time Memory
19282 2016-02-24T02:41:02 Z kaTkaHr 비트 (kriii4_Q) C++14
9 / 100
 167 ms 1948 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 make_matrix(frac A[MX][MX])
{
	for(int i = 0; i <= N; i++){
		if( i <= N-2 ) A[i][i+1] = frac(i+1, N);
	  if( i >= 1) A[i][i-1] = frac(N-i+1, N);
	}
}

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 36 ms 1948 KB Output is correct
2 Correct 101 ms 1948 KB Output is correct
3 Correct 0 ms 1948 KB Output is correct
4 Correct 11 ms 1948 KB Output is correct
5 Correct 159 ms 1948 KB Output is correct
6 Correct 3 ms 1948 KB Output is correct
7 Correct 23 ms 1948 KB Output is correct
8 Correct 79 ms 1948 KB Output is correct
9 Correct 0 ms 1948 KB Output is correct
10 Correct 3 ms 1948 KB Output is correct
11 Correct 34 ms 1948 KB Output is correct
12 Correct 105 ms 1948 KB Output is correct
13 Correct 0 ms 1948 KB Output is correct
14 Correct 55 ms 1948 KB Output is correct
15 Correct 154 ms 1948 KB Output is correct
16 Correct 3 ms 1948 KB Output is correct
17 Correct 22 ms 1948 KB Output is correct
18 Correct 78 ms 1948 KB Output is correct
19 Correct 167 ms 1948 KB Output is correct
20 Correct 6 ms 1948 KB Output is correct

Subtask #2
0.0 / 91.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 1948 KB Output isn't correct
2 Halted 0 ms 0 KB -