QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#658591#9476. 012 Griducup-team5319#AC ✓82ms28352kbC++144.6kb2024-10-19 17:06:232024-10-19 17:06:26

Judging History

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

  • [2024-10-19 17:06:26]
  • 评测
  • 测评结果:AC
  • 用时:82ms
  • 内存:28352kb
  • [2024-10-19 17:06:23]
  • 提交

answer

//Linkwish's code
#include<bits/stdc++.h>
#define endl '\n'
#define si inline
#define fi first
#define se second
using namespace std;
typedef long long ll;typedef __int128 li;typedef long double ld;
typedef pair<int,int> pii;typedef pair<ll,ll> pll;
typedef const int ci;typedef const ll cl;ci iinf=1e9;cl linf=LLONG_MAX;
template<typename T>si bool gmax(T &x,const T y){if(x<y)return x=y,1;return 0;}
template<typename T>si bool gmin(T &x,const T y){if(y<x)return x=y,1;return 0;}

namespace LinkWish{

    ci N=(1<<19),M=N,mod=998244353;

    si int qpow(int x,int y){
        int res=1;
        for(;y;x=1ll*x*x%mod,y>>=1)if(y&1)res=1ll*res*x%mod;
        return res;
    }
    
    si int GMod(ci x){return x>mod?x-mod:x;}
    
    int lena=N,lenb=N;
    int A[M],B[M];
    int lg,lim,P[M];
    si void calclim(){lim=1<<(lg=__lg(lena+lenb)+1);}
    si void Init(){
        calclim();
        for(int i=0,j=1,w;i<lg;i++){
            w=qpow(3,(mod-1)>>(i+1)),P[j++]=1;
            for(;j<(2<<i);j++)P[j]=1ll*P[j-1]*w%mod;
        }
    }
    
    si void DIF(int *a){
        for(int i=lg-1,len=lim>>1;~i;i--,len>>=1){
            for(int j=0;j<lim;j+=(len<<1)){
                for(int k=j,x,y,cur=len;k<j+len;k++,cur++){
                    x=a[k],y=a[k+len];
                    a[k]=GMod(x+y),a[k+len]=1ll*(x-y+mod)*P[cur]%mod;
                }
            }
        }
    }
    si void DIT(int *a){
        for(int i=0,len=1;i<lg;i++,len<<=1){
            for(int j=0;j<lim;j+=(len<<1)){
                for(int k=j,x,y,cur=len;k<j+len;k++,cur++){
                    x=a[k],y=1ll*a[k+len]*P[cur]%mod;
                    a[k]=GMod(x+y),a[k+len]=GMod(x-y+mod);
                }
            }
        }
        reverse(a+1,a+lim);
        for(int i=0,inv=qpow(lim,mod-2);i<lim;i++)a[i]=1ll*a[i]*inv%mod;
    }

    int n=400003;
    vector<int> e[N];

