QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#67506	#4472. 珍珠	alpha1022	100 ✓	90ms	13484kb	C++23	7.0kb	2022-12-10 16:43:48	2022-12-10 16:43:52

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-12-10 16:43:52]
评测

测评结果：100
用时：90ms
内存：13484kb

查看

[2022-12-10 16:43:48]
提交

answer

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define add(a,b) (a + b >= mod ? a + b - mod : a + b)
#define dec(a,b) (a < b ? a - b + mod : a - b)
using namespace std;
const int N = 1e5;
const int mod = 998244353;
inline int fpow(int a,int b)
{
    int ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
    return ret;
}
int D;
long long n,m;
namespace Poly
{
    const int N = 1 << 18;
    const int G = 3;
    int lg2[N + 5];
    int rev[N + 5],fac[N + 5],ifac[N + 5],inv[N + 5];
    int rt[N + 5],irt[N + 5];
    inline void init()
    {
        for(register int i = 2;i <= N;++i)
            lg2[i] = lg2[i >> 1] + 1;
        int w = fpow(G,(mod - 1) / N);
        rt[N >> 1] = 1;
        for(register int i = (N >> 1) + 1;i <= N;++i)
            rt[i] = (long long)rt[i - 1] * w % mod;
        for(register int i = (N >> 1) - 1;i;--i)
            rt[i] = rt[i << 1];
        fac[0] = 1;
        for(register int i = 1;i <= N;++i)
            fac[i] = (long long)fac[i - 1] * i % mod;
        ifac[N] = fpow(fac[N],mod - 2);
        for(register int i = N;i;--i)
            ifac[i - 1] = (long long)ifac[i] * i % mod;
        for(register int i = 1;i <= N;++i)
            inv[i] = (long long)ifac[i] * fac[i - 1] % mod;
    }
    struct poly
    {
        vector<int> a;
        inline poly(int x = 0)
        {
            x && (a.push_back(x),1);
        }
        inline poly(const vector<int> &o)
        {
            a = o,shrink();
        }
        inline void shrink()
        {
            for(;!a.empty() && !a.back();a.pop_back());
        }
        inline int size() const
        {
            return a.size();
        }
        inline void resize(int x)
        {
            a.resize(x);
        }
        inline int operator[](int x) const
        {
            if(x < 0 || x >= size())
                return 0;
            return a[x];
        }
        inline int &operator[](int x)
        {
            return a[x];
        }
        inline void clear()
        {
            vector<int>().swap(a);
        }
        inline void ntt(int type = 1)
        {
            int n = size();
            type == -1 && (reverse(a.begin() + 1,a.end()),1);
            int lg = lg2[n] - 1;
            for(register int i = 0;i < n;++i)
                rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << lg),
                i < rev[i] && (swap(a[i],a[rev[i]]),1);
            for(register int w = 2,m = 1;w <= n;w <<= 1,m <<= 1)
                for(register int i = 0;i < n;i += w)
                    for(register int j = 0;j < m;++j)
                    {
                        int t = (long long)rt[m | j] * a[i | j | m] % mod;
                        a[i | j | m] = dec(a[i | j],t),a[i | j] = add(a[i | j],t);
                    }
            if(type == -1)
                for(register int i = 0;i < n;++i)
                    a[i] = (long long)a[i] * inv[n] % mod;
        }
        friend inline poly operator+(const poly &a,const poly &b)
        {
            vector<int> ret(max(a.size(),b.size()));
            for(register int i = 0;i < ret.size();++i)
                ret[i] = add(a[i],b[i]);
            return poly(ret);
        }
        friend inline poly operator-(const poly &a,const poly &b)
        {
            vector<int> ret(max(a.size(),b.size()));
            for(register int i = 0;i < ret.size();++i)
                ret[i] = dec(a[i],b[i]);
            return poly(ret);
        }
        friend inline poly operator*(poly a,poly b)
        {
            if(a.a.empty() || b.a.empty())
                return poly();
            int lim = 1,tot = a.size() + b.size() - 1;
            for(;lim < tot;lim <<= 1);
            a.resize(lim),b.resize(lim);
            a.ntt(),b.ntt();
            for(register int i = 0;i < lim;++i)
                a[i] = (long long)a[i] * b[i] % mod;
            a.ntt(-1),a.shrink();
            return a;
        }
        poly &operator+=(const poly &o)
        {
            resize(max(size(),o.size()));
            for(register int i = 0;i < o.size();++i)
                a[i] = add(a[i],o[i]);
            return *this;
        }
        poly &operator-=(const poly &o)
        {
            resize(max(size(),o.size()));
            for(register int i = 0;i < o.size();++i)
                a[i] = dec(a[i],o[i]);
            return *this;
        }
        poly &operator*=(poly o)
        {
            return (*this) = (*this) * o;
        }
        poly deriv() const
        {
            if(a.empty())
                return poly();
            vector<int> ret(size() - 1);
            for(register int i = 0;i < size() - 1;++i)
                ret[i] = (long long)(i + 1) * a[i + 1] % mod;
            return poly(ret);
        }
        poly integ() const
        {
            if(a.empty())
                return poly();
            vector<int> ret(size() + 1);
            for(register int i = 0;i < size();++i)
                ret[i + 1] = (long long)a[i] * inv[i + 1] % mod;
            return poly(ret);
        }
        inline poly modxn(int n) const
        {
            n = min(n,size());
            return poly(vector<int>(a.begin(),a.begin() + n));
        }
        inline poly inver(int m) const
        {
            poly ret(fpow(a[0],mod - 2));
            for(register int k = 1;k < m;)
                k <<= 1,ret = (ret * (2 - modxn(k) * ret)).modxn(k);
            return ret.modxn(m);
        }
        inline poly log(int m) const
        {
            return (deriv() * inver(m)).integ(),modxn(m);
        }
        inline poly exp(int m) const
        {
            poly ret(1);
            for(register int k = 1;k < m;)
                k <<= 1,ret = (ret * (1 - ret.log(k) + modxn(k))).modxn(k);
            return ret.modxn(m);
        }
    };
}
using Poly::init;
using Poly::poly;
poly f,g;
int ans;
int main()
{
    Poly::init();
    scanf("%d%lld%lld",&D,&n,&m);
    if(n - 2 * m >= D)
    {
        printf("%d\n",fpow(D,n % (mod - 1)));
        return 0;
    }
    else if(n < 2 * m)
    {
        puts("0");
        return 0;
    }
    f.resize(D + 1),g.resize(D + 1);
    for(register int i = 0;i <= D;++i)
        f[i] = Poly::ifac[i],
        g[i] = (long long)(i & 1 ? mod - 1 : 1) * fpow((D - 2 * i + mod) % mod,n % (mod - 1)) % mod * Poly::ifac[i] % mod;
    g *= f,g.resize(D + 1);
    for(register int i = 0;i <= D;++i)
        g[i] = (long long)g[i] * Poly::fac[D] % mod * Poly::ifac[D - i] % mod * fpow(2,mod - 1 - i) % mod * Poly::fac[i] % mod;
    reverse(g.a.begin(),g.a.end());
    for(register int i = 0;i <= D;++i)
        f[i] = (long long)(i & 1 ? mod - 1 : 1) * Poly::ifac[i] % mod;
    f *= g,f.resize(D + 1),reverse(f.a.begin(),f.a.end());
    for(register int i = 0;i <= D;++i)
        f[i] = (long long)f[i] * Poly::ifac[i] % mod;
    for(register int i = 0;i <= n - 2 * m;++i)
        ans = add(ans,f[i]);
    printf("%d\n",ans);
}

