Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[問題案]Exp of Formal Power Series(exp_of_formal_power_series) #65

Closed
yosupo06 opened this issue Sep 19, 2019 · 7 comments
Closed

[問題案]Exp of Formal Power Series(exp_of_formal_power_series) #65

yosupo06 opened this issue Sep 19, 2019 · 7 comments

Comments

@yosupo06
Copy link
Owner

@yosupo06 yosupo06 commented Sep 19, 2019

母関数 $f(x) = \sum_{i = 0}^{N - 1} a_i x^i$ が与えられます。この母関数のexpの先頭 $N$ 項を求めてください。つまり

$(\sum_{k = 0}^{N - 1} f(x)^k / k!) % (x^N)$ を出力してください

入力

N
a_0 a_1 a_2 ... a_{N - 1}

制約

  • 1 <= N <= 500,000
  • a_0 == 0
  • 0 <= a_i < 998244353

出力

b_0 b_1 ... b_{N - 1}

ただし g(x) = \sum_{i = 0}^{N - 1} b_i x^i とする

#63

@yosupo06 yosupo06 added this to 作業待ち in 問題リスト Sep 19, 2019
@hos-lyric

This comment has been minimized.

Copy link
Contributor

@hos-lyric hos-lyric commented Sep 19, 2019

あとで変えられる部分はまた pull request なりなんなりだそうと思います

mod が書いてないことに,気づいたんですよね
a_0 以外は 0 <= a_i < 998244353 ですか

@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Sep 19, 2019

そうです(fixed)

@hos-lyric

This comment has been minimized.

Copy link
Contributor

@hos-lyric hos-lyric commented Sep 19, 2019

問題名は後から直すのがめんどそうということにも気づけた
通常型母関数というよりは形式的冪級数じゃないかなとちょっと思った

@yosupo06 yosupo06 changed the title [問題案] exp of OGF(exp_of_ogf) [問題案] exp of power series(exp_of_power_series) Sep 19, 2019
@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Sep 19, 2019

ありがとうございます(fixed)

@hos-lyric

This comment has been minimized.

Copy link
Contributor

@hos-lyric hos-lyric commented Sep 19, 2019

formal power series を fps と呼ぶ文化広めたいですね (これは半分提案半分雑談です)
(いやなんでもよいんですけど,ながいので……)

https://docs.sympy.org/latest/modules/series/formal.html#sympy.series.formal.fps
用法はあるらしい (?)

@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Sep 19, 2019

formalが無いと意味がちょっと変わるのかな、とりあえず付けておきます

@yosupo06 yosupo06 changed the title [問題案] exp of power series(exp_of_power_series) [問題案]Exp of Formal Power Series(exp_of_formal_power_series) Sep 19, 2019
@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Sep 20, 2019

問題名は(もちろん限度はあるけど)ある程度までは長くても困らないことに気付いたんで、あんまり有名じゃない(or 略する前が長すぎない)略称は使わないことにしました(これも深く考えてなかったんで既に統一感が終わってるんですが)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
問題リスト
  
作成済み
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
2 participants
You can’t perform that action at this time.