{"image_url":null,"blog_url":"https://yosupo.hatenablog.com/","url":"https://yosupo.hatenablog.com/entry/2024/03/19/213339","author_url":"https://blog.hatena.ne.jp/yosupo/","provider_url":"https://hatena.blog","categories":[],"blog_title":"\u3088\u3059\u307d\u306e\u65e5\u8a18","version":"1.0","provider_name":"Hatena Blog","description":"\u554f\u984c \u9577\u3055N\u306e\u6574\u6570\u5217a_i\u304c\u4e0e\u3048\u3089\u308c\u307e\u3059 $Q$\u500b\u306e\u30af\u30a8\u30ea\u3092\u51e6\u7406\u3057\u3066\u304f\u3060\u3055\u3044 given l, r, x: $a_l \\cdots a_r$\u3092$x$\u500d given l, r: $a_l \\times a_{l+1} \\times \\cdots \\times a_r \\bmod 998244353$\u3092\u51fa\u529b $O(\\log N)$ per query\u3067\u89e3\u3051\u308b\u304c\u304a\u305d\u3089\u304f$O( \\log^{2} N)$\u3068\u8b58\u5225\u4e0d\u53ef\u80fd\u3002 \u3061\u306a\u307f\u306b\u5143\u30cd\u30bf\u306f\u3053\u308c(\u89e3\u6cd5\u306f\u9055\u3046): \u533a\u9593\u4ee3\u5165/\u533a\u9593\u7a4d \u0398(logN)/query - noshi91\u306e\u30e1\u30e2 $O(\\log^{2} N)$ \u89e3\u6cd5 \u666e\u901a\u306b\u9045\u5ef6\u4f1d\u642csegtree\u306b\u4e57\u305b\u308b\u3002\u2026","title":"\u533a\u9593mul \u533a\u9593\u7a4d O(log N)","html":"<iframe src=\"https://hatenablog-parts.com/embed?url=https%3A%2F%2Fyosupo.hatenablog.com%2Fentry%2F2024%2F03%2F19%2F213339\" title=\"\u533a\u9593mul \u533a\u9593\u7a4d O(log N) - \u3088\u3059\u307d\u306e\u65e5\u8a18\" class=\"embed-card embed-blogcard\" scrolling=\"no\" frameborder=\"0\" style=\"display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;\"></iframe>","width":"100%","published":"2024-03-19 21:33:39","author_name":"yosupo","type":"rich","height":"190"}