oj.uz

답안 #19281

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
19281 2016-02-24T02:38:38 Z kaTkaHr 비트 (kriii4_Q) C++14
9 / 100
 169 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 main()
{
	int N, p, q, K;
	scanf("%d%d", &N, &K);

  for(int i = 0; i <= N; i++){
    D[i][i] = I[i][i] = 1;
    if( i <= N-2 ) D[i][i+1] = frac(-i-1, N);
    if( i >= 1) D[i][i-1] = frac(-N+i-1, N);
    
		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++){
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 1948 KB Output is correct
2 Correct 105 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 0 ms 1948 KB Output is correct
7 Correct 20 ms 1948 KB Output is correct
8 Correct 81 ms 1948 KB Output is correct
9 Correct 0 ms 1948 KB Output is correct
10 Correct 6 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 169 ms 1948 KB Output is correct
20 Correct 3 ms 1948 KB Output is correct

Subtask #2
0.0 / 91.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 1948 KB Output isn't correct
2 Halted 0 ms 0 KB -