源文件, 语言: C++23

詳細信息

Test #1:

score: 4

Accepted

time: 4ms

memory: 8176kb

input:

2 7 3

output:

result:

ok 1 number(s): "128"

Test #2:

score: 4

Accepted

time: 4ms

memory: 8124kb

input:

2 20 9

output:

result:

ok 1 number(s): "1048576"

Test #3:

score: 4

Accepted

time: 2ms

memory: 8144kb

input:

99 97 30

output:

893559494

result:

ok 1 number(s): "893559494"

Test #4:

score: 4

Accepted

time: 4ms

memory: 8192kb

input:

100 97 29

output:

870441375

result:

ok 1 number(s): "870441375"

Test #5:

score: 4

Accepted

time: 2ms

memory: 8192kb

input:

97 100 16

output:

114531619

result:

ok 1 number(s): "114531619"

Test #6:

score: 4

Accepted

time: 3ms

memory: 8204kb

input:

98 98 38

output:

910698957

result:

ok 1 number(s): "910698957"

Test #7:

score: 4

Accepted

time: 4ms

memory: 8144kb

input:

100 99 30

output:

267167918

result:

ok 1 number(s): "267167918"

Test #8:

score: 4

Accepted

time: 10ms

memory: 8248kb

input:

4000 3998 602

