library(gmp)
 
printf <- function(...) cat(sprintf(...))
 
ithDuplicatedPermutationInv <- function(a)
{
    N <- length(a)
    i <- as.bigz(1)
 
    a <- as.integer(factor(a))  
    c <- table(a)
 
    P <- factorial(as.bigz(N)) %/% prod(factorial(as.bigz(c)))
 
    for (j in 1:N) {
        k <- a[j]
        if (k > 1) i <- i + (P * sum(c[1:(k - 1)])) %/% (N - j + 1)
        P <- (P * c[k]) %/% (N - j + 1)
        c[k] <- c[k] - 1
    }
 
    i
}
 
Q <- list(
    c(1, 2, 3, 4, 5, 6, 7, 8, 9),
    c(1, 2, 3, 4, 5, 6, 7, 9, 8),
    c(1, 2, 3, 4, 5, 6, 8, 7, 9),
    c(9, 8, 7, 6, 5, 4, 3, 2, 1),
    NULL,
    c(1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4),
    c(1, 1, 1, 2, 2, 2, 3, 3, 4, 3, 4, 4),
    c(1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 3, 4),
    c(2, 2, 2, 3, 3, 1, 4, 3, 4, 1, 1, 4),
    c(3, 2, 4, 4, 2, 4, 3, 3, 1, 1, 1, 2),
    c(4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1),
    NULL,
    c(1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5),
    c(1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 4, 5, 5),
    c(1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5, 4, 5),
    c(1, 1, 1, 3, 3, 3, 4, 4, 2, 5, 4, 5, 2, 2, 5),
    c(1, 1, 1, 4, 3, 5, 5, 3, 5, 4, 4, 2, 2, 2, 3),
    c(1, 1, 1, 5, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2),
    c(5, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1),
    NULL,
    c(1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 
      6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10),
    c(1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5,
      6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 10, 9, 10, 10, 10, 10),
    c(1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5,
      6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 9, 10, 10, 10),
    c(1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5,
      6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 9, 9, 10, 10, 8, 8, 9, 8, 8, 9, 10, 10, 10, 9),
    c(1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5,
      6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 10, 10, 9, 8, 8, 9, 10, 10, 8, 9, 10, 9, 8, 9),
    c(10, 10, 10, 10, 10, 9, 9, 9, 9, 9, 8, 8, 8, 8, 8, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6,
      5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1),
    NULL,
    c(3, 1, 4, 1, 5, 9)
)
 
for (q in Q) {
    if (length(q)) {
        printf("入力: [%s]\n", toString(q))
        printf("出力: %s\n", format(ithDuplicatedPermutationInv(q)))
    }
    printf("\n")
}

