原问题 CF1548C

有多项式做法 答案为

题解里说分母次数比较低的情况可以暴力$O(n)$计算多项式的系数,代码如下.

    a[0] = -1;
    a[1] = -3;
    a[2] = -3;
    a[3] = -1;
    for (int i = 0; i <= 3 * n + 3; i++)
        a[i] += C(3 * n + 3, i);
    for (int i = 3 * n + 3; i >= 3; i--)
    {
        ans[i - 3] = a[i];
        a[i - 1] = ((a[i - 1] - 3 * a[i] + MOD) % MOD + MOD) % MOD;
        a[i - 2] = ((a[i - 2] - 3 * a[i] + MOD) % MOD + MOD) % MOD;
    }

给$a$赋值的部分可以看出来是计算分子的系数，但是看不太懂下面的循环里是怎么暴力做多项式除法的...