QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#122897#1816. Multiple ParenthesessolemnteeAC ✓1210ms119772kbC++208.5kb2023-07-11 14:03:052023-07-11 14:03:06

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-11 14:03:06]
  • 评测
  • 测评结果:AC
  • 用时:1210ms
  • 内存:119772kb
  • [2023-07-11 14:03:05]
  • 提交

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]);

}

Details

Tip: Click on the bar to expand more detailed information

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'