QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#122897 | #1816. Multiple Parentheses | solemntee | AC ✓ | 1210ms | 119772kb | C++20 | 8.5kb | 2023-07-11 14:03:05 | 2023-07-11 14:03:06 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
typedef long long ll;
class Cipolla
{
int P, I2{};
using pll=pair<ll, ll>;
#define X first
#define Y second
ll mul(ll a, ll b)const{return a*b%P;}
pll mul(pll a, pll b)const{return {(a.X*b.X+I2*a.Y%P*b.Y)%P,(a.X*b.Y+a.Y*b.X)%P};}
template<class T>T POW(T a,int b,T x)
{
for(;b;b>>=1,a=mul(a,a))
if(b&1)x=mul(x,a);
return x;
}
public:
Cipolla(int p=0):P(p){}
pair<int,int>sqrt(int n)
{
int a=rand(),x;
if (!(n%=P))return{0,0};
if (POW(n,(P-1)>>1,1)==P-1)return {-1, -1};
while(POW(I2 =((ll)a*a-n+P)%P,(P-1)>>1,1)==1)a=rand();
x=(int)POW(pll{a,1},(P+1)>>1, {1,0} ).X;
if(2*x>P)x=P-x;
return{x,P-x};
}
#undef X
#undef Y
};
const int mod=998244353;
using Poly = vector<int>;
using MultiPoly = vector<Poly>;
void add(int &x,int y){x+=y;if(x>=mod)x-=mod;}
void del(int &x,int y){x-=y;if(x<0)x+=mod;}
int mul(int x,int y){return 1ll*x*y%mod;}
int POW(ll a,int b=mod-2,ll x=1)
{
for(;b;b>>=1,a=a*a%mod)
if(b&1)x=x*a%mod;
return x;
}
Poly getInv(int L)
{
Poly inv(L);
inv[1] = 1;
for(int i=2;i<=L-1;i++)
inv[i]=mul((mod-mod/i),inv[mod%i]);
return inv;
}
auto inv=getInv(N); // NOLINT
namespace NTT
{
const int g=3;
Poly Omega(int L)
{
int wn=POW(g,mod/L);
Poly w(L);
w[L>>1]=1;
for(int i=L/2+1;i<=L-1;i++)w[i]=mul(w[i-1],wn);
for(int i=L/2-1;i>=1;i--)w[i]=w[i<<1];
return w;
}
auto W=Omega(1<<22); // NOLINT
///998244353->r*2^23+1 w_max=23
///1004535809->r*2^21+3 w_max=21
///这边w要随N变大!!!
void DIF(int *a,int n)
{
for(int k=n>>1;k;k>>=1)
for(int i=0,y;i<n;i+=k<<1)
for(int j=0;j<k;++j)
{
y=a[i+j+k];
a[i+j+k]=mul(a[i+j]-y+mod,W[k+j]);
add(a[i+j],y);
}
}
void IDIT(int *a,int n)
{
for(int k=1;k<n;k<<=1)
for(int i=0,x,y;i<n;i+=k<<1)
for(int j=0;j<k;++j)
{
x=a[i+j];
y=mul(a[i+j+k],W[k+j]);
a[i+j+k]=x-y<0?x-y+mod:x-y;
add(a[i+j],y);
}
int Inv=mod-(mod-1)/n;
for(int i=0;i<=n-1;i++)a[i]=mul(a[i],Inv);
reverse(a+1,a+n);
}
}
/*---------------------------------------------------------------------------*/
namespace Polynomial
{
// basic operator
int norm(int n)
{
return 1<<(__lg(n-1)+1);
}
void norm(Poly &a)
{
if(!a.empty())a.resize(norm(a.size()),0);
else a={0};
}
void DFT(Poly &a)
{
NTT::DIF(a.data(),a.size());
}
void IDFT(Poly &a)
{
NTT::IDIT(a.data(),a.size());
}
Poly &dot(Poly &a, Poly &b)
{
for(int i=0;i<a.size();i++)a[i]=mul(a[i],b[i]);
return a;
}
// mul / div int
Poly &operator*=(Poly &a, int b)
{
for(auto &x:a)x=mul(x,b);return a;
}
Poly operator*(Poly a, int b)
{
return a*=b;
}
Poly operator*(int a, Poly b)
{
return b*a;
}
Poly &operator/=(Poly &a, int b)
{
return a*=POW(b);
}
Poly operator/(Poly a, int b)
{
return a/=b;
}
// Poly add / sub
Poly &operator+=(Poly &a, Poly b)
{
a.resize(max(a.size(),b.size()));
for(int i=0;i<b.size();i++)add(a[i], b[i]);
return a;
}
Poly operator+(Poly a, Poly b)
{
return a+=b;
}
Poly &operator-=(Poly &a, Poly b)
{
a.resize(max(a.size(),b.size()));
for(int i=0;i<b.size();i++)
del(a[i], b[i]);
return a;
}
Poly operator-(Poly a, Poly b)
{
return a-=b;
}
// Poly mul
Poly operator*(Poly a, Poly b)
{
int n=a.size()+b.size()-1,L=norm(n);
if (a.size()<=8||b.size()<=8)
{
Poly c(n);
for(int i=0;i<a.size();i++)
for(int j=0;j<b.size();j++)
c[i+j]=(c[i+j]+(ll)a[i]*b[j])%mod;
return c;
}
a.resize(L),b.resize(L);
DFT(a),DFT(b),dot(a, b),IDFT(a);
return a.resize(n),a;
}
// Poly inv
Poly Inv2k(Poly a)
{
// |a| = 2 ^ k
int n=a.size(),m=n>>1;
if(n==1)return {POW(a[0])};
Poly b=Inv2k(Poly(a.begin(),a.begin()+m)),c=b;
b.resize(n),DFT(a),DFT(b),dot(a,b),IDFT(a);
for(int i=0;i<=n-1;i++)a[i]=i<m?0:mod-a[i];
DFT(a),dot(a,b),IDFT(a);
return move(c.begin(),c.end(),a.begin()),a;
}
Poly Inv(Poly a)
{
int n=a.size();
norm(a),a=Inv2k(a);
return a.resize(n),a;
}
// Poly div / mod
Poly operator/(Poly a,Poly b)
{
int k=a.size()-b.size()+1;
if(k<0)return {0};
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
b.resize(k),a=a*Inv(b);
a.resize(k),reverse(a.begin(),a.end());
return a;
}
pair<Poly,Poly>operator%(Poly a,const Poly& b)
{
Poly c=a/b;
a-=b*c,a.resize(b.size()-1);
return {c,a};
}
// Poly calculus
Poly deriv(Poly a)
{
for(int i=1;i<a.size();i++)a[i-1]=mul(i,a[i]);
return a.pop_back(),a;
}
Poly integ(Poly a)
{
a.push_back(0);
for(int i=(int)a.size()-1;i>=1;i--)a[i]=mul(inv[i],a[i-1]);
return a[0]=0,a;
}
// Poly ln
//a[0]=1!!!!!
Poly Ln(Poly a)
{
int n=a.size();
a=deriv(a)*Inv(a);
return a.resize(n - 1),integ(a);
}
// Poly exp
//a[0]=0!!!!!
Poly Exp(Poly a)
{
int n=a.size(),k=norm(n);
Poly b = {1},c,d;
a.resize(k);
for(int L=2;L<=k;L<<=1)
{
d=b,b.resize(L),c=Ln(b),c.resize(L);
for(int i=0;i<=L-1;i++)c[i]=a[i]-c[i]+(a[i]<c[i]?mod:0);
add(c[0],1);
DFT(b), DFT(c),dot(b, c),IDFT(b);
move(d.begin(),d.end(),b.begin());
}
return b.resize(n),b;
}
// Poly sqrt
Poly Sqrt(Poly a)
{
int n=a.size(),k=norm(n);a.resize(k);
Poly b={(new Cipolla(mod))->sqrt(a[0]).first,0},c;
for(int L=2;L<=k;L<<=1)
{
b.resize(L);
c=Poly(a.begin(),a.begin()+L)*Inv2k(b);
for(int i=L/2;i<=L-1;i++)b[i]=mul(c[i],(mod+1)/2);
}
return b.resize(n),b;
}
// Poly pow
Poly Pow(Poly &a, int b)
{
return Exp(Ln(a)*b);// a[0] = 1
}
Poly Pow(Poly a, int b1, int b2) { // b1 = b % P, b2 = b % phi(P) and b >= n iff a[0] > 0
int n=a.size(),d=0,k;
while(d<n&&!a[d])++d;
if((ll)d*b1>=n)return Poly(n);
a.erase(a.begin(),a.begin()+d);
k=POW(a[0]),norm(a*=k);
a=Pow(a,b1)*POW(k,mod-1-b2);
a.resize(n),d*= b1;
for(int i=n-1;i>=0;i--)a[i]=i>=d?a[i-d]:0;
return a;
}
// Get [x ^ k](f / g)
int divAt(Poly f,Poly g,ll k)
{
int n=max(f.size(),g.size()),m=norm(n);
for (;k;k>>=1)
{
f.resize(m*2,0),DFT(f);
g.resize(m*2,0),DFT(g);
for(int i=0;i<=2*m-1;i++)f[i]=mul(f[i],g[i^1]);
for(int i=0;i<=m-1;i++)g[i]=mul(g[2*i],g[2*i+1]);
g.resize(m),IDFT(f),IDFT(g);
for(int i=0,j=k&1;i<n;i++,j+=2)f[i]=f[j];
f.resize(n),g.resize(n);
}
return f[0];
}
// Get a[k] by a[n] = sum c[i] * a[n - i]
int LinearRecur(Poly a, Poly c, ll k)
{
c[0]=mod-1,a=a*c,a.resize(c.size()-1);
return divAt(a,c,k);
}
}
using namespace Polynomial;
const int M=2e6+50;
int P1[M],P2[M];
typedef long long ll;
ll poww(ll a,ll b){
ll t=1;
while(b){
if(b&1)t=t*a%mod;
a=a*a%mod;
b>>=1;
}
return t;
}
void init(int tot){
P1[0]=1;
for(int i=1;i<=tot;i++)P1[i]=1ll*P1[i-1]*i%mod;
P2[tot]=poww(P1[tot],mod-2);
for(int i=tot-1;i>=0;i--)P2[i]=1ll*P2[i+1]*(i+1)%mod;
}
int C(int n,int m){
return 1ll*P1[n]*P2[m]%mod*P2[n-m]%mod;
}
int main(){
init(2000000);
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
Poly P(m+1);
P[0]=1;
for(int i=1;i<=m;i++)if(i!=k){
P[i]=C(2*i,i);
del(P[i],C(2*i,i-1));
//printf("p[%d]=%d\n",i,P[i]);
}
auto ans=Pow(P,n);
printf("%d",ans[m]);
}
詳細信息
Test #1:
score: 100
Accepted
time: 39ms
memory: 42780kb
input:
2 2 1
output:
4
result:
ok answer is '4'
Test #2:
score: 0
Accepted
time: 36ms
memory: 42744kb
input:
1 1 1
output:
0
result:
ok answer is '0'
Test #3:
score: 0
Accepted
time: 33ms
memory: 43224kb
input:
24 120 30
output:
379268651
result:
ok answer is '379268651'
Test #4:
score: 0
Accepted
time: 34ms
memory: 43236kb
input:
1451 1598 1130
output:
884873572
result:
ok answer is '884873572'
Test #5:
score: 0
Accepted
time: 36ms
memory: 43228kb
input:
1324 1742 1033
output:
856733047
result:
ok answer is '856733047'
Test #6:
score: 0
Accepted
time: 38ms
memory: 43184kb
input:
1378 1614 1335
output:
869903701
result:
ok answer is '869903701'
Test #7:
score: 0
Accepted
time: 29ms
memory: 43196kb
input:
1071 1907 1281
output:
327700529
result:
ok answer is '327700529'
Test #8:
score: 0
Accepted
time: 37ms
memory: 43104kb
input:
1204 1337 1277
output:
475981175
result:
ok answer is '475981175'
Test #9:
score: 0
Accepted
time: 31ms
memory: 43176kb
input:
146 246 100
output:
404402509
result:
ok answer is '404402509'
Test #10:
score: 0
Accepted
time: 40ms
memory: 43124kb
input:
226 183 144
output:
351921989
result:
ok answer is '351921989'
Test #11:
score: 0
Accepted
time: 34ms
memory: 42796kb
input:
234 287 158
output:
658959115
result:
ok answer is '658959115'
Test #12:
score: 0
Accepted
time: 40ms
memory: 42748kb
input:
242 156 122
output:
325586111
result:
ok answer is '325586111'
Test #13:
score: 0
Accepted
time: 35ms
memory: 42792kb
input:
168 271 135
output:
181613866
result:
ok answer is '181613866'
Test #14:
score: 0
Accepted
time: 36ms
memory: 42792kb
input:
22 25 1
output:
684860973
result:
ok answer is '684860973'
Test #15:
score: 0
Accepted
time: 36ms
memory: 42732kb
input:
45 22 15
output:
217501624
result:
ok answer is '217501624'
Test #16:
score: 0
Accepted
time: 36ms
memory: 42808kb
input:
47 29 16
output:
690840771
result:
ok answer is '690840771'
Test #17:
score: 0
Accepted
time: 40ms
memory: 42688kb
input:
2 25 25
output:
660660974
result:
ok answer is '660660974'
Test #18:
score: 0
Accepted
time: 37ms
memory: 42668kb
input:
32 34 11
output:
133387056
result:
ok answer is '133387056'
Test #19:
score: 0
Accepted
time: 138ms
memory: 52076kb
input:
88196 118335 104471
output:
7192211
result:
ok answer is '7192211'
Test #20:
score: 0
Accepted
time: 82ms
memory: 47788kb
input:
142215 57117 51272
output:
627598793
result:
ok answer is '627598793'
Test #21:
score: 0
Accepted
time: 94ms
memory: 47960kb
input:
102255 60360 51525
output:
447649003
result:
ok answer is '447649003'
Test #22:
score: 0
Accepted
time: 143ms
memory: 51612kb
input:
132449 83413 54230
output:
215816803
result:
ok answer is '215816803'
Test #23:
score: 0
Accepted
time: 139ms
memory: 51732kb
input:
68499 95762 77190
output:
393029560
result:
ok answer is '393029560'
Test #24:
score: 0
Accepted
time: 1135ms
memory: 112572kb
input:
751951 751951 1
output:
804170883
result:
ok answer is '804170883'
Test #25:
score: 0
Accepted
time: 32ms
memory: 43312kb
input:
804420 1962 410
output:
869056555
result:
ok answer is '869056555'
Test #26:
score: 0
Accepted
time: 94ms
memory: 47892kb
input:
828607 63739 13
output:
926542030
result:
ok answer is '926542030'
Test #27:
score: 0
Accepted
time: 65ms
memory: 45432kb
input:
472167 20529 23
output:
142703540
result:
ok answer is '142703540'
Test #28:
score: 0
Accepted
time: 527ms
memory: 78304kb
input:
363438 363438 1
output:
764563597
result:
ok answer is '764563597'
Test #29:
score: 0
Accepted
time: 1132ms
memory: 117024kb
input:
1000000 1000000 628333
output:
283487375
result:
ok answer is '283487375'
Test #30:
score: 0
Accepted
time: 1154ms
memory: 117236kb
input:
1000000 1000000 900084
output:
651386967
result:
ok answer is '651386967'
Test #31:
score: 0
Accepted
time: 1210ms
memory: 119772kb
input:
1000000 1000000 27328
output:
621963453
result:
ok answer is '621963453'
Test #32:
score: 0
Accepted
time: 1125ms
memory: 117604kb
input:
1000000 1000000 538409
output:
997879100
result:
ok answer is '997879100'
Test #33:
score: 0
Accepted
time: 1168ms
memory: 117732kb
input:
1000000 1000000 928121
output:
964724707
result:
ok answer is '964724707'
Test #34:
score: 0
Accepted
time: 1130ms
memory: 111360kb
input:
685624 665877 563708
output:
257429683
result:
ok answer is '257429683'
Test #35:
score: 0
Accepted
time: 1134ms
memory: 115772kb
input:
692290 942095 553970
output:
82511143
result:
ok answer is '82511143'
Test #36:
score: 0
Accepted
time: 1163ms
memory: 112536kb
input:
579579 765702 631728
output:
954001361
result:
ok answer is '954001361'
Test #37:
score: 0
Accepted
time: 1140ms
memory: 110824kb
input:
756854 634736 567170
output:
393747028
result:
ok answer is '393747028'
Test #38:
score: 0
Accepted
time: 1142ms
memory: 117052kb
input:
649175 997874 511181
output:
242172216
result:
ok answer is '242172216'
Test #39:
score: 0
Accepted
time: 1141ms
memory: 117148kb
input:
786431 1000000 999999
output:
627359027
result:
ok answer is '627359027'