Submission #61382873

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ui = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(l);i>=(r);--i)
#define repn(i,n) for(int i=0;i<(n);++i)
#define sizc(x) ((int)(x).size())
#define allc(x) (x).begin(),(x).end()
#define fir first
#define sec second
constexpr int N = 3e5+5;
using Z = modint998244353;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

using ui = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(l);i>=(r);--i)
#define repn(i,n) for(int i=0;i<(n);++i)
#define sizc(x) ((int)(x).size())
#define allc(x) (x).begin(),(x).end()
#define fir first
#define sec second

constexpr int N = 3e5+5;

using Z = modint998244353;

int n;

Z fac[N],invf[N];
void init(int n){
    fac[0]=1;
    rep(i,1,n)fac[i]=fac[i-1]*i;
    invf[n]=1/fac[n];
    per(i,n,1)invf[i-1]=invf[i]*i;
}

bitset<N> vis;
void sieve(int n){
    rep(i,2,n)if(!vis[i])rep(j,2,n/i)vis[i*j]=1;
}

Z g[N],f[N];

signed main(){
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

    cin>>n,init(n),sieve(n);
    g[1]=n;
    rep(i,3,n)if(!vis[i])g[i]=fac[i-1]/2*n*i;
    f[0]=1;
    auto dc=[&](auto &&self,int l,int r)->void{
        if(l==r){if(l)f[l]*=fac[l-1];return;}
        int mid=l+r>>1;
        self(self,l,mid);
        vector<Z> a(mid-l+1),b(r-l+1);
        rep(i,l,mid)a[i-l]=f[i]*invf[i];
        rep(i,1,r-l)b[i]=g[i]*invf[i-1];
        vector<Z> res=convolution(a,b);
        rep(i,mid+1,r)f[i]+=res[i-l];
        self(self,mid+1,r);
    };dc(dc,0,n);
    cout<<(f[n]/n/n).val()<<'\n';
}

Submission Info

Compile Error

Main.cpp: In instantiation of ‘main()::<lambda(auto:55&&, int, int)> [with auto:55 = main()::<lambda(auto:55&&, int, int)>&]’:
Main.cpp:59:9:   required from here
Main.cpp:51:18: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   51 |         int mid=l+r>>1;
      |                 ~^~

Judge Result