http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2111

由和差化积公式,我们有

即递推式

(只贴出与题目有关的代码,宏定义见 GitHub

const int mx = 50;

ll a[mx][mx + 1];

void init()
{
    a[0][0] = a[1][1] = 1LL;
    int i, j;
    Forr(i, 2, mx)
    {
        a[i][0] = -a[i - 2][0];
        Forr(j, 1, i + 1) a[i][j] = 2 * a[i - 1][j - 1] - a[i - 2][j];
    }
}

// 当n>1时,除了常数项,系数绝对值都是>1的
void printCos(ll *a, int n)
{
    printf("%lldCos^%d(A)", a[n], n);
    int i;
    rForr(i, n - 2, 2) if (a[i]) printf("%+lldCos^%d(A)", a[i], i);
    if (a[1]) printf("%+lldCos(A)", a[1]);
    if (a[0]) printf("%+lld", a[0]);
    Pn();
}

int main()
{
    init();
    int n;
    while (SI(n), n) n == 1 ? (void)puts("Cos(A)") : printCos(a[n], n);
    return 0;
}

Comments

comments powered by Disqus