代码

#include<bits/stdc++.h>
using namespace std;
#define cs const
#define re register
#define pii pair<int,int>
#define ll long long
#define y1 shinkle
#define fi first
#define pb push_back
#define se second
#define bg begin
using namespace std;


inline int read()
{
    int x = 0, fh = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        if (ch == '-')
            fh = -1;
    for (; isdigit(ch); ch = getchar())
        x = (x << 1) + (x << 3) + (ch ^ '0');
    return x * fh;
}

const int N = 1 << 14;
int P,mod;

typedef vector<int> vi;
inline int add(int a,int b){return (a+b)>=mod?(a+b-mod):(a+b);}
inline int dec(int a,int b){return (a<b)?(a-b+mod):(a-b);}
inline int mul(int a,int b){static ll r;r=(ll)a*b;return (r>=mod)?(r%mod):r;}
inline void Add(int &a,int b){a=(a+b)>=mod?(a+b-mod):(a+b);}
inline void Dec(int &a,int b){a=(a<b)?(a-b+mod):(a-b);}
inline void Mul(int &a,int b){static ll r;r=(ll)a*b;a=(r>=mod)?(r%mod):r;}
inline int ksm(int a,int b,int res=1){for(;b;b>>=1,Mul(a,a))(b&1)&&(Mul(res,a),1);return res;}
inline int Inv(int x){return ksm(x,mod-2);}
inline int fix(ll x){x%=mod;return (x<0)?x+mod:x;}

int msqrt(int x)
{
    if (!x)
        return 0;
    if (ksm(x, (P - 1) / 2) != 1)
        return -1;
    if (P % 4 == 3)
        return ksm(x, (P + 1) / 4);
    int z = 2;
    while (ksm(z, (P - 1) / 2) == 1)
        ++z;
    const int s = __builtin_ctz(P - 1), q = (P - 1) >> s;
    int r = ksm(x, (q + 1) / 2), t = ksm(x, q);
    z = ksm(z, q);
    for (int i = 1; i < s; ++i) {
        int y = mul(z, z);
        if (ksm(t, 1 << (s - i - 1)) != 1)
            t = mul(t, y), r = mul(r, z);
        z = y;
    }
    return r;
}
string k;
int p, x;
int pk[5005];
int c[5005][5005];
int pos[5005];
int invs[N], fac[N], ifac[N];
int binom(int n, int k) { return mul(fac[n], mul(ifac[n - k], ifac[k])); }
void ginv()
{
    invs[1] = 1;
    fac[0] = ifac[0] = 1;
    for (int i = 2; i != N; ++i)
        invs[i] = mul(invs[P % i], (P - P / i));
    for (int i = 1; i != N; ++i)
        fac[i] = mul(fac[i - 1], i);
    for (int i = 1; i != N; ++i)
        ifac[i] = mul(ifac[i - 1], invs[i]);
}