output:

267823033

result:

ok 1 number(s): "267823033"

Test #9:

score: 4

Accepted

time: 6ms

memory: 8472kb

input:

3999 3998 478

output:

result:

ok 1 number(s): "7661427"

Test #10:

score: 4

Accepted

time: 7ms

memory: 8344kb

input:

4000 3999 18

output:

46680613

result:

ok 1 number(s): "46680613"

Test #11:

score: 4

Accepted

time: 3ms

memory: 8444kb

input:

4000 3998 683

output:

689956672

result:

ok 1 number(s): "689956672"

Test #12:

score: 4

Accepted

time: 10ms

memory: 8300kb

input:

3998 3998 1743

output:

625630497

result:

ok 1 number(s): "625630497"

Test #13:

score: 4

Accepted

time: 8ms

memory: 8228kb

input:

300 999999997 499999880

output:

311178114

result:

ok 1 number(s): "311178114"

Test #14:

score: 4

Accepted

time: 2ms

memory: 8308kb

input:

297 999999999 499999955

output:

111728734

result:

ok 1 number(s): "111728734"

Test #15:

score: 4

Accepted

time: 8ms

memory: 8196kb

input:

298 999999998 499999978

output:

873407954

result:

ok 1 number(s): "873407954"

Test #16:

score: 4

Accepted

time: 1ms

memory: 8124kb

input:

100000 999999998 0

output:

403169128

result:

ok 1 number(s): "403169128"

Test #17:

score: 4

Accepted

time: 74ms

memory: 13392kb

input:

99999 100000 1

output:

520922757

result:

ok 1 number(s): "520922757"

Test #18:

score: 4

Accepted

time: 77ms

memory: 13400kb

input:

99998 99998 2

output:

776350879

result:

ok 1 number(s): "776350879"

Test #19:

score: 4

Accepted

time: 87ms

memory: 13436kb

input:

99998 999999998 499972261

output:

805937760

result:

ok 1 number(s): "805937760"

Test #20:

score: 4

Accepted

time: 83ms

memory: 13416kb

input:

99997 999999999 499975678

output:

265933807

result:

ok 1 number(s): "265933807"

Test #21:

score: 4

Accepted

time: 86ms

memory: 13368kb

input:

100000 1000000000 499958129

output:

59384653

result:

ok 1 number(s): "59384653"

Test #22:

score: 4

Accepted

time: 90ms

memory: 13396kb

input:

99998 999999999 499978565

output:

897679746

result:

ok 1 number(s): "897679746"

Test #23:

score: 4

Accepted

time: 81ms

memory: 13484kb

input:

100000 999999999 499970692

output:

169325977

result:

ok 1 number(s): "169325977"

Test #24:

score: 4

Accepted

time: 79ms

memory: 13392kb

input:

99997 1000000000 499976402

output:

562099965

result:

ok 1 number(s): "562099965"

Test #25:

score: 4

Accepted

time: 72ms

memory: 13420kb

input:

99997 1000000000 499978285

output:

681053406

result:

ok 1 number(s): "681053406"

Extra Test:

score: 0

Extra Test Passed