Submission #105373

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
105373	2019-04-11 14:53:11	gs14004	Phibonacci (kriii2_P)	C++17	4 / 4	3 ms	628 KiB

P

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<lint, lint> pi;
const int mod = 1e9 + 7;
lint ipow(lint x, lint p){
  lint ret = 1, piv = x;
  while(p){
    if(p & 1) ret = ret * piv % mod;
    piv = piv * piv % mod;
    p >>= 1;
  }
  return ret;
}
vector<int> berlekamp_massey(vector<int> x){
  vector<int> ls, cur;
  int lf, ld;
  for(int i=0; i<x.size(); i++){
    lint t = 0;
    for(int j=0; j<cur.size(); j++){
      t = (t + 1ll * x[i-j-1] * cur[j]) % mod;
    }
    if((t - x[i]) % mod == 0) continue;
    if(cur.empty()){
      cur.resize(i+1);
      lf = i;
      ld = (t - x[i]) % mod;
      continue;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

P.cpp: In function 'std::vector<int> berlekamp_massey(std::vector<int>)':
P.cpp:20:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<x.size(); i++){
               ~^~~~~~~~~
P.cpp:22:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<cur.size(); j++){
                ~^~~~~~~~~~~
P.cpp:37:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<cur.size(); j++){
                ~^~~~~~~~~~~
P.cpp: In function 'int guess_nth_term(std::vector<int>, lint)':
P.cpp:82:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(n < x.size()) return x[n];
     ~~^~~~~~~~~~
P.cpp: In function 'std::vector<int> berlekamp_massey(std::vector<int>)':
P.cpp:32:30: warning: 'ld' may be used uninitialized in this function [-Wmaybe-uninitialized]
   lint k = -(x[i] - t) * ipow(ld, mod - 2) % mod;
                          ~~~~^~~~~~~~~~~~~
P.cpp:33:18: warning: 'lf' may be used uninitialized in this function [-Wmaybe-uninitialized]
   vector<int> c(i-lf-1);
                 ~^~~

• Subtask 1: 1 / 1
• Subtask 2: 3 / 3