    int fac[N],inv[N];
    si void init(){
        fac[0]=1;for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
        inv[n]=qpow(fac[n],mod-2);for(int i=n-1;~i;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
    }
    si int C(int x,int y){
        if(x<0||y<0||x<y)return 0;
        return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;
    }

    int sz[N],cnt[N];
    void dfs(int x,int fa){
        sz[x]=1;
        for(int to:e[x])if(to!=fa)dfs(to,x),sz[x]+=sz[to];
        cnt[sz[x]]++,cnt[n-sz[x]]++;
    }
    
    void mian(){
        init();
		
		int n, m; scanf("%d %d", &n, &m);


        lena=n, lenb = m-1, Init();
        // for(int i=0;i<=n;i++){
        //     A[i]=inv[i];
        //     B[i]=1ll*cnt[n-i+1]*fac[n-i+1]%mod;
        // }
		A[0] = 0; for (int i = 1; i <= n; i++) A[i] = 1ll * inv[i - 1] * inv[i - 1] % mod;
		B[0] = 0; for (int i = 1; i < m; i++) B[i] = 1ll * inv[i - 1] * inv[i - 1] % mod;

        DIF(A),DIF(B);
        for(int i=0;i<lim;i++)A[i]=1ll*A[i]*B[i]%mod;
        DIT(A);

		int ans = 0;
		for (int i = 2; i < n + m; i++) ans = (ans + 1ll * fac[i - 2] * fac[i - 2] % mod * A[i]) % mod;
		
		// printf("%d\n", ans);

memset(A, 0, sizeof A); memset(B, 0, sizeof B);
		A[0] = 0; for (int i = 1; i <= n; i++) A[i] = 1ll * inv[i] * (i == 1 ? 0 : inv[i - 2]) % mod;
		B[0] = 0; for (int i = 1; i < m; i++) B[i] = 1ll * inv[i] * (i == 1 ? 0 : inv[i - 2]) % mod;
		// for (int i = 1; i <= n; i++) printf("@ %d\n", A[i]);
		// for (int i = 1; i < m; i++) printf("# %d\n", B[i]);

        DIF(A),DIF(B);
        for(int i=0;i<lim;i++)A[i]=1ll*A[i]*B[i]%mod;
        DIT(A);

		// for (int i = 2; i < n + m; i++) printf("! %d %lld\n", A[i], 1ll * fac[i - 2] * fac[i - 2] % mod * A[i] % mod);
		for (int i = 2; i < n + m; i++) ans = (ans + 1ll * (mod - fac[i - 2]) * fac[i - 2] % mod * A[i]) % mod;

		ans = ans * 2 % mod;
		for (int d = 1; d <= n; d++) {
			int c1 = 1ll * C(d + m - 2, d - 1) * C(d + m - 2, d - 1) % mod;
			int c2 = d == 1 ? 0 : int(1ll * C(d + m - 2, d) * C(d + m - 2, d - 2) % mod);
			ans = (ans + 1ll * c1 * (n - d + 1)) % mod; ans = (ans + 1ll * (mod - c2) * (n - d + 1)) % mod;
			// printf("%d\n", ans);
		}
		for (int d = 1; d <= m - 2; d++) {
			int c1 = 1ll * C(d + n - 2, d - 1) * C(d + n - 2, d - 1) % mod;
			int c2 = d == 1 ? 0 : int(1ll * C(d + n - 2, d) * C(d + n - 2, d - 2) % mod);
			ans = (ans + 1ll * c1 * (m - d - 1)) % mod; ans = (ans + 1ll * (mod - c2) * (m - d - 1)) % mod;
		}
		printf("%d\n", (ans + 2) % mod);
    }
}

signed main(){
    // #ifndef ONLINE_JUDGE
    // assert(freopen("in.in","r",stdin));
    // #endif
    // ios::sync_with_stdio(0);
    // cin.tie(0),cout.tie(0);   
    LinkWish::mian();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 26508kb

input:

2 2

output:

11

result:

ok "11"

Test #2:

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

input:

20 23

output:

521442928

result:

ok "521442928"

Test #3:

score: 0
Accepted
time: 76ms
memory: 27040kb

input:

200000 200000

output:

411160917

result:

ok "411160917"

Test #4:

score: 0
Accepted
time: 6ms
memory: 28316kb

input:

8 3

output:

2899

result:

ok "2899"

Test #5:

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

input:

10 9

output:

338037463

result:

ok "338037463"

Test #6:

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

input:

3 3

output:

64

result:

ok "64"

Test #7:

score: 0
Accepted
time: 9ms
memory: 26500kb

input:

9 4

output:

39733

result:

ok "39733"

Test #8:

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

input:

36 33

output:

545587245

result:

ok "545587245"

Test #9:

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

input:

35 39

output:

62117944

result:

ok "62117944"

Test #10:

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

input:

48 10

output:

264659761

result:

ok "264659761"

Test #11:

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

input:

46 30

output:

880000821

result:

ok "880000821"

Test #12:

score: 0
Accepted
time: 6ms
memory: 28352kb

input:

25 24

output:

280799864

result:

ok "280799864"

Test #13:

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

input:

17 10

output:

624958192

result:

ok "624958192"

Test #14:

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

input:

4608 9241

output:

322218996

result:

ok "322218996"

Test #15:

score: 0
Accepted
time: 6ms
memory: 27048kb

input:

3665 6137

output:

537704652

result:

ok "537704652"

Test #16:

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

input:

4192 6186

output:

971816887

result:

ok "971816887"

Test #17:

score: 0
Accepted
time: 9ms
memory: 26512kb

input:

4562 4403

output:

867628411

result:

ok "867628411"

Test #18:

score: 0
Accepted
time: 9ms
memory: 28156kb

input:

8726 3237

output:

808804305

result:

ok "808804305"

Test #19:

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

input:

5257 8166

output:

488829288

result:

ok "488829288"

Test #20:

score: 0
Accepted
time: 6ms
memory: 27480kb

input:

8013 7958

output:

215666893

result:

ok "215666893"

Test #21:

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

input:

8837 5868

output:

239261227

result:

ok "239261227"

Test #22:

score: 0
Accepted
time: 10ms
memory: 28276kb

input:

8917 5492

output:

706653412

result:

ok "706653412"

Test #23:

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

input:

9628 5378

output:

753685501

result:

ok "753685501"

Test #24:

score: 0
Accepted
time: 75ms
memory: 26912kb

input:

163762 183794

output:

141157510

result:

ok "141157510"

Test #25:

score: 0
Accepted
time: 35ms
memory: 26984kb

input:

83512 82743

output:

114622013

result:

ok "114622013"

Test #26:

score: 0
Accepted
time: 33ms
memory: 26904kb

input:

84692 56473

output:

263907717

result:

ok "263907717"

Test #27:

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

input:

31827 74195

output:

200356808

result:

ok "200356808"

Test #28:

score: 0
Accepted
time: 73ms
memory: 28040kb

input:

189921 163932

output:

845151158

result:

ok "845151158"

Test #29:

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

input:

27157 177990

output:

847356039

result:

ok "847356039"

Test #30:

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

input:

136835 39390

output:

962822638

result:

ok "962822638"

Test #31:

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

input:

118610 18795

output:

243423874

result:

ok "243423874"

Test #32:

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

input:

122070 19995

output:

531055604

result:

ok "531055604"

Test #33:

score: 0
Accepted
time: 40ms
memory: 28164kb

input:

20031 195670

output:

483162363

result:

ok "483162363"

Test #34:

score: 0
Accepted
time: 82ms
memory: 27524kb

input:

199992 199992

output:

262099623

result:

ok "262099623"

Test #35:

score: 0
Accepted
time: 82ms
memory: 27596kb

input:

200000 199992

output:

477266520

result:

ok "477266520"

Test #36:

score: 0
Accepted
time: 77ms
memory: 28148kb

input:

199999 199996

output:

165483205

result:

ok "165483205"

Test #37:

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

input:

1 1

output:

3

result:

ok "3"

Test #38:

score: 0
Accepted
time: 24ms
memory: 26776kb

input:

1 100000

output:

8828237

result:

ok "8828237"

Test #39:

score: 0
Accepted
time: 21ms
memory: 27148kb

input:

100000 2

output:

263711286

result:

ok "263711286"

Test #40:

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

input:

50 50

output:

634767411

result:

ok "634767411"

Extra Test:

score: 0
Extra Test Passed