求助QAQ
查看原帖
求助QAQ
245875
Ame__楼主2020/9/14 16:14

RT,卡了半天了还是卡不过去(,求dalao帮忙卡个常数

#include<bits/stdc++.h>
    
#define LL long long
    
#define _ 0
    
#define R register

using namespace std;
    
/*Grievous Lady*/
    
template <typename _n_> void mian(_n_ & _x_){
    _x_ = 0;int _m_ = 1;char buf_ = getchar();
    while(buf_ < '0' || buf_ > '9'){if(buf_ == '-')_m_ =- 1;buf_ = getchar();}
    do{_x_ = (_x_ << 1) + (_x_ << 3) + buf_ - '0';buf_ = getchar();}while(buf_ >= '0' && buf_ <= '9');_x_ *= _m_;
}

#define mod 998244353

const int kato = 5e5 + 10;

int n , m , len;

int fac[kato] , inv[kato] , fac_inv[kato] , A[kato] , B[kato] , S[kato] , F[kato];

#define init() \
{ \
    for(len = 1;len <= (max(n , m) << 1);len <<= 1); \
    fac[0] = fac[1] = inv[0] = inv[1] = fac_inv[0] = fac_inv[1] = 1; \
    for(R int i = 2;i <= n + m;i ++){ \
        fac[i] = 1LL * fac[i - 1] * i % mod; \
        inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod; \
        fac_inv[i] = 1LL * fac_inv[i - 1] * inv[i] % mod; \
    } \
    for(R int i = 0;i <= n;i ++){ \
        if(i & 1) A[i] = (mod - fac_inv[i]); \
        else A[i] = fac_inv[i]; \
        B[i] = fac_inv[i] * 1LL * quick_pow(i , n) % mod; \
    } \
}

inline int quick_pow(int a , int b){
    R int res = 1;
    for(; b ; b >>= 1 , a = 1LL * a * a % mod){
        if(b & 1){
            res = 1LL * res * a % mod;
        }
    }
    return res;
}

inline int c(int a , int b){
    if(a < b) return 0;
    return 1LL * fac[a] * fac_inv[b] % mod * fac_inv[a - b] % mod; 
}

inline void NTT(int *y , int len , int opt){
    R int *rev = new int[len];
    rev[0] = 0;
    for(R int i = 1;i < len;i ++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (len >> 1));
    for(R int i = 0;i < len;i ++) if(i < rev[i]) swap(y[i] , y[rev[i]]);
    for(R int i = 1;i < len;i <<= 1){
        R int g1 = quick_pow(3 , (mod - 1) / (i << 1));
        for(R int j = 0;j < len;j += (i << 1)){
            for(R int k = 0 , g = 1;k < i;k ++ , g = g * 1LL * g1 % mod){
                R int res = y[i + k + j] * 1LL * g % mod;
                y[i + k + j] = ((y[j + k] - res) % mod + mod) % mod;
                y[j + k] = (y[j + k] + res) % mod;
            }
        }
    }
    if(opt == -1){
        reverse(y + 1 , y + len);
        for(R int i = 0 , inv = quick_pow(len , mod - 2);i < len;i ++) y[i] = y[i] * 1LL * inv % mod;
    }
    delete []rev;
}

void poly_inv(int *a , int len){
    if(len == 1){ a[0] = quick_pow(a[0] , mod - 2); return;}
    R int len1 = len / 2;
    R int *g = new int[len * 2];
    for(R int i = 0;i < len1;i ++) g[i] = a[i];
    for(R int i = len1;i < len * 2;i ++) g[i] = 0;
    poly_inv(g , len1);
    for(R int i = len1;i < len * 2;i ++) g[i] = 0;
    NTT(g , len * 2 , 1) , NTT(a , len * 2 , 1);
    for(R int i = 0;i < len * 2;i ++) a[i] = ((2 * g[i] % mod - a[i] * 1LL * g[i] % mod * g[i] % mod) % mod + mod) % mod;
    NTT(a , len * 2 , -1);
    for(R int i = len;i < len * 2;i ++) a[i] = 0;
    delete []g;
}

inline void poly_dev(int *a , int len){
    for(R int i = 1;i < len;i ++) a[i - 1] = a[i] * 1LL * i % mod; 
    a[len - 1] = 0;
}

inline void poly_dev_inv(int *a , int len){
	for(R int i = len + 1 ; i ; i --) a[i] = a[i - 1] * 1LL * quick_pow(i , mod - 2) % mod;
	a[0] = 0;
}

inline void get_ln(int *a, int len){
	R int *b = new int[len * 2];
	for(R int i = 0;i < len;i ++) b[i] = a[i];
	for(R int i = len;i < len * 2;i ++) b[i] = 0;
	poly_dev(b , len); poly_inv(a , len);
    NTT(a , len * 2 , 1); NTT(b , len * 2 , 1);
	for(R int i = 0;i < len * 2;i ++) a[i] = a[i] * 1LL * b[i] % mod;
	NTT(a , len * 2, -1);
	poly_dev_inv(a , len);
	for(R int i = len;i < len * 2;i ++) a[i] = 0;
	delete []b;
}

void poly_exp(int *a , int len){
	if(len == 1) { a[0] ++; return; }
	R int len1 = len / 2; R int *g = new int[len * 2];
	for(R int i = 0;i < len1;i ++) g[i] = a[i];
	for(R int i = len1;i < len * 2;i ++) g[i] = 0;
	poly_exp(g , len1);
	for(R int i = len1;i < len * 2;i ++) g[i] = 0;
	int *lng = new int[len * 2];
	for(R int i = 0;i < len * 2;i ++) lng[i] = g[i];
	get_ln(lng , len); a[0] ++;
	for(R int i = 0;i < len;i ++){ a[i] -= lng[i]; if (a[i] < 0) a[i] += mod; }
	NTT(a , len * 2 , 1); NTT(g , len * 2 , 1);
	for(R int i = 0;i < len * 2;i ++) a[i] = a[i] * 1LL * g[i] % mod;
	NTT(a , len * 2 , -1);
	for(R int i = len;i < len * 2;i ++) a[i] = 0;
    delete []g;
}

inline int solve_I(){
    return quick_pow(m , n);
}

inline int solve_II(){
    R int res = 1;
    for(R int i = m ; i >= m - n + 1 ; i --){
        res = 1LL * res * i % mod;
    }
    return res;
}

inline int solve_III(){
    return 1LL * S[m] * fac[m] % mod;
}

inline int solve_IV(){
    int res = 0;
    for(R int i = 1;i <= m;i ++){
        res = (res + S[i]) % mod;
    }
    return res % mod;
}

inline int solve_V(){
    return n > m ? 0 : 1;
}

inline int solve_VI(){ 
    return n < m ? 0 : S[m]; 
}

inline int solve_VII(){
    return c(n + m - 1 , m - 1);
}

inline int solve_VIII(){
    return c(m , n);
}

inline int solve_IX(){
    return c(n - 1 , m - 1);
}

inline int solve_X(){
    return F[n];
}

inline int solve_XI(){
    return n > m ? 0 : 1;
}

inline int solve_XII(){
    return n < m ? 0 : F[n - m];
}

inline int Ame_(){
    // #ifdef LOCAL
        // FILE("");
    // #endif
    mian(n) , mian(m); init();
    NTT(A , len , 1); NTT(B , len , 1);
    for(R int i = 0;i < len;i ++) A[i] = 1LL * A[i] * B[i] % mod;
    NTT(A , len , -1);
    for(R int i = 0;i <= n;i ++) S[i] = A[i];
    for(R int i = 1;i <= m;i ++){
        for(R int j = i;j <= n;j += i){
            F[j] = (F[j] + (mod - inv[j / i])) % mod;
        }
    }
    poly_exp(F , len); poly_inv(F , len);
    printf("%d\n" , solve_I());
    printf("%d\n" , solve_II());
    printf("%d\n" , solve_III());
    printf("%d\n" , solve_IV());
    printf("%d\n" , solve_V());
    printf("%d\n" , solve_VI());
    printf("%d\n" , solve_VII());
    printf("%d\n" , solve_VIII());
    printf("%d\n" , solve_IX());
    printf("%d\n" , solve_X());
    printf("%d\n" , solve_XI());
    printf("%d\n" , solve_XII());
    return ~~(0^_^0);
}
    
int Ame__ = Ame_();
    
signed main(){;}
2020/9/14 16:14
加载中...