QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#97668#6323. Range NEQyangjlTL 120ms27552kbC++208.1kb2023-04-17 20:57:082023-04-17 20:57:12

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-17 20:57:12]
  • 评测
  • 测评结果:TL
  • 用时:120ms
  • 内存:27552kb
  • [2023-04-17 20:57:08]
  • 提交

answer

#include<iostream>
#include<cmath>
#include<cstring>
#include<cassert>
#include<string>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<unordered_map>
#include<map>
#include<vector>
#include<set>
#include<unordered_set>
#include<bitset>
#include<climits>
#include<numeric>
#include<functional>
#include<iomanip>
#include<random>
#ifdef YJL
#include<debug.h>
#else
#define debug(args...)0
#define debug_n(a,n)0
#endif
using namespace std;
typedef long long ll;
template<int P>
struct MInt {
    int x;
    MInt(): x(0){}
    MInt(ll x): x(norm(x%P)){}
    static int norm(int x) {
        if(x<0) x+=P;
        else if(x>=P) x-=P;
        return x;
    }
    MInt pow(ll b) const{
        MInt res=1,a=*this;
        for(; b; b>>=1,a*=a)
            if(b&1) res*=a;
        return res;
    }
    MInt inv() const{
        return pow(P-2);
    }
    MInt operator-() const{
        return MInt()-*this;
    }
    MInt& operator+=(const MInt& a) {
        x=norm(x+a.x);
        return *this;
    }
    MInt& operator-=(const MInt& a) {
        x=norm(x-a.x);
        return *this;
    }
    MInt& operator*=(const MInt& a) {
        x=(ll)x*a.x%P;
        return *this;
    }
    MInt& operator/=(const MInt& a) {
        return *this*=a.inv();
    }
    friend MInt operator+(MInt l,const MInt& r) {
        return l+=r;
    }
    friend MInt operator-(MInt l,const MInt& r) {
        return l-=r;
    }
    friend MInt operator*(MInt l,const MInt& r) {
        return l*=r;
    }
    friend MInt operator/(MInt l,const MInt& r) {
        return l/=r;
    }
    friend istream& operator>>(istream& is,MInt& a) {
        ll v;
        is>>v;
        a=MInt(v);
        return is;
    }
    friend ostream& operator<<(ostream& os,const MInt& a) {
        return os<<a.x;
    }
};
const int P=998244353;
using Z=MInt<P>;
namespace NTT {
	using Poly=vector<Z>;
    Poly mulxk(Poly a,int k) {
        a.insert(a.begin(),k,0);
        return a;
    }
    Poly divxk(const Poly& a,int k) {
        if(a.size()<=k) return Poly();
        return Poly(a.begin()+k,a.end());
    }
    Poly modxk(const Poly& a,int k) {
        k=min(k,(int)a.size());
        return Poly(a.begin(),a.begin()+k);
    }
    Poly operator+(const Poly& a,const Poly& b) {
        Poly c(a);
		c.resize(max(a.size(),b.size()));
		for(int i=0; i<b.size(); ++i)
            c[i]+=b[i];
		return c;
    }
    Poly operator-(const Poly& a,const Poly& b) {
        Poly c(a);
		c.resize(max(a.size(),b.size()));
		for(int i=0; i<b.size(); ++i)
            c[i]-=b[i];
		return c;
    }
    Poly operator-(Poly a) {
        for(auto& x:a)
            x=-x;
        return a;
    }
    #if fftTag==3
    using FFT::operator*;
    #else
    void dft(Poly& a) {
        static vector<int> rev;
        int n=a.size();
        if(rev.size()!=n) {
            rev.resize(n);
            for(int i=1; i<n; ++i)
			    rev[i]=rev[i>>1]>>1|(i&1?n>>1:0);
        }
		for(int i=0; i<n; ++i)
			if(i<rev[i]) 
                swap(a[i], a[rev[i]]);
        // w[i]=w(highbit(i)*2, i-highbit(i))
        static vector<Z> w{0,1};
        if(w.size()<n) {
            int k=__builtin_ctz(w.size());
            w.resize(n);
            for(; (1<<k)<n; ++k) {
                // w(1<<(k+1),1)
                Z e=Z(3).pow((P-1)>>(k+1));
                for(int i=(1<<(k-1)); i<(1<<k); ++i) {
                    w[i<<1]=w[i];
                    w[i<<1|1]=w[i]*e;
                }
            }
        }
		for(int m=1; m<n; m<<=1)
			for(int i=0; i<n; i+=m<<1)
				for(int j=0; j<m; ++j) {
					Z B=a[i+j], C=a[i+m+j]*w[m+j];
					a[i+j]=B+C, a[i+m+j]=B-C;
				}
	}
    void idft(Poly& a) {
        dft(a);
        reverse(a.begin()+1,a.end());
        Z inv=(1-P)/(int)a.size();
        for(auto& x:a)
            x*=inv;
    }
	Poly operator*(Poly a,Poly b) {
		if(a.empty()||b.empty()) return Poly();
		int len=1, sz=a.size()+b.size()-1;
		while(len<sz)
            len<<=1;
		a.resize(len), dft(a);
		b.resize(len), dft(b);
		for(int i=0; i<len; ++i)
            a[i]*=b[i];
		idft(a);
		a.resize(sz);
		return a;
	}
    #endif
	Poly operator*(Poly a,Z b) {
		for(auto& x:a) x*=b;
		return a;
	}
    Poly operator*(Z a,Poly b) {
		return b*a;
	}
    Poly operator+=(Poly& a,const Poly& b) {
        return a=a+b;
    }
    Poly operator-=(Poly& a,const Poly& b) {
        return a=a-b;
    }
    template<class T>
    Poly operator*=(Poly& a,const T& b) {
        return a=a*b;
    }
    Poly Deriv(Poly a) {
		for(int i=0; i+1<a.size(); ++i)
            a[i]=a[i+1]*(i+1);
		if(a.size())
            a.pop_back();
		return a;
	}
	Poly Integ(Poly a) {
		a.push_back(0);
		for(int i=(int)a.size()-1; i>0; --i)
            a[i]=a[i-1]/i;
		a[0]=0;
		return a;
	}
	Poly Inv(const Poly& a,int m=-1) {
		assert(a[0].x!=0);
		if(m==-1) m=a.size();
        Poly f{a[0].inv()};
        int k=1;
        while(k<m) {
            k<<=1;
            f=modxk(f*(Poly{2}-f*modxk(a,k)),k);
            // 非MTT优化:两次变一次
            // Poly x=f; x.resize(k); x.resize(k<<1);
            // Poly y=a; y.resize(k); y.resize(k<<1);
            // dft(x), dft(y);
            // for(int i=0; i<x.size(); ++i)
            //     x[i]=x[i]*(2-x[i]*y[i]);
            // idft(x);
            // f=modxk(x,k);
        }
		return modxk(f,m);
	}
	namespace Cipolla {
		Z w,a;
		struct CP {
			Z x,y;
			CP(Z x,Z y): x(x),y(y) {}
			CP operator*(const CP& b) const{
				return CP(x*b.x+y*b.y*w,x*b.y+y*b.x);
			}
            CP pow(int b) const{
                CP ans(1,0), a(*this);
                for(; b; b>>=1,a=a*a)
                    if(b&1) ans=ans*a;
                return ans;
            }
		};
		int sqrt(Z n) {
			if(!n.x) return 0;
			if(n.pow((P-1)>>1).x==P-1)
                return -1;// 非二次剩余
			while(true) {
				a=rand(), w=a*a-n;
                if(w.pow((P-1)>>1).x==P-1)
                    return CP(a,1).pow((P+1)>>1).x.x;
			}
            return -1;
		}
	}
    Poly Sqrt(const Poly& a,int m=-1) {
        int x=Cipolla::sqrt(a[0]);
        assert(x!=-1);
        if(m==-1) m=a.size();
        Poly f{min(x,P-x)};
        int k=1;
        while(k<m) {
            k<<=1;
            f=(f+modxk(modxk(a,k)*Inv(f,k),k))*((1+P)>>1);
        }
        return modxk(f,m);
    }
	Poly Ln(const Poly& a,int m=-1) {
		assert(a[0].x==1);
		if(m==-1) m=a.size();
		return modxk(Integ(Deriv(a)*Inv(a,m)),m);
	}
	Poly Exp(const Poly& a,int m=-1) {
        assert(a[0].x==0);
        if(m==-1) m=a.size();
        Poly f{1};
        int k=1;
        while(k<m) {
            k<<=1;
            f=modxk(f*(Poly{1}-Ln(f,k)+modxk(a,k)),k);
        }
        return modxk(f,m);
    }
    Poly Pow(const Poly& a,ll k,int m=-1) {
        if(m==-1) m=a.size();
        int i=0;
        while(i<a.size() && !a[i].x) i++;
        if(i==a.size()||i*k>=m) return Poly(m);
        Z val=a[i].pow(k);// val*x^(ik)
        Poly b=divxk(a,i)*a[i].inv();
        return mulxk(Exp(k*Ln(b,m-i*k),m-i*k),i*k)*val;
    }
    Poly mulSub(const Poly& a,Poly b) {// 减法卷积
		if(b.empty()) return Poly();
        reverse(b.begin(), b.end());
        return divxk(a*b,b.size()-1);
	}
} using namespace NTT;

