QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#381236 | #8049. Equal Sums | ucup-team2230# | WA | 0ms | 19252kb | C++23 | 3.7kb | 2024-04-07 16:36:21 | 2024-04-07 16:36:23 |
Judging History
answer
#ifndef LOCAL
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#endif
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using uint=unsigned;
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define si(x) int(x.size())
#define a first
#define b second
template<class t>using vc=vector<t>;
template<class t,class u>bool chmax(t&a, u b){ if(a<b){a=b;return 1;}return 0;}
template<class t,class u>bool chmin(t&a,u b){if(a>b){a=b;return 1;}return 0;}
using P=pair<int,int>;
const uint mod=998244353;
struct mint{
uint v;
mint(ll vv=0){s(vv%mod+mod);}
mint& s(uint vv){
v=vv<mod?vv:vv-mod;
return *this;
}
mint operator-()const{return mint()-*this;}
mint&operator+=(mint r){return s(v+r.v);}
mint&operator-=(mint r){return s(v+mod-r.v);}
mint&operator*=(mint r){v=(unsigned long long)v*r.v%mod; return *this;}
mint&operator/=(mint r){return *this*=r.inv();}
mint operator+(mint r)const{return mint(*this)+=r;}
mint operator-(mint r)const{return mint(*this)-=r;}
mint operator*(mint r)const{return mint(*this)*=r;}
mint operator/(mint r)const{return mint(*this)/=r;}
mint pow(ll n)const{
if(n<0)return inv(),pow(-n);
mint res(1),x(*this);
while(n){
if(n&1)res*=x;
x*=x;
n>>=1;
}
return res;
}
mint inv()const{return pow(mod-2);}
};
const mint prim_root=3;
const mint prim_root_inv=prim_root.inv();
void inplace_fmt(vc<mint>&f, const bool inv){
const int n=f.size();
const mint root=inv?prim_root_inv:prim_root;
static vc<mint>g;
g.clear();g.resize(n);
for(int b=n/2;b>=1;b/=2){
mint w=root.pow((mod-1)/(n/b)), p=1;
for(int i=0;i<n;i+=b*2){
rep(j,b){
f[i+j+b]*=p;
g[i/2+j]=f[i+j]+f[i+b+j];
g[n/2+i/2+j]=f[i+j]-f[i+b+j];
}
p*=w;
}
swap(f,g);
}
if(inv){
mint z=mint(n).inv();
rep(i,n)f[i]*=z;
}
}
vc<mint> multiply(vc<mint> a,vc<mint> b){
int n=a.size(),m=b.size();
assert(n>0&&m>0);
int s=1;while(s<n+m-1) s*=2;
a.resize(s);inplace_fmt(a,false);
b.resize(s);inplace_fmt(b,false);
rep(i,s)a[i]*=b[i];inplace_fmt(a,true);
a.resize(n+m-1);return a;
}
void solve(){
int n,m;
cin>>n>>m;
vc<P> A(n),C(m);
/*
for(int i=0;i<n;i++) cin>>A[i].a>>A[i].b;
for(int i=0;i<m;i++){
cin>>C[i].a>>C[i].b;
}*/
for(int i=0;i<n;i++) A[i].a=1,A[i].b=500;
for(int i=0;i<m;i++) C[i].a=1,C[i].b=500;
int M=500;
int B=4*M*M;
vc<mint> dp(2*B);
vc<mint> prev(2*B);
dp[B]=1;
vc<vc<mint>> ans(n+1,vc<mint>(m+1));
auto adda=[&](int l,int r,int x){
for(int i=l;i<=r;i++){
prev[i]=dp[i];
dp[i]=dp[i-1]+prev[i-A[x].a]-prev[i-A[x].b-1];
}
};
auto addc=[&](int l,int r,int x){
for(int i=r;i>=l;i--){
prev[i]=dp[i];
dp[i]=dp[i+1]+prev[i+C[x].a]-prev[i+C[x].b+1];
}
};
vc<vc<mint>> cur(20);
int mx=n+m;
for(int i=0;i<20;i++){
int sz=mx*M*4;
cur[i].resize(sz);
mx=(mx+2)/2;
}
auto rec=[&](int a,int b,int c,int d,int dep,auto self)->void{
if(a==b||c==d) return;
if(a+1==b&&c+1==d){
ans[a][c]=dp[B];
} else{
int L=max(b-a,d-c);
int l=B-M*(b-a),r=B+M*(d-c);
for(int i=l;i<=r;i++) cur[dep][i-l]=dp[i];
int ma=(a+b)/2,mc=(c+d)/2;
self(a,ma,c,mc,dep+1,self);
for(int i=a;i<ma;i++){
adda(l,r,i);
l+=M;
}
self(ma,b,c,mc,dep+1,self);
for(int i=c;i<mc;i++){
addc(l,r,i);
r-=M;
}
self(ma,b,mc,d,dep+1,self);
l=B-M*(b-a),r=B+M*(d-c);
for(int i=l;i<=r;i++) dp[i]=cur[dep][i-l];
for(int i=c;i<mc;i++){
addc(l,r,i);
r-=M;
}
self(a,ma,mc,d,dep+1,self);
for(int i=l;i<=r;i++) dp[i]=cur[dep][i-l];
}
};
rec(0,n+1,0,m+1,0,rec);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cout<<ans[i+1][j+1].v<<" ";
}cout<<endl;
}
}
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
cout<<fixed<<setprecision(20);
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 19252kb
input:
2 3 1 2 2 3 1 4 2 2 1 3
output:
500 124750 20708500 124750 83333500 663751741
result:
wrong answer 1st numbers differ - expected: '2', found: '500'