(0) 설명의 편의를 위해서,  초기상태에 물고기의 뱃속에 들어있는 보석의 종류를 물고기의 종류라고 합시다.
또한, 어떤 물고기 A가 먹을 수있는 물고기들의 집합을 G(A)라고 합시다. 이때 그 물고기의 뱃속에서 나올수 있는 조합의 갯수는
 ( G(A)속의 종류 1의 갯수 + 1 ) * (  .. 종류 2의 갯수 + 1 ) * ( .. 보석 K의 갯수 + 1) 이 될 것입니다.
 
  예를 들어서, 종류1 의 물고기A가 종류별로 각각 {3,2,4}마리의 물고기를 먹을 수 있을때 그 뱃속에서 나올수 있는 조합의 수는:
  1번 보석의 갯수는 [ 1 ... 4 ] (4종류) /  2번 보석의 갯수는 [ 0 ... 2 ] (3종류) /  3번 보석의 갯수는 [ 0 ... 4 ] (5종류)
  로 4*3*5=60 가지입니다. 

 (1) 어떤 동종의 물고기 A,B가 있다고 합시다. 이때 각 물고기의 길이를 L(A), L(B)라고 하고,
 L(A) ≥ L(B) 임을 가정합시다. B가 먹을 수 있는 물고기는 항상 A가 먹을 수 있기 때문에  G(A)⊇G(B)가 성립됩니다. 
거기에 더해서,  A,B의 종류가 같기 때문에 B의 뱃속에서 나올 수 있는 조합은 항상 A의 뱃속에서 나올수 있습니다.
여기에서 각 종류별로 가장 큰 물고기의 배에서 나올 수 있는 조합을 세어도 답이 될것임을 알 수 있습니다.
앞으로는 각 종류별로 챔피언인 K마리의 물고기만이 다른 물고기를 먹는다고 생각하도록 하겠습니다.

 (2) 이제 서로 다른 종류의 가장 큰 물고기 K 마리만을 포식자로 남겨놓았습니다. 
그  가장 큰 물고기에 그 종류의 번호를 붙여서 부르도록 하겠습니다.
예를들어 종류가 1번인 물고기 중 가장 큰 물고기를 1번물고기라 부르겠습니다.
이번에도 서로 다른 종류의 N,M 두 물고기가 L(N) ≥ L(M)을 만족한다고 합시다. 역시  G(N)⊇G(M)이 성립할 것입니다.
그러면 역시 M이 만들 수 있는 조합의 대부분이 N이 만들 수 있는 조합에 포함될 것입니다.
그러나, N과 M이 각각 가지고 있는 고유의 보석의 종류가 다르기 때문에 M은 다음 2가지측면에서 차별화를 시도할 수 있습니다. 

 case i. - 보석 N의 갯수를 0개 가질 수 있다 : 
   물고기 N이 태생적인 한계[?] 때문에 항상 보석 N을 최소한 1개는 가져야하기 때문에,
   보석 N을 0개 가지는 경우가 있다면 이는 항상 물고기 N이 고려하지 않았던 경우입니다.

 case ii- 보석 M의 갯수를 N이 가진 최대값보다 한 개 더 많이 가질 수 있다 : 
  L(M)이 꽤 클 때, 물고기 M이 '먹을 수 있는(자신이 가지고 있는 것은 제외하고)' 보석M의 갯수(노테이션이 헷갈리는군요-_-;)와
  물고기 N이 먹을 수 있는 보석 M의 갯수가 같을 수 있습니다. 이 경우에는 물고기M 자신이 갖고 있는 보석M을 보태서 최대값이
  N의 최대값보다 1 클 수 있는데, 이 역시 물고기 N이 고려하지 않았던 경우입니다.

  1번 케이스의 경우는 어떤 N과 M에 대해서도 가능하지만 2번 케이스의 경우는 몇몇 N과 M에 대해서만 성립합니다.
