QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#30098#2811. NoMmyee100 ✓26ms3312kbC++1111.6kb2022-04-24 19:10:452022-04-28 12:26:47

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-28 12:26:47]
  • Judged
  • Verdict: 100
  • Time: 26ms
  • Memory: 3312kb
  • [2022-04-24 19:10:45]
  • Submitted

answer

#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
namespace AnyMod
{
    ullt Mod=-1;
    inline voi ChgMod(ullt v){Mod=v;}
    struct ModInt
    {
        private:
            ullt v;inline ullt chg(ullt w){return(w<Mod)?w:w-Mod;}
            inline ModInt _chg(ullt w){ModInt ans;ans.v=(w<Mod)?w:w-Mod;return ans;}
        public:
            ModInt():v(0){}
            ModInt(ullt v):v(v%Mod){}
            bol empty(){return!v;}
            inline ullt val(){return v;}
            friend bol operator<(ModInt a,ModInt b){return a.v<b.v;}
            friend bol operator>(ModInt a,ModInt b){return a.v>b.v;}
            friend bol operator<=(ModInt a,ModInt b){return a.v<=b.v;}
            friend bol operator>=(ModInt a,ModInt b){return a.v>=b.v;}
            friend bol operator==(ModInt a,ModInt b){return a.v==b.v;}
            friend bol operator!=(ModInt a,ModInt b){return a.v!=b.v;}
            inline friend ModInt operator+(ModInt a,ModInt b){return a._chg(a.v+b.v);}
            inline friend ModInt operator-(ModInt a,ModInt b){return a._chg(a.v+a.chg(Mod-b.v));}
            inline friend ModInt operator*(ModInt a,ModInt b){return a.v*b.v;}
            friend ModInt operator/(ModInt a,ModInt b){return b._power(Mod-2)*a.v;}
            friend ModInt operator^(ModInt a,ullt b){return a._power(b);}
            inline ModInt operator-(){return _chg(Mod-v);}
            ModInt sqrt()
            {
                if(power(v,(Mod-1)>>1,Mod)!=1)return 0;
                ModInt b=1;do b++;while(b._power((Mod-1)>>1)==1);
                ullt t=Mod-1,s=0,k=1;while(!(t&1))s++,t>>=1;
                ModInt x=_power((t+1)>>1),e=_power(t);
                while(k<s)
                {
                    if(e._power(1llu<<(s-k-1))!=1)x*=b._power((1llu<<(k-1))*t);
                    e=_power(Mod-2)*x*x,k++;
                }
                return _min(x,-x),x;
            }
            ModInt inv(){return _power(Mod-2);}
            ModInt _power(ullt index){ModInt ans(1),w(v);while(index){if(index&1)ans*=w;w*=w,index>>=1;}return ans;}
            voi read(){v=0;chr c;do c=getchar();while(c>'9'||c<'0');do v=(c-'0'+v*10)%Mod,c=getchar();while(c>='0'&&c<='9');v%=Mod;}
            voi print()
            {
                static chr C[20];uint tp=0;
                ullt w=v;do C[tp++]=w%10+'0',w/=10;while(w);
                while(tp--)putchar(C[tp]);
            }
            voi println(){print(),putchar('\n');}
            ModInt operator++(int){ModInt ans=*this;return v=chg(v+1),ans;}
        public:
            inline ullt&operator()(){return v;}
            inline ModInt&operator+=(ModInt b){return*this=_chg(v+b.v);}
            inline ModInt&operator-=(ModInt b){return*this=_chg(v+chg(Mod-b.v));}
            inline ModInt&operator*=(ModInt b){return*this=v*b.v;}
            ModInt&operator^=(ullt b){return*this=_power(b);}
            ModInt&operator/=(ModInt b){return*this=b._power(Mod-2)*v;}
            ModInt&operator++(){return v=chg(v+1),*this;}
    };
}
namespace BF_POLY
{
    typedef AnyMod::ModInt modint;
    typedef std::vector<modint>modvec;
    struct poly
    {
        std::vector<modint>V;
        poly(){}
        poly(uint n){V.resize(n);}
        poly(std::vector<modint>V):V(V){}
        inline modint&operator[](uint n){return V[n];};
		inline voi bzr(){V.clear();}
		inline voi push(modint v){V.push_back(v);}
		inline voi pop(){V.pop_back();}
		inline voi cut_zero(){while(!V.empty()&&V.back().empty())V.pop_back();}
		inline voi chg_siz(uint n){V.resize(n);}
		inline voi chg_deg(uint n){V.resize(n+1);}
		inline bol empty(){return cut_zero(),V.empty();}
		inline uint size(){return V.size();}
		inline uint deg(){return V.size()-1;}
		inline modint val(uint n){return(n<size())?V[n]:0;}
        inline modvec GET(){return V;}
        poly reverse()
        {
            poly ans;for(uint i=size()-1;~i;i--)ans.push(V[i]);
            return ans;
        }
		friend poly operator+(poly a,poly b)
		{
			if(a.size()<b.size())a.chg_siz(b.size());
			for(uint i=0;i<b.size();i++)a[i]+=b[i];
			a.cut_zero();return a;
		}
		friend poly operator+(poly a,modint v)
		{
			if(!a.size())a.chg_siz(1);
			a[0]+=v;return a;
		}
		friend poly operator+(modint v,poly a)
		{
			if(!a.size())a.chg_siz(1);
			a[0]+=v;return a;
		}
		friend poly operator-(poly a){
            for(auto&s:a.V)s=-s;
            return a;
        }
		friend poly operator-(poly a,poly b)
		{
			if(a.size()<b.size())a.chg_siz(b.size());
			for(uint i=0;i<b.size();i++)a[i]-=b[i];
			a.cut_zero();return a;
		}
		friend poly operator-(poly a,modint v)
		{
			if(!a.size())a.chg_siz(1);
			a[0]-=v;return a;
		}
		friend poly operator-(modint v,poly a)
		{
			if(!a.size())a.chg_siz(1);
			a[0]-=v;return-a;
		}
		friend poly operator*(poly a,poly b)
		{
            poly ans;ans.chg_siz(a.size()+b.size());
            for(uint i=0;i<a.size();i++)for(uint j=0;j<b.size();j++)ans[i+j]+=a[i]*b[j];
            ans.cut_zero();
            return ans;
		}
        friend poly operator*(poly A,modint b)
        {
            for(auto&s:A.V)s*=b;
            return A;
        }
        friend poly operator*(modint b,poly A)
        {
            for(auto&s:A.V)s*=b;
            return A;
        }
        friend poly operator<<(poly a,uint k)
        {
        	poly ans;ans.chg_siz(k);for(auto v:a.V)ans.push(v);
        	return ans;
        }
        friend poly operator>>(poly a,uint k)
        {
        	poly ans;for(uint i=k;i<a.size();i++)ans.push(a[i]);
        	return ans;
        }
        friend poly sub_mul(poly a,poly b)
        {
            uint len=(a=a.reverse()).size();
            a=a*b;a.chg_siz(len);a=a.reverse();
            return a;
        }
        poly inv(){return inv(size());}
        poly inv(uint prec)
        {
            if(!prec||!val(0)())return poly();
            poly ans(prec);ans[0]=V[0].inv();
            for(uint i=1;i<prec;i++)
            {
                for(uint j=1;j<=i;j++)ans[i]+=ans[i-j]*val(j);
                ans[i]*=-ans[0];
            }
            return ans;
        }
        poly exp(){return exp(size());}
        poly exp(uint prec)
        {
            if(!prec||val(0)())return poly();
            poly ans(prec);
            ans[0]=1;
            for(uint i=1;i<prec;i++)
            {
                for(uint j=0;j<i;j++)ans[i]+=val(i-j)*(i-j)*ans[j];
                ans[i]/=i;
            }
            return ans;
        }
        poly sqrt(){return sqrt(size());}
        poly sqrt(uint prec)
        {
            if(!prec||!val(0)())return poly();
            poly ans(prec);
            ans[0]=V[0]==1?1:V[0].sqrt();
            modint v=ans[0].inv()/2;
            for(uint i=1;i<prec;i++)
            {
                ans[i]=val(i);
                for(uint j=1;j<i;j++)ans[i]-=ans[j]*ans[i-j];
                ans[i]*=v;
            }
            return ans;
        }
        poly&operator+=(poly b)
        {
			if(size()<b.size())chg_siz(b.size());
			for(uint i=0;i<b.size();i++)V[i]+=b[i];
			cut_zero();return*this;
        }
        inline poly&operator+=(modint v)
        {
        	if(!size())chg_siz(1);
        	V[0]+=v;return*this;
        }
        poly&operator-=(poly b)
        {
			if(size()<b.size())chg_siz(b.size());
			for(uint i=0;i<b.size();i++)V[i]-=b[i];
			cut_zero();return*this;
        }
        inline poly&operator-=(modint v)
        {
        	if(!size())chg_siz(1);
        	V[0]-=v;return*this;
        }
        poly&operator*=(poly b){return*this=*this*b;}
        poly&operator*=(modint v)
        {
        	for(auto&t:V)t*=v;
			return*this;
        }
        poly&operator<<=(uint v){return*this=*this<<v;}
        poly&operator>>=(uint v){return*this=*this>>v;}
    };
    struct cpd
    {
        modint point_eval(poly P,modint x)
        {
            modint ans;
            for(uint i=P.deg();~i;i--)ans=ans*x+P[i];
            return ans;
        }
        poly z_npow(poly P,uint n)
        {
            if(P.empty())return P;
            poly ans(P.deg()*n+1);
            for(uint i=0;i<P.size();i++)ans[i*n]+=P[i];
            return ans;
        }
        poly z_npow(poly P,uint n,uint prec)
        {
            poly ans(prec);
            for(uint i=0;i<P.size()&&i*n<prec;i++)ans[i*n]+=P[i];
            return ans;
        }
        poly z_mul_k(poly P,modint k)
        {
            modint t(1);
            for(uint i=0;i<P.size();i++)P[i]*=t,t*=k;
            return P;
        }
        poly z_add_v(poly P,modint v)
        {
            uint n=P.size();if(!n)return P;
            modvec A(n),B(n);
            A[0]=1;for(uint i=1;i<n;i++)A[i]=A[i-1]*i;
            B[n-1]=A[n-1].inv();for(uint i=n-1;i;i--)B[i-1]=B[i]*i;
            poly User(n);modint w(1);
            for(uint i=0;i<n;i++)P[i]*=A[i],User[i]=w*B[i],w*=v;
            P=sub_mul(P,User),P.chg_siz(n);
            for(uint i=0;i<n;i++)P[i]*=B[i];
            return P;
        }
        poly chg_siz(poly P,uint siz){P.chg_siz(siz);return P;}
        poly PolyaInv(poly P,uint prec){return(modint(1)-P).inv(prec);}
        poly PolyaInv(poly P){return PolyaInv(P,P.size());}
        voi println(poly P,uint n)
        {
            for(uint i=0;i<n;i++){
                if(i)putchar(' ');
                P.val(i).print();
            }
            putchar('\n');
        }
        voi println(poly P){println(P,P.size());}
        poly LIM_MUL(poly a,poly b,uint lim)
        {
            poly ans;ans.chg_siz(lim);
            for(uint i=0;i<a.size();i++)for(uint j=0;j<b.size()&&i+j<lim;j++)ans[i+j]+=a[i]*b[j];
            ans.cut_zero();
            return ans;
        }
        poly Max_Mul(poly a,poly b)
        {
            poly ans(std::max(a.size(),b.size()));
            modint v=0;for(uint i=0;i<a.size();i++)v+=b.val(i),ans[i]+=v*a[i];
            v=0;for(uint i=0;i<b.size();i++)ans[i]+=v*b[i],v+=a.val(i);
            return ans;
        }
    };
};
using namespace BF_POLY;
modint P[4005],Q[4005];
poly Pow(poly P,uint index)
{
    poly ans(modvec{1});
    while(index)
    {
        if(index&1)ans*=P;
        P*=P,index>>=1;
    }
    return ans;
}
poly Get(uint n)
{
    poly ans(n/2+1);ans[0]=1;
    for(uint i=0;i<n/2;i++)ans[i+1]=ans[i]*(n-2*i)*(n-2*i-1);
    for(uint i=0;i<=n/2;i++)ans[i]*=Q[i];
    return ans;
}
int main()
{
    AnyMod::ChgMod(1e9+7);
    uint n,m;scanf("%u%u",&n,&m);
    uint LIM=n<<1;
    P[0]=1;for(uint i=1;i<=LIM;i++)P[i]=P[i-1]*i;
    Q[LIM]=P[LIM].inv();for(uint i=LIM;i;i--)Q[i-1]=Q[i]*i;
    uint w=n*2/m;uint cnt1=n*2%m;uint cnt0=m-cnt1;
    poly X=Pow(Get(w),cnt0)*Pow(Get(w+1),cnt1);
    modint ans=0;
    for(uint i=0;i<=n;i++)ans+=X.val(i)*((i&1)?-modint(1):1)*P[n]*Q[n-i]*P[n*2-i*2];
    ans.println();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 9
Accepted

Test #1:

score: 9
Accepted
time: 3ms
memory: 3172kb

input:

1 1

output:

0

result:

ok single line: '0'

Test #2:

score: 0
Accepted
time: 3ms
memory: 3220kb

input:

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3072kb

input:

2 2

output:

16

result:

ok single line: '16'

Test #4:

score: 0
Accepted
time: 3ms
memory: 3084kb

input:

3 1

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 3ms
memory: 3220kb

input:

3 2

output:

288

result:

ok single line: '288'

Test #6:

score: 0
Accepted
time: 3ms
memory: 3216kb

input:

3 3

output:

384

result:

ok single line: '384'

Test #7:

score: 0
Accepted
time: 3ms
memory: 3172kb

input:

4 2

output:

9216

result:

ok single line: '9216'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3176kb

input:

4 3

output:

13824

result:

ok single line: '13824'

Test #9:

score: 0
Accepted
time: 2ms
memory: 3132kb

input:

5 1

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 3ms
memory: 3100kb

input:

5 5

output:

2088960

result:

ok single line: '2088960'

Subtask #2:

score: 12
Accepted

Dependency #1:

100%
Accepted

Test #11:

score: 12
Accepted
time: 3ms
memory: 3100kb

input:

99 55

output:

117836331

result:

ok single line: '117836331'

Test #12:

score: 0
Accepted
time: 3ms
memory: 3180kb

input:

69 50

output:

427094826

result:

ok single line: '427094826'

Test #13:

score: 0
Accepted
time: 3ms
memory: 3176kb

input:

67 5

output:

733227544

result:

ok single line: '733227544'

Test #14:

score: 0
Accepted
time: 3ms
memory: 3192kb

input:

69 26

output:

730153757

result:

ok single line: '730153757'

Test #15:

score: 0
Accepted
time: 2ms
memory: 3180kb

input:

71 64

output:

100578188

result:

ok single line: '100578188'

Test #16:

score: 0
Accepted
time: 4ms
memory: 3108kb

input:

87 10

output:

410973724

result:

ok single line: '410973724'

Test #17:

score: 0
Accepted
time: 3ms
memory: 3076kb

input:

64 35

output:

623989218

result:

ok single line: '623989218'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3220kb

input:

67 51

output:

312068739

result:

ok single line: '312068739'

Test #19:

score: 0
Accepted
time: 3ms
memory: 3152kb

input:

85 3

output:

796582412

result:

ok single line: '796582412'

Subtask #3:

score: 13
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #20:

score: 13
Accepted
time: 3ms
memory: 3184kb

input:

164 20

output:

152386555

result:

ok single line: '152386555'

Test #21:

score: 0
Accepted
time: 3ms
memory: 3196kb

input:

154 80

output:

741601266

result:

ok single line: '741601266'

Test #22:

score: 0
Accepted
time: 3ms
memory: 3232kb

input:

266 255

output:

245915928

result:

ok single line: '245915928'

Test #23:

score: 0
Accepted
time: 4ms
memory: 3188kb

input:

239 19

output:

511848592

result:

ok single line: '511848592'

Test #24:

score: 0
Accepted
time: 0ms
memory: 3112kb

input:

296 141

output:

462138216

result:

ok single line: '462138216'

Test #25:

score: 0
Accepted
time: 3ms
memory: 3208kb

input:

255 250

output:

727256255

result:

ok single line: '727256255'

Test #26:

score: 0
Accepted
time: 3ms
memory: 3312kb

input:

257 15

output:

253032679

result:

ok single line: '253032679'

Test #27:

score: 0
Accepted
time: 1ms
memory: 3152kb

input:

300 299

output:

559277735

result:

ok single line: '559277735'

Subtask #4:

score: 18
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #28:

score: 18
Accepted
time: 5ms
memory: 3160kb

input:

625 19

output:

787742499

result:

ok single line: '787742499'

Test #29:

score: 0
Accepted
time: 3ms
memory: 3224kb

input:

657 324

output:

660247748

result:

ok single line: '660247748'

Test #30:

score: 0
Accepted
time: 5ms
memory: 3112kb

input:

646 582

output:

830442831

result:

ok single line: '830442831'

Test #31:

score: 0
Accepted
time: 5ms
memory: 3120kb

input:

637 14

output:

468904506

result:

ok single line: '468904506'

Test #32:

score: 0
Accepted
time: 8ms
memory: 3140kb

input:

685 343

output:

516203560

result:

ok single line: '516203560'

Test #33:

score: 0
Accepted
time: 5ms
memory: 3132kb

input:

713 644

output:

225559251

result:

ok single line: '225559251'

Test #34:

score: 0
Accepted
time: 7ms
memory: 3136kb

input:

900 899

output:

941929065

result:

ok single line: '941929065'

Subtask #5:

score: 48
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #35:

score: 48
Accepted
time: 16ms
memory: 3128kb

input:

1624 18

output:

887332511

result:

ok single line: '887332511'

Test #36:

score: 0
Accepted
time: 20ms
memory: 3212kb

input:

1779 1687

output:

611283083

result:

ok single line: '611283083'

Test #37:

score: 0
Accepted
time: 22ms
memory: 3272kb

input:

1603 18

output:

846564825

result:

ok single line: '846564825'

Test #38:

score: 0
Accepted
time: 18ms
memory: 3168kb

input:

1651 818

output:

148850576

result:

ok single line: '148850576'

Test #39:

score: 0
Accepted
time: 19ms
memory: 3264kb

input:

1579 1501

output:

427262684

result:

ok single line: '427262684'

Test #40:

score: 0
Accepted
time: 26ms
memory: 3268kb

input:

2000 1999

output:

510859110

result:

ok single line: '510859110'