锐客网

  1. 首页 > it技术 > >

数论|hdu 5322 Hope（分治+NTT）

分治数论ntt

分治+NTT。思路是多校题解上的思路，我只是敲了一遍代码。
下面图片引用自：http://blog.sina.com.cn/s/blog_15139f1a10102vo6q.html
数论|hdu 5322 Hope（分治+NTT）
文章图片


【数论|hdu 5322 Hope（分治+NTT）】由于给定MOD是一个质数，并且998244353=119*2^23 + 1，所以可以用NTT直接代替FFT。

//#pragma comment(linker, "/STACK:1024000000,1024000000") #include #include #include #include #include #include #include #include #include #include #define LL int #define MP make_pair #define xx first #define yy second #define INF 1200000000000000000ll #define lson l, m, rt << 1 #define rson m + 1, r, rt << 1|1 #define CLR(a, b) memset(a, b, sizeof(a)) using namespace std; const int maxn = 100100; const int N = 1 << 19; const int P = 998244353; const int G = 3; const int NUM = 20; LLwn[NUM]; LL quick_mod(LL a, LL b, LL mod) { LL ans = 1; a %= mod; while(b) { if(b & 1) ans = 1ll * ans * a % mod; a = 1ll * a * a % mod; b >>= 1; } return ans; }void GetWn() { for(int i=0; i> 1; for(int i = 1; i < len - 1; i ++) { if(i < j) swap(a[i], a[j]); int k = len >> 1; while(j >= k) { j -= k; k >>= 1; } if(j < k) j += k; } }void NTT(LL a[], int len, int on) { Rader(a, len); int id = 0; for(int h = 2; h <= len; h <<= 1) { id++; for(int j = 0; j < len; j += h) { LL w = 1; for(int k = j; k < j + h / 2; k++) { LL u = a[k]; LL t = 1ll * w * (a[k + h / 2]) % P; a[k] = (u + t) % P; a[k + h / 2] = (u - t + P) % P; w = 1ll * w * wn[id] % P; } } } if(on == -1) { for(int i = 1; i < len / 2; i++) swap(a[i], a[len - i]); LL Inv = quick_mod(len, P - 2, P); for(int i = 0; i < len; i++) a[i] = 1ll * a[i] * Inv % P; } }void Conv(LL a[], LL b[], int n) { NTT(a, n, 1); NTT(b, n, 1); for(int i = 0; i < n; i++) a[i] = 1ll * a[i] * b[i] % P; NTT(a, n, -1); }LL dp[maxn]; LL fac[maxn], Invfac[maxn]; LL a[N], b[N]; void divide(int l, int r) { if(l == r) return ; int len = 1, m = (l + r) >> 1; divide(l, m); while(len <= (r - l + 1)) len <<= 1; for(int i = 0; i < len; i++) { a[i] = b[i] = 0; b[i] = 1ll*i*i%P; } for(int i = l; i <= m; i++) { a[i-l+1] = 1ll*dp[i]*Invfac[i]%P; } Conv(a, b, len); for(int i = m + 1; i <= r; i ++) dp[i] = (dp[i] + 1ll * fac[i - 1] * a[i - l + 1] % P) % P; divide(m + 1, r); }void init() { GetWn(); fac[0] = Invfac[0] = 1; for(int i = 1; i <= 100000; i ++) { fac[i] = 1ll * fac[i - 1] * i % P; Invfac[i] = quick_mod(fac[i], P - 2, P); } CLR(dp, 0); dp[0] = 1; divide(0, 100000); }int main() { init(); int n; while(scanf("%d", &n) != EOF) printf("%d\n", dp[n]); }



    推荐阅读


    上一篇：Android属性动画上手实现各种动画效果，自定义动画，抛物线等

    下一篇：C++|把二元查找树转变成排序的双向链表