극단적인 예로, N이 아예 M자체를 먹어 버릴 수 있다면 1번 케이스의 경우를 제외하고는 M의 어떤 조합도 N이 만드는 조합에
포함될 것입니다. 정확히 말하자면, N이 물고기M이 먹을 수 없는 종류 M인 가장 작은 물고기(자기 자신을 포함해서)를 먹을 수 있다면
2번 케이스는 성립할 수 없습니다.

 (3) 편의를 위해서 문제에 추가적으로 다음과 같은 가정이 있다고 하겠습니다:
 각 종류별로 가장 큰 물고기의 크기순으로 번호가 매겨져 있습니다. 즉, L(1)≥L(2)≥L(3)≥...≥L(K).
 (만약 그렇지 않은 경우에도, 위 조건을 만족하도록 보석의 번호를 다시 매길 수 있습니다.)
 또한 각 물고기 i가 먹을수 있는 보석 j의 갯수를 T(i,j)라 하고 T(i,j) = G(i)에 속하는 보석 j의 갯수라 정의하겠습니다.
 큰 순서대로, 즉 번호순으로 각 물고기가 만들 수 있는 '새로운'  조합을 고려하는 방법으로 접근하고자 합니다.

 임의의 x번째 물고기를 고려하는 경우를 생각해봅시다.
 1 ... x-1 번째 물고기까지는 고려되었고, x+1 ... k 번째 물고기는 고려되지 않았습니다.
 따라서, 앞에서부터 1...x에 대해서만 보석의 조합이 이전과 다르면, 그 뒤의 종류들은 (0)에서 고려했던데로
 { T(x, x+1) + 1 } * { T(x, x+2)+1 } * ... { T(x, k)+1 } 의 가짓수를 만들어 낼 수 있습니다. 반대로 1...x 의 보석의 조합이
 이전에 고려되었던 조합이면 그 뒤의 조합은 어떻게 되든 이미 고려되었던 조합이 됩니다.

 x의 관점에서 새로운 조합을 만들어 내는 방법은 (2)에서의 케이스들에서 살펴보았습니다.
 (0)에서 살펴보았듯이, x의 뱃속에서 나올 수 있는 보석 x의 갯수는 [1...T(x,x)+1] 입니다.
 이 중 T(x,x)+1 개가 나오는 경우를 제외하고는, 2번 케이스에 해당하지 않습니다.
 그러나 종류 1...x까지 보석의 갯수가 0개 나온다고 본다면 고려되지 않았던 조합을 만들어 낼 수 있습니다.
 이때 가능한 조합의 갯수는 { T(x, x+1) + 1 } * { T(x, x+2)+1 } * ... { T(x, k)+1 }  => <1>
 T(x,x) +1 개가 나오는 경우에는 T(y,x) < T(x,x)+1 , y<x 를 만족하는 y가 존재할 수 있습니다.
 이러한 y들은 이전에 고려되지 않았던것처럼 볼 수있으므로  { T(x,y)+1 } 만큼의 선택의 수가 늘어나게 됩니다.
 이 y들중 가장 작은 값을 min_y라고 하면, 역시 가능한 조합의 갯수는
 { T(x, min_y)+1 } * { T(x, min_y+1)+1 } ... * { T(x, x-1)+1 } * { T(x, x+1) + 1 } * { T(x, x+2)+1 } * ... { T(x, k)+1 } => <2>

 그런데, <1>은 [1...T(x,x)]에 대한 경우이므로 T(x,x)번 발생하고 <2>는 단 한번(T(x,x)+1)번 발생합니다.
 그러므로 각 x에 대해서, 
                                                                                                          { T(x,x) } * { T(x, x+1) + 1 } * { T(x, x+2)+1 } * ... { T(x, k)+1 } 
  +  { T(x, min_y)+1 } * { T(x, min_y+1)+1 } ... * { T(x, x-1)+1 }                * { T(x, x+1) + 1 } * { T(x, x+2)+1 } * ... { T(x, k)+1 }            

  를 수행해주면 됩니다. 각 곱셈을 순서대로 해준다면 O(K*K)의 시간이 걸리는데,  우리의 친구 Indexed Tree를 사용하면
 이를 O(K lg K)로 줄일 수 있습니다. 이번에도 글이 길었네요-_-; 항상 글이 장광설적으로 가는거 같습니다 ㅠㅠ