QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#91353 | #547. BM 算法 | Crysfly# | WA | 47ms | 3840kb | C++11 | 3.6kb | 2023-03-28 17:14:31 | 2023-03-28 17:14:35 |
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.
- [2023-03-28 17:14:31]
- Submitted
answer
#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define ll long long
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
#define mod 998244353
struct modint{
int x;
modint(int o=0){x=o;}
modint &operator = (int o){return x=o,*this;}
modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
modint &operator ^=(int b){
modint a=*this,c=1;
for(;b;b>>=1,a*=a)if(b&1)c*=a;
return x=c.x,*this;
}
modint &operator /=(modint o){return *this *=o^=mod-2;}
modint &operator +=(int o){return x=x+o>=mod?x+o-mod:x+o,*this;}
modint &operator -=(int o){return x=x-o<0?x-o+mod:x-o,*this;}
modint &operator *=(int o){return x=1ll*x*o%mod,*this;}
modint &operator /=(int o){return *this *= ((modint(o))^=mod-2);}
template<class I>friend modint operator +(modint a,I b){return a+=b;}
template<class I>friend modint operator -(modint a,I b){return a-=b;}
template<class I>friend modint operator *(modint a,I b){return a*=b;}
template<class I>friend modint operator /(modint a,I b){return a/=b;}
friend modint operator ^(modint a,int b){return a^=b;}
friend bool operator ==(modint a,int b){return a.x==b;}
friend bool operator !=(modint a,int b){return a.x!=b;}
bool operator ! () {return !x;}
modint operator - () {return x?mod-x:0;}
};
vector<modint> fac,ifac,iv;
inline void initC(int n)
{
if(iv.empty())fac=ifac=iv=vector<modint>(2,1);
int m=iv.size(); ++n;
if(m>=n)return;
iv.resize(n),fac.resize(n),ifac.resize(n);
For(i,m,n-1){
iv[i]=iv[mod%i]*(mod-mod/i);
fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*iv[i];
}
}
inline modint C(int n,int m){
if(m<0||n<m)return 0;
return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
inline modint sign(int n){return (n&1)?(mod-1):(1);}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
#define maxn 10005
#define inf 0x3f3f3f3f
#define poly vector<modint>
int n,m;
modint h[maxn];
poly BM(modint*a,int n)
{
poly res,lst;
modint delt=0;
int w=0;
For(i,1,n){
modint t=0;
for(int j=0;j<res.size();++j)
t+=res[j]*a[i-1-j];
if(a[i].x==t.x)continue;
if(!w){
w=i,delt=a[i]-t;
res.resize(i);continue;
}
poly now=res;
modint mul=(a[i]-t)/delt;
if(res.size()<lst.size()+i-w) res.resize(lst.size()+i-w);
res[i-w-1]+=mul;
for(int j=0;j<lst.size();++j)
res[i-w+j]-=mul*lst[j];
if(now.size()-i<lst.size()-w)
lst=now,w=i,delt=a[i]-t;
}
return res;
}
modint ans[maxn],g[maxn],p[maxn],tmp[maxn];
void mul(modint*a,modint*b,modint*c,int k){
For(i,0,2*k)tmp[i]=0;
For(i,0,k-1)For(j,0,k-1)tmp[i+j]+=a[i]*b[j];
Rep(i,2*k,k)if(tmp[i].x)Rep(j,k,0)tmp[i-j]+=tmp[i]*p[j];
For(i,0,2*k-1)c[i]=tmp[i];
}
modint calc(int m,poly f,modint*a)
{
if(m<=f.size())return a[m-1];
int k=f.size();
p[0]=mod-1;
For(i,1,k)p[i]=f[i-1];
For(i,0,2*k)ans[i]=g[i]=0;
ans[0]=1;
if(k>1) g[1]=1; else g[0]=p[0];
for(;m;m>>=1,mul(g,g,g,k))if(m&1)mul(ans,g,ans,k);
modint res=0;
For(i,0,k-1) res+=a[i+1]*ans[i];
return res;
}
signed main()
{
n=read();
For(i,1,n) h[i]=read();
poly f=BM(h,n);
for(auto x:f) cout<<x.x<<" "; puts("");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 47ms
memory: 3840kb
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:
519996520 676098795 636816471 494383311 88254187 542188011 442632990 847848618 639292958 22724161 734302549 364991396 926096346 988368003 304154451 342281483 623977164 383132553 297361731 782343399 865656753 547123615 620909076 813317753 466953279 371327965 118623130 665641245 786523122 671100455 65...
result:
wrong answer you didn't minimize k