ARC033 D問題

多項式の値、f(0), f(1), …, f(N)が与えられるから、f(T)を出力しろ、という問題。
単純にラグランジェ補間でよい。
逆元を求める際はextgcdとmod_inverseを使ってあげる。

ll mod = (ll)1e9+7;

// extgcd
// ax+by = gcd(a,b)の階を生成する。返り値はgcd(a, b)
// gcd(a,b) == 1のときはx, yが必ず存在している
template<class T>
T extgcd(T a, T b, T& x, T& y) {
    T d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1; y = 0;
    }
    return d;
}

// mod_inverse
// a*x == 1(mod m)となるxを生成する。つまり逆元を求める。
// ただしmが素数の時しか使えない。
// ax = 1+mkを求めることと同値だからextgcdを使っている
template<class T>
T mod_inverse(T a, T m = mod) {
    T x, y;
    extgcd(a, m, x, y);
    return (m+x%m) % m;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll N; cin >> N;
    ll A[N+1];
    for(ll i=0; i<=N; i++){
        cin >> A[i];
    }
    ll T; cin >> T;
    ll C[N+1];
    ll res = 0;
    ll wari = 1;
    ll wari2 = 1;
    for(ll j=0; j<=N; j++){
        wari2 *= (T-j);
        wari2 %= mod;
    }
    while(wari2 < 0) wari2 += mod;
    for(ll i=0; i<=N; i++){
        C[i] = A[i];
        if(i == 0){
            for(ll j=0; j<=N; j++){
                if(i != j){
                    wari *= (i-j);
                    wari %= mod;
                }
            }
        }else{
            wari *= (i-0);
            wari %= mod;
            wari *= mod_inverse((i-1)-N+mod, mod);
            wari %= mod;
        }
        while(wari < 0) wari += mod;
        C[i] *= mod_inverse(wari, mod);
        C[i] %= mod;

        ll tmp = wari2 * mod_inverse(T-i, mod);
        tmp %= mod;
        while(tmp < 0) tmp += mod;

        res += C[i]*tmp;
        res %= mod;
    }
    cout << res << endl;
}