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(){;}