namespace {
    const int MAXN=2e6+10;
    Z inv[MAXN],fac[MAXN],infac[MAXN];
    int initFac=[](int n=MAXN-1) {
        n=min(n,P-1);
        inv[1]=fac[0]=infac[0]=1;
        for(int i=1; i<=n; ++i) {
            fac[i]=fac[i-1]*i;
            if(i>1) inv[i]=(P-P/i)*inv[P%i];
            infac[i]=infac[i-1]*inv[i];
        }
        return 0;
    }();
    Z binom(int n,int m) {// n,m<P
        if(m<0||n<m) return 0;
        return fac[n]*infac[m]*infac[n-m];
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n,m;
    cin>>n>>m;
    Poly f(m+1);
    for(int i=0; i<=m; ++i) {
        f[i]=binom(m,i)*binom(m,i)*fac[i];
    }
    f=Pow(f,n,n*m+1);
    Z ans=0;
    for(int i=0; i<=n*m; ++i) {
        ans+=(i&1?-1:1)*fac[n*m-i]*f[i];
    }
    cout<<ans;
    return 0;
}
/*




*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 35ms
memory: 26892kb

input:

2 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 42ms
memory: 26824kb

input:

5 1

output:

44

result:

ok 1 number(s): "44"

Test #3:

score: 0
Accepted
time: 120ms
memory: 27552kb

input:

167 91

output:

284830080

result:

ok 1 number(s): "284830080"

Test #4:

score: 0
Accepted
time: 32ms
memory: 26872kb

input:

2 1

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 31ms
memory: 26888kb

input:

2 3

output:

36

result:

ok 1 number(s): "36"

Test #6:

score: 0
Accepted
time: 36ms
memory: 26824kb

input:

2 4

output:

576

result:

ok 1 number(s): "576"

Test #7:

score: 0
Accepted
time: 36ms
memory: 26828kb

input:

3 1

output:

2

result:

ok 1 number(s): "2"

Test #8:

score: 0
Accepted
time: 31ms
memory: 26796kb

input:

3 2

output:

80

result:

ok 1 number(s): "80"

Test #9:

score: 0
Accepted
time: 30ms
memory: 26888kb

input:

3 3

output:

12096

result:

ok 1 number(s): "12096"

Test #10:

score: 0
Accepted
time: 30ms
memory: 26864kb

input:

3 4

output:

4783104

result:

ok 1 number(s): "4783104"

Test #11:

score: 0
Accepted
time: 30ms
memory: 26872kb

input:

4 1

output:

9

result:

ok 1 number(s): "9"

Test #12:

score: 0
Accepted
time: 36ms
memory: 26860kb

input:

4 2

output:

4752

result:

ok 1 number(s): "4752"

Test #13:

score: 0
Accepted
time: 30ms
memory: 26868kb

input:

4 3

output:

17927568

result:

ok 1 number(s): "17927568"

Test #14:

score: 0
Accepted
time: 30ms
memory: 26832kb

input:

4 4

output:

776703752

result:

ok 1 number(s): "776703752"

Test #15:

score: 0
Accepted
time: 38ms
memory: 26864kb

input:

5 2

output:

440192

result:

ok 1 number(s): "440192"

Test #16:

score: 0
Accepted
time: 31ms
memory: 26808kb

input:

5 3

output:

189125068

result:

ok 1 number(s): "189125068"

Test #17:

score: 0
Accepted
time: 31ms
memory: 26784kb

input:

5 4

output:

975434093

result:

ok 1 number(s): "975434093"

Test #18:

score: -100
Time Limit Exceeded

input:

1000 1000

output:


result: