QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#44780 | #547. BM 算法 | He_Ren# | WA | 211ms | 3852kb | C++14 | 1.1kb | 2022-08-21 16:28:19 | 2022-08-21 16:28:19 |
Judging History
This is the latest submission verdict.
- [2024-12-28 21:37:58]
- hack成功,自动添加数据
- (/hack/1317)
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2022-08-21 16:28:19]
- Submitted
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int mod = 998244353;
inline void add_mod(int &a,int b){ a+=b; if(a>=mod) a-=mod;}
inline ll pw(ll a,ll b)
{
ll res = 1;
while(b)
{
if(b&1) res=res*a%mod;
a=a*a%mod; b>>=1;
}
return res;
}
vector<int> Berlekamp_Massey(const vector<int> &a)
{
int n = (int)a.size(), len = 0, d = 0, ld = 1, m = 0;
vector<int> res(n), lst(n), tmp;
res[0] = 1;
for(int i=0; i<n; ++i)
{
++m; d = 0;
for(int j=0; j<=len; ++j)
d = (d + (ll)res[j] * a[i-j]) %mod;
if(!d) continue;
tmp = res;
ll k = (ll)d * pw(ld, mod-2) %mod;
for(int j=m; j<n; ++j)
res[j] = (res[j] - lst[j-m] * k) %mod;
if(len >= i-len+1) continue;
len = i-len+1; lst = res; ld = d; m = 0;
}
res.resize(len+1); res.erase(res.begin());
for(auto &t: res)
add_mod(t = -t, mod);
return res;
}
int main(void)
{
int n;
scanf("%d",&n);
vector<int> a(n);
for(auto &t: a)
scanf("%d",&t);
auto b = Berlekamp_Massey(a);
printf("%d\n",(int)b.size());
for(auto t: b)
printf("%d ",t);
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 211ms
memory: 3852kb
input:
10000 481761257 325845401 89198273 331256176 423285801 510703206 160079009 805700484 2785453 119847482 4456012 47414124 382685410 463638256 314056646 483110670 723760177 473280072 294639899 965560586 243267953 822936984 475063108 193430844 842374415 125382693 569285769 643640101 548245375 253979925 ...
output:
5000 726853717 129727253 975527767 174198152 57717580 521381464 526163079 61218536 684428819 527876619 434055591 225023914 146824049 333898293 877641392 940375562 537500383 468813622 739265136 387881906 724429571 813293171 29894524 812924462 358628608 292463502 836098605 655676136 827581794 89731090...
result:
wrong answer you didn't minimize k