2006年JOI予選模擬問5

昔のJOIは多倍長好きだったんですかね...

問題文を読むと, 求める答えが n H (r - mn) = (n + r - mn - 1) C (r - mn)であることはあきらか.
あとは, nCk = n! / k!(n - k)!　を実直に計算します. (バグたくさんで悲しみに包まれました.)

頭の悪い多倍長なのでAOJでは当然間に合いません. ((n, m, r) = (10000, 0, 10000)ケースで20秒くらいかかります)

#include <stdio.h>
#include <string.h>

#define BASE (1000000)

int main(void)
{
    int n, m, r;
    int head, tail;
    int i, j;
    static __int64 ans[20000], temp[20000];
    __int64 carry;
    
    tail = sizeof(ans) / sizeof(__int64) - 1;
    
    scanf("%d%d%d", &n, &m, &r);
    
    if (r - m * n < 0 || n + r - m * n - 1 < 0){
        printf("0\n");
    }
    else {
        head = tail;
        ans[tail] = 1;
        
        //nCkを求める. n!
        for (i = 1; i <= n + r - m * n - 1; i++){
            carry = 0;
            for (j = tail; j >= head; j--){
                carry += i * ans[j];
                ans[j] = carry % BASE;
                carry /= BASE;
            }
            while (carry != 0){
                ans[--head] = carry % BASE;
                carry /= BASE;
            }
        }
        
        
        //k!
        for (i = r - m * n; i >= 2; i--){
            memcpy(temp, ans, sizeof(ans));
            carry = 0;
            for (j = head; j <= tail; j++){
                carry = carry * BASE + temp[j];
                ans[j] = carry / i;
                carry %= i;
            }
        }
        
        //(n - k)!
        for (i = n - 1; i >= 2; i--){
            memcpy(temp, ans, sizeof(ans));
            carry = 0;
            for (j = head; j <= tail; j++){
                carry = carry * BASE + temp[j];
                ans[j] = carry / i;
                carry %= i;
            }
        }
        
        while (ans[head] == 0){
            head++;
        }
        
        
        for (i = head; i <= tail; i++){
            if (i != head){
                printf("%06I64d", ans[i]);
            }
            else {
                printf("%I64d", ans[i]);
            }
        }
        printf("\n");
    }
    
    return (0);
}