数学题-零点式转换为一般式Know your Aliens

CF网址 Know your Aliens

题目描述

Our world has been invaded by shapeshifting aliens that kidnap people and steal their identities.You are an inspector from a task force dedicated to detect and capture them. As such, you were given special tools to detect aliens and differentiate them from real humans. Your current mission is to visit a city that is suspected of have been invaded, secretly inspect every person there so as to know whose are aliens and whose aren’t, and report it all to Headquarters. Then they can send forces to the city by surprise and capture all the aliens at once. The aliens are aware of the work of inspectors like you, and are monitoring all radio channels to detect the transmission of such reports, in order to anticipate any retaliation. Therefore, there have been several efforts to encrypt the reports, and the most recent method uses polynomials.

The city you must visit has N citizens, each identified by a distinct even integer from 2 to 2N. You want to find a polynomial P such that, for every citizen i, P(i) > 0 if citizen i is

a human, and P(i) < 0 otherwise. This polynomial will be transmitted to the Headquarters.With the aim of minimizing bandwidth, the polynomial has some additional requirements:each root and coefficient must be an integer, the coefficient of its highest degree term must be either 1 or −1, and its degree must be the lowest possible.

For each citizen, you know whether they’re a human or not. Given this information, you must find a polynomial that satisfies the described constraints.

输入

The input consists of a single line that contains a string S of length N (1 ≤ N ≤ 104),where N is the population of the city. For i = 1, 2, . . . , N, the i-th character of S is either the uppercase letter “H” or the uppercase letter “A”, indicating respectively that citizen 2i is a human or an alien.

输出

The first line must contain an integer D indicating the degree of a polynomial that satisfies the described constraints. The second line must contain D + 1 integers representing the coefficients of the polynomial, in decreasing order of the corresponding terms. It’s guaranteed that there exists at least one solution such that the absolute value of each coefficient is less than 263.

样例输入

【样例1】
HHH
【样例2】
AHHA
【样例3】
AHHHAH

样例输出

【样例1】
0
1
【样例2】
2
-1 10 -21
【样例3】
3
1 -23 159 -297

题目大意

给出一个字符串（下标从1开始），要构造一个一元n次多项式f(x)，使得在字符串中位置为’A’的对应下标的二倍 2×i 处的函数值f(2i) < 0, 而在字符对应为’H’对应的下标的二倍 2 × i处的函数值 f(2i) > 0

而且要使得零点以及系数全部为整数（each root and coefficient must be an integer），并且要最高项的系数是 1 or -1

（the coefficient of its highest degree term must be either 1 or −1,）并且还要使得最高项的系数尽可能的小（its degree must be the lowest possible）我tmd当时怎么就没看见第一个条件呢

这样一来，如果相邻的两个字符不相同，那么必然就有一个零点，并且零点为整数，那么来讲，相邻的两个下标2i 2(i+1)之间必然有一个零点，所以这个零点就必然是 2 * i + 1

这个题主要用到了韦达定理：

关于符号问题，如果极端的考虑一下，就是下图：

因为a_n不是1就是-1所以导致后面的a_n-1以及a_n-2等非常好求

不开long long直接卡掉，CFwa1

string s;
ll x[maxn];
ll b[maxn];
int cnt;
void _Get_x(){
    int len = s.size();
    for(int i=1;i < len-1;i++){
        if(s[i] != s[i+1]) x[++cnt] = 2*i+1;
    }
    cout<<cnt<<endl;
}
void _Get_xi(){
    for(int i=1;i<= cnt;i++){
        for(int j=i+1;j>=1;j--){
            b[j] = b[j - 1];
        }
        for(int j=1;j<=i;j++){
            b[j] += b[j+1] * x[i];
        }
    }
}
int main()
{
    b[1] = 1;
    cin >> s;
    s = 'a' + s;
    _Get_x();
    _Get_xi();
    int oper = 1;
    if(s[1] == 'H' && cnt % 2) oper *= -1;
    if(s[1] == 'A' && cnt % 2 == 0) oper *= -1;
    for(int i=cnt + 1;i >= 1;i --){
        printf("%lld",b[i]*oper);
        oper *= -1;
        if(i != 1) printf(" ");
    }
    return 0;
}