[原创]51nod 1718 Cos的多项式 【数学】

Tabris

CSDN数学51nod

发布于：2017年4月21日

次浏览

[原创]51nod 1718 Cos 的多项式 【数学】

2017-04-21 13:11:03 Tabris_ 阅读数：702

博客爬取于 2020-06-14 22:40:57
以下为正文

版权声明：本文为 Tabris 原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/70313683

题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1718
————————————————————————————————————————————
1718 Cos 的多项式
基准时间限制：1 秒 空间限制：131072 KB 分值： 40 难度：4 级算法题 收藏 关注
小明对三角函数充满了兴趣，有一天他突然发现一个神奇的性质。
2cos(nx)似乎可以表示成 2cos(x)的一个多项式。
但是小明并不能证明它的正确性。
现在给定 n，问是否可以表示成这样的多项式，如果可以，只需输出各项系数的和。（Tip:如果这个和很大，那就高精度咯：)）
否则输出 No

样例解释：2cos(3x)=(2cosx)^3-3*(2*cosx)，系数为 1 和-3，他们的和为-2。
Input
一个数表示 n（n<=1e15)
Output
如果能表示 输出各项系数和
不能 输出 No
Input 示例
3
Output 示例
-2

————————————————————————————————————————————

我们知道

考虑
$2cos((n-1)x) = 2(cos(nx)cos(x)+sin(nx)sin(x) ) $2cos((n+1)x) = 2(cos(nx)cos(x)-sin(nx)sin(x) )

\Rightarrow 2cos((n-1)x)+2cos((n+1)x) = 2cos(nx)\times 2cos(x)

设f(n) = 2cos(nx)
有f(n-1)+f(n+1)=f(n)f(1)\\ \Rightarrow f(n+1)= f(n)f(1) - f(n-1)\\ \Rightarrow f(n+1)= f(n)\times 2cos(x) - f(n-1)\

这样就有了推出所有公式了

然后计算出系数和 震惊的发现其结果竟是有循环节的!!!!

然后打表 AC

附本题代码
————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13

# include <bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int N = 200000+7;

LL n;
int a[6] = {1,-1,-2,-1,1,2};
int main(){
    scanf("%lld",&n);
    printf("%d",a[(n+5)%6]);
    return 0;
}

本页文档最后更新于：2021年5月16日

CSDN

数学

算法