bGlicmFyeShnbXApCgpwcmludGYgPC0gZnVuY3Rpb24oLi4uKSBjYXQoc3ByaW50ZiguLi4pKQoKaXRoRHVwbGljYXRlZFBlcm11dGF0aW9uSW52IDwtIGZ1bmN0aW9uKGEpCnsKICAgIE4gPC0gbGVuZ3RoKGEpCiAgICBpIDwtIGFzLmJpZ3ooMSkKCiAgICBhIDwtIGFzLmludGVnZXIoZmFjdG9yKGEpKSAgCiAgICBjIDwtIHRhYmxlKGEpCiAgCiAgICBQIDwtIGZhY3RvcmlhbChhcy5iaWd6KE4pKSAlLyUgcHJvZChmYWN0b3JpYWwoYXMuYmlneihjKSkpCiAgCiAgICBmb3IgKGogaW4gMTpOKSB7CiAgICAgICAgayA8LSBhW2pdCiAgICAgICAgaWYgKGsgPiAxKSBpIDwtIGkgKyAoUCAqIHN1bShjWzE6KGsgLSAxKV0pKSAlLyUgKE4gLSBqICsgMSkKICAgICAgICBQIDwtIChQICogY1trXSkgJS8lIChOIC0gaiArIDEpCiAgICAgICAgY1trXSA8LSBjW2tdIC0gMQogICAgfQoKICAgIGkKfQoKUSA8LSBsaXN0KAogICAgYygxLCAyLCAzLCA0LCA1LCA2LCA3LCA4LCA5KSwKICAgIGMoMSwgMiwgMywgNCwgNSwgNiwgNywgOSwgOCksCiAgICBjKDEsIDIsIDMsIDQsIDUsIDYsIDgsIDcsIDkpLAogICAgYyg5LCA4LCA3LCA2LCA1LCA0LCAzLCAyLCAxKSwKICAgIE5VTEwsCiAgICBjKDEsIDEsIDEsIDIsIDIsIDIsIDMsIDMsIDMsIDQsIDQsIDQpLAogICAgYygxLCAxLCAxLCAyLCAyLCAyLCAzLCAzLCA0LCAzLCA0LCA0KSwKICAgIGMoMSwgMSwgMSwgMiwgMiwgMiwgMywgMywgNCwgNCwgMywgNCksCiAgICBjKDIsIDIsIDIsIDMsIDMsIDEsIDQsIDMsIDQsIDEsIDEsIDQpLAogICAgYygzLCAyLCA0LCA0LCAyLCA0LCAzLCAzLCAxLCAxLCAxLCAyKSwKICAgIGMoNCwgNCwgNCwgMywgMywgMywgMiwgMiwgMiwgMSwgMSwgMSksCiAgICBOVUxMLAogICAgYygxLCAxLCAxLCAyLCAyLCAyLCAzLCAzLCAzLCA0LCA0LCA0LCA1LCA1LCA1KSwKICAgIGMoMSwgMSwgMSwgMiwgMiwgMiwgMywgMywgMywgNCwgNCwgNSwgNCwgNSwgNSksCiAgICBjKDEsIDEsIDEsIDIsIDIsIDIsIDMsIDMsIDMsIDQsIDQsIDUsIDUsIDQsIDUpLAogICAgYygxLCAxLCAxLCAzLCAzLCAzLCA0LCA0LCAyLCA1LCA0LCA1LCAyLCAyLCA1KSwKICAgIGMoMSwgMSwgMSwgNCwgMywgNSwgNSwgMywgNSwgNCwgNCwgMiwgMiwgMiwgMyksCiAgICBjKDEsIDEsIDEsIDUsIDUsIDUsIDQsIDQsIDQsIDMsIDMsIDMsIDIsIDIsIDIpLAogICAgYyg1LCA1LCA1LCA0LCA0LCA0LCAzLCAzLCAzLCAyLCAyLCAyLCAxLCAxLCAxKSwKICAgIE5VTEwsCiAgICBjKDEsIDEsIDEsIDEsIDEsIDIsIDIsIDIsIDIsIDIsIDMsIDMsIDMsIDMsIDMsIDQsIDQsIDQsIDQsIDQsIDUsIDUsIDUsIDUsIDUsIAogICAgICA2LCA2LCA2LCA2LCA2LCA3LCA3LCA3LCA3LCA3LCA4LCA4LCA4LCA4LCA4LCA5LCA5LCA5LCA5LCA5LCAxMCwgMTAsIDEwLCAxMCwgMTApLAogICAgYygxLCAxLCAxLCAxLCAxLCAyLCAyLCAyLCAyLCAyLCAzLCAzLCAzLCAzLCAzLCA0LCA0LCA0LCA0LCA0LCA1LCA1LCA1LCA1LCA1LAogICAgICA2LCA2LCA2LCA2LCA2LCA3LCA3LCA3LCA3LCA3LCA4LCA4LCA4LCA4LCA4LCA5LCA5LCA5LCA5LCAxMCwgOSwgMTAsIDEwLCAxMCwgMTApLAogICAgYygxLCAxLCAxLCAxLCAxLCAyLCAyLCAyLCAyLCAyLCAzLCAzLCAzLCAzLCAzLCA0LCA0LCA0LCA0LCA0LCA1LCA1LCA1LCA1LCA1LAogICAgICA2LCA2LCA2LCA2LCA2LCA3LCA3LCA3LCA3LCA3LCA4LCA4LCA4LCA4LCA4LCA5LCA5LCA5LCA5LCAxMCwgMTAsIDksIDEwLCAxMCwgMTApLAogICAgYygxLCAxLCAxLCAxLCAxLCAyLCAyLCAyLCAyLCAyLCAzLCAzLCAzLCAzLCAzLCA0LCA0LCA0LCA0LCA0LCA1LCA1LCA1LCA1LCA1LAogICAgICA2LCA2LCA2LCA2LCA2LCA3LCA3LCA3LCA3LCA3LCA4LCA5LCA5LCAxMCwgMTAsIDgsIDgsIDksIDgsIDgsIDksIDEwLCAxMCwgMTAsIDkpLAogICAgYygxLCAxLCAxLCAxLCAxLCAyLCAyLCAyLCAyLCAyLCAzLCAzLCAzLCAzLCAzLCA0LCA0LCA0LCA0LCA0LCA1LCA1LCA1LCA1LCA1LAogICAgICA2LCA2LCA2LCA2LCA2LCA3LCA3LCA3LCA3LCA3LCA4LCAxMCwgMTAsIDksIDgsIDgsIDksIDEwLCAxMCwgOCwgOSwgMTAsIDksIDgsIDkpLAogICAgYygxMCwgMTAsIDEwLCAxMCwgMTAsIDksIDksIDksIDksIDksIDgsIDgsIDgsIDgsIDgsIDcsIDcsIDcsIDcsIDcsIDYsIDYsIDYsIDYsIDYsCiAgICAgIDUsIDUsIDUsIDUsIDUsIDQsIDQsIDQsIDQsIDQsIDMsIDMsIDMsIDMsIDMsIDIsIDIsIDIsIDIsIDIsIDEsIDEsIDEsIDEsIDEpLAogICAgTlVMTCwKICAgIGMoMywgMSwgNCwgMSwgNSwgOSkKKQoKZm9yIChxIGluIFEpIHsKICAgIGlmIChsZW5ndGgocSkpIHsKICAgICAgICBwcmludGYoIuWFpeWKmzogWyVzXVxuIiwgdG9TdHJpbmcocSkpCiAgICAgICAgcHJpbnRmKCLlh7rlips6ICVzXG4iLCBmb3JtYXQoaXRoRHVwbGljYXRlZFBlcm11dGF0aW9uSW52KHEpKSkKICAgIH0KICAgIHByaW50ZigiXG4iKQp9