2016 TCO Algorithm Round 2B easy: TriangleTriples

はぁ…

問題

TopCoder Statistics - Problem Statement

A, B, C が与えられる。1 <= a <= A, 1 <= b <= B, 1 <= c <= C を満たす (a, b, c) の組で, この組が三角形の各辺に対応するようなものの場合の数を求めよ。

解法

三角形の辺の組としてあり得ないものを数え, それを A*B*C から引く, というように考えます。あり得ない辺の組としては,

• a が最大のもの(a >= b+c を満たす)
• b が最大のもの(b >= c+a を満たす)
• c が最大のもの(c >= a+b を満たす)

を考えれば良いです。これらはすべて独立しているので, 例えば c が最大のものを求めるアルゴリズムができれば, 後は同じようにやれば良いです。

で, これは三角錐の格子点を数え上げる問題になります。

小さい二つの三角錐が交わったら, その分は足しこみましょう。

本番はこれを三角錐の問題と考えないで 0 -> min(A, B) -> max(A, B) -> A+B と分割して考えて死んでました。計算できそう(というか実際にそれで通している人がいる)から困る。

const int MOD = 1e9+7;
ll mod_pow(ll x, ll p, ll MOD) {
    ll a = 1;
    while (p) {
        if (p%2) a = a*x%MOD;
        x = x*x%MOD;
        p/=2;
    }
    return a;
}

// mod_inverse
ll mod_inverse(ll a, ll m) {
    return mod_pow(a, m-2, m);
}

ll f(ll x) {
    if (x < 0) return 0;
    x--;
    return x*(x+1)%MOD*(x+2)%MOD*mod_inverse(6, MOD)%MOD;
}

ll calc(ll A, ll B, ll C) {
    ll ret = f(C)-f(C-A)-f(C-B)+f(C-A-B);
    ret = (ret%MOD + MOD)%MOD;
    return ret;
}

class TriangleTriples {
public:
    int count(int A, int B, int C) {
        ll sum = A;
        (sum *= B) %= MOD;
        (sum *= C) %= MOD;
        ll minus = 0;
        minus += calc(A, B, C);
        minus += calc(B, C, A);
        minus += calc(C, A, B);
        minus %= MOD;
        sum = (sum+MOD-minus)%MOD;
        return (int)sum;
    }
};