typedef vector<int> poly;
namespace Poly{
	cs int C=15,M=(1<<C)|5;
	poly w[C+1];
    int rev[M],iv[M];
	inline void init_rev(int lim){
		for(int i=0;i<lim;i++)rev[i]=(rev[i>>1]>>1)|((i&1)*(lim>>1));
	}
	inline void init_w(){
		for(int i=1;i<=C;i++)w[i].resize((1<<(i-1))|1);//=new int[(1<<(i-1))|1];
		int wn=ksm(3,(mod-1)/(1<<C));w[C][0]=1;
		for(int i=1,l=1<<(C-1);i<l;i++)w[C][i]=mul(w[C][i-1],wn);
		for(int i=C-1;i;i--)
		for(int j=0,l=1<<(i-1);j<l;j++)w[i][j]=w[i+1][j<<1];
		iv[0]=iv[1]=1;
		for(int i=2;i<M;i++)iv[i]=mul(mod-mod/i,iv[mod%i]);
	}
	inline void dft(int *f,int lim){
		for(int i=0;i<lim;i++)if(i>rev[i])swap(f[i],f[rev[i]]);
		for(int mid=1,l=1,a0,a1;mid<lim;mid<<=1,l++)
		for(int i=0;i<lim;i+=mid<<1)
		for(int j=0;j<mid;j++)
		a0=f[i+j],a1=mul(w[l][j],f[i+j+mid]),f[i+j]=add(a0,a1),f[i+j+mid]=dec(a0,a1);
	}
	inline void ntt(poly &f,int lim,int kd){
		dft(&f[0],lim);
		if(kd==-1){
			reverse(f.bg()+1,f.bg()+lim);
			for(int i=0;i<lim;i++)Mul(f[i],iv[lim]);
		}
	}
	inline poly operator +(poly a,poly b){
		if(a.size()<b.size())a.resize(b.size());
		for(int i=0;i<b.size();i++)Add(a[i],b[i]);
		return a;
	}
	inline poly operator -(poly a,poly b){
		if(a.size()<b.size())a.resize(b.size());
		for(int i=0;i<b.size();i++)Dec(a[i],b[i]);
		return a;
	}
	inline poly operator *(poly a,int b){
		for(int i=0;i<a.size();i++)Mul(a[i],b);return a;
	}
	inline poly operator *(poly a,poly b){
		if(!a.size()||!b.size())return poly(0);
		int deg=a.size()+b.size()-1;
		if(a.size()<=32||b.size()<=32){
			poly c(deg,0);
			for(int i=0;i<a.size();i++)
			for(int j=0;j<b.size();j++)
			Add(c[i+j],mul(a[i],b[j]));
			return c;
		}
        int lim=1;while(lim<deg)lim<<=1;
		init_rev(lim);
		a.resize(lim),ntt(a,lim,1);
		b.resize(lim),ntt(b,lim,1);
		for(int i=0;i<lim;i++)Mul(a[i],b[i]);
		ntt(a,lim,-1),a.resize(deg);
		return a;
	}

poly power(vector<int> x, string y)
{
    int len = y.length();
    int n1 = p - 1, n2 = p - 1, n3 = n1 + n2 - 1;
    poly px=x,py(1);
    px.resize(n1);
 //   copy_n(x.begin(), n1, px);    
    py[0] = 1;
    for (int now = len-1; now >=0;now--) {
        if(y[now]=='1'){
            py=py*px;
            for(int i=p-1;i<py.size();i++)Add(py[i-p+1],py[i]);
            py.resize(p-1);
        }
        px=px*px;
        for(int i=p-1;i<px.size();i++)Add(px[i-p+1],px[i]);
        px.resize(p-1);
    }
    return py;
}

}

void solve()
{ auto st = clock();
    for(int i=1;i<=1000;i++)k+='1';
    p=4999,x=2648;
   // cin >> p >> x;
    c[0][0] = 1;
    for (int i = 1; i <= p - 1; ++i) {
        c[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % p;
    }
    if(1.0 * (clock()-st) / CLOCKS_PER_SEC >4.5){
        assert(0);
    }
    int g1 = 0;
    for (int i = 2; i <= p - 1; ++i) {
    if(1.0 * (clock()-st) / CLOCKS_PER_SEC >4.5){
        assert(0);
    }
        bitset<5005> s;
        int now = 1;
        for (int j = 0; j <= p - 2; ++j) {
            if(1.0 * (clock()-st) / CLOCKS_PER_SEC >4.5){
        assert(0);
    }
            s.set(now);
            now = 1ll * now * i % p;
        }
        if ((int)s.count() == p - 1) {
            if(1.0 * (clock()-st) / CLOCKS_PER_SEC >4.5){
        assert(0);
    }
            g1 = i;
            break;
        }
    }
    if(1.0 * (clock()-st) / CLOCKS_PER_SEC >4.5){
        assert(0);
    }
    int now = 1;
    for (int i = 0; i <= p - 2; ++i) {
        pos[now] = i;
        now = 1ll * now * g1 % p;
    }
    if(1.0 * (clock()-st) / CLOCKS_PER_SEC >4.5){
        assert(0);
    }
    for (int i = 0; i <= p - 1; ++i)
        for (int j = 0; j <= p - 1; ++j)
            if (c[i][j] != 0)
                pk[pos[c[i][j]]]++;
    if(1.0 * (clock()-st) / CLOCKS_PER_SEC >4.5){
        assert(0);
    }
    vector<int> ans(p, 0);
    for (int i = 0; i <= p - 2; ++i)
        ans[i] = pk[i];
    if(1.0 * (clock()-st) / CLOCKS_PER_SEC >4.5){
        assert(0);
    }
//   cerr << 1.0 * (clock()-st) / CLOCKS_PER_SEC << endl;
    ans = Poly::power(ans, k);
    cerr << 1.0 * (clock()-st) / CLOCKS_PER_SEC << endl;
    cout << ans[pos[x]] << endl;
}
int main()
{
//freopen("1.in","r",stdin);
    int T = 1;
    //	cin>>T;
    P =mod= 998244353;
    Poly::init_w();
    ginv();
    while (T--) {
        solve();
    }
    cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
    return 0;
}

评测结果