メモ

yukicoderでゆるふわgolf

Project Euler 251-300 解説

これの続き
sugarknri.hatenablog.com

何を埋めてないかぐっと睨まれると垢バレする気がするけど気にしないぜ

251
x^3+y^3=(x+y)^3-3xy(x+y)は受験数学典型
後半パートは特殊な形の数たちの素因数分解をosa_k法っぽくやるやつ
整数問題みたいにmodとかgcdとかで丁寧にreductionすると早くなるらしい

252
F - Integer Convex Hull

253
状態がヤバイDPをやるだけに見えるが、シンプルな3乗があるらしい。見えません……

254
2つの操作をやっているので2つに分けて全探索

255
実験するとだいたい同じ進行をするようなので、適当にまとめる

256
2×n,3×n,4×n,…で条件を満たす敷き方ができるようなnの構造を実験により探る

257
やりようはいくらでもある
3変数2次方程式の解の列挙だと思って143,195のoverviewのテクをするか、いい感じに因数分解して全探索+素因数分解するのが正解者掲示板ではメジャー

258
いつもの
2乗かけていいので簡単

259
区間DP

260
普通にDPしようとすると空間3乗時間4乗になるが累積ORさえあれば十分なので空間2乗時間3乗になるやつ
ABC224Eが類題

261

式を整理するとペル型方程式になるので頑張ると解けます(多分)

262
まずは図を描いてみる
コースの概形がわかればあとは幾何の問題

263
素数の条件から、nは2の倍数であり3の倍数でなく5の倍数であり……。
practicalの条件から、nは2の倍数で……と小さいmodで十分たくさん場合分けして高速化すると間に合います

264
nごとにx^2+y^2=nとなる(x,y)の組を生成して、ここから3点を選ぶと外心の条件は満たす
垂心の条件は? 答え:オイラー

265
De Bruijn graphのオイラー閉路を求める問題です

266
部分和問題
半分全列挙

267
乗算で効くので順序に依存せず、「表が何回出ればいいか」という問題に
あとは高校数学

268
包除

269
桁DP
Pの根になりうる整数は……?

270
DP
正方形ではなく円だったらカタラン数になります(へー)
3乗で解けるが、制約が小さいので雑に4乗でやったほうが実装が楽という説もある

271
中国剰余定理

272
乗法群(Z/p^nZ)^*の構造を知っていますか?
あとは268と同じ

273
二個の平方数の和 - Wikipediaに式変形が書いてあるが、それよりもZ[i]での素因数分解だと理解した方が後々の役に立つだろう
雑にやると計算量はO(4^(素数の個数))、メモ化すると3ベキ

274
10と互いに素なpについて、xがpで割り切れるかどうかと10xがpで割り切れるかどうかは同じ

275
ポリオミノの賢い数え上げ方を知っていますか? 英語版wikipediaに書いてあります
Polyomino - Wikipedia

276
gcdの条件を無視したものは定数時間で求められます(面倒)
C - 擬二等辺三角形
あとは約数包除
いつものテクでO(N^(2/3))
約数包除原理 - メモ

277
3種類の操作のうち、操作後も整数であるのは、anのmod 3によって問題文中で与えられた1通り
an mod 3を気にせずに与えられた文字列に対応する操作をしたとき、全ての値が整数であるための必要十分条件は、最後の値が整数であること

278
フロベニウスの硬貨交換問題
wikipediaにもう少し一般的なケースについて答えが書いてある
Coin problem - Wikipedia
今回のケースについては合同式をこねると初等的に求まるらしい
答えを少し式変形するといつものでO(N^(3/4))とかO~(N^(2/3))とかになる
似たような問題として718がある

279
余弦定理を考えると「tan1°は有理数か?」みたいなやつになる
あとは143とかでやった
賢いことをするとO(N^(2/3))で、超賢いことをするとO(N^(3/5))で求められるらしい。何それ怖…

280
適当に状態を圧縮すると解ける。すごいライブラリを持っているなら圧縮しなくても解ける
圧縮後の状態はDAGなので普通に確率DPしたくなる。実はDPの遷移行列はO(2^N)種類しかないので、O(N^2)の行列をO(2^N)回解いて全部でO(2^N N^6)で前計算でき、これで遷移がO(N)になって全体でO(4^N N^0.5)

281
バーンサイド補題

282
テトレーションはここ
https://judge.yosupo.jp/problem/tetration_mod

283

まだまともに考えてない

284
CRT
10進で4桁くらい計算してみるとわかるんじゃないですか
別解、Henselをやろうとすると(2x-1)で割る計算をする必要があるように思えるが、x^2-x=0なので、(4x^2-4x+1)=(2x-1)^2を掛けると割り算を消せて高速化できます。びっくり

285
積分をしてください
……という問題に見えるが、図を描きましょう

286
にぶたん+DP
50次方程式を解くのでもいいらしい

287
ある種の単調性があるので、ある領域が1色かどうかのチェックをO(1)でできる
あとはやるだけ
for文回すだけの解法もあるらしい。なにそれ

288
ルジャンドルの定理

289
連結性DP
TDPC Qなど

290
桁DP
4次元でDPしたりしないように

291
こういうのはまずd=gcd(x,y)とおくのが定石。エスパーでも解けるが。
残りのパートは216で見た

292
DP
辺の候補を列挙するとだいたい「部分集合で、和が0になるものはいくつ?」になる
多分O(N^4.5)だと思う。
上の方は疎なことを使って、下はDP上は再帰にするともっと早くなる(オーダーはわからん)

293
p-smooth numberは少ない、素数は多い

294
ダブリング
遷移に対称性があるので行列累乗よりダブリングの方が真に計算量がよくなるパターン
母関数を考えてもO~で同じ計算量になる
Root of unity filterの練習問題にもなる

295

296
初等幾何を頑張るときれいな式になる
gcdでlogがつくかと思いきや、SB木で互いに素な組を列挙することでlogが消せる
上下に分けるいつものテクでO~(N^4/3)くらいになるっぽい

297
ゼッケンドルフ表現は貪欲
wikipediaの図を見ればやるべきことは明らか

298
DP
何を覚えているかを座圧

299
初等幾何を頑張るときれいな式になる
数式パートは257とだいたい同じ

300
全探索やるだけ
適当に状態を圧縮

続き
sugarknri.hatenablog.com

競プロ小説

競技プログラミングやろう!」
「なに?」
競技プログラミング
「プログラミングの勉強をしたいってこと?」
「それもあるけど、競技プログラミングはゲームだから」
「そうなんだ」
「そうだよ。……テンション低いな?」
「いや、何ヶ月か前にお前が似たようなことを言って俺にスプラ3を買わせた時のことを思い出しただけだよ。俺はでんせつになったけど、お前の最終ログインいつ?とか思ってないから安心してくれ」
「その節はどうも。今回はなんと初期投資0円で始められるから頼む」
「いいけどさ。それで、プログラミングするの?」
「そう。毎週土曜の21時にコンテストが開かれて、100分間の制限時間で解いた問題に応じてレーティングが増減する。目指せ、トップランカー! ……というゲーム」
「対人ゲームではないってことか」
PvPではないね。全員に共通の問題が出されて、多く解いた人が上位」
「要するに学校でやってるテストで競う感じ?」
「そうそう。お前そういうの好きだろ、いつも上の方にいるじゃん」
「別に好きというわけでもないが……。それで、どんな問題が出るわけ? 兵庫県警を呼べるプログラムを作るとか?」
兵庫県警?」
「いや、知らないならいい。話を進めてくれ」
「おーけー。出る問題は、簡単にいったら数学だな。具体的には……、っと、お前ってプログラミングできるんだっけ?」
「できるよ」
「マジ?」
「マジマジ。見てろよ」

>>> def plus(a, b): return a + b
>>> plus(1, 2)
3

「ほんとにできるんだ。知らなかった……」
「電卓の代わりに使ってるくらいだけどな。それで、話の続きは?」
「あーはいはい。いや、話が早くて助かるね。一番初心者向けの問題が『整数A,Bが与えられるのでA+Bを出力してください』なんだよね」
「いま作ったな。言語は何でもいいのか?」
「うん。ほんとは入出力もしないといけないんだけど、お前が実はすでにプログラミングをできることがわかったからその辺の話は省略する。知らなかったらあとでググってくれ」
「わかった。で、これを大量に解いたら勝ち? タイピング大会じゃん」
「まあこれは一番簡単な問題だからね。もうちょっと難しい問題だとこういうのがある。『何個かの正整数が与えられます。ここから和が偶数になるように2つ選ぶとき、和の最大値は?』」
「偶数が作れないときは?」
「じゃあとりあえずそういうケースはないものとして解いてくれ」
「わかった。別にそんなに難しいとは思わないけどな」

def f(array):
  n = len(array)
  ans = 0
  for i in range(n):
    for j in range(i+1, n):
      if (array[i] + array[j]) % 2 == 0:
        ans = max(ans, array[i] + array[j])
  return ans

「うーん、この言語は知らないけど、雰囲気的に合ってそう。いやー、やっぱお前賢いから話がスムーズに進むな」
「もっと褒めてくれていいぞ」
「うんうん、想定した通りの誤解法を書いてくれてありがとう」
「は?」
「いやいや、これは俺が説明してない要素だからお前は悪くない」
「わざわざこのコードを書いた俺の労力を返せ」
「まあまあ。実は、提出するプログラムには実行時間に制限がある。大抵の問題は2秒だ」
「こんなシンプルな処理で2秒も掛かることなくない?」
「じゃあ試してみよう。実行時間ってどうやって測れるか知ってる?」
「知らないけど、2秒以上かどうか判定するだけなら見てれば十分だろ」
「たしかに。それじゃあ、適当に作った長さ1万の配列を渡してみて」
「全部1でもいいか?」
「いいよ」

>>> f([1] * 10000)
2

「5秒くらいかかってるな」
「そう。これをどうにか2秒以内におさめてください」
「うーん……。ソートして枝刈りすれば良さそう」
「なに??」

def f(array):
  n = len(array)
  array.sort()
  array.reverse()
  ans = 0
  for i in range(n):
    for j in range(i+1, n):
      if array[i] + array[j] <= ans:
        break
      if (array[i] + array[j]) % 2 == 0:
        ans = max(ans, array[i] + array[j])
  return ans
>>> f([1]*10000)
2

「一瞬になったな。これで正解か?」
「えっ、どうなんだろう?」
「なんで出題者がわからないんだよ」
「用意してる答えと違うことされたから……」
「実際にはどうやって正誤判定してるんだ?」
「出題者が何十個か入力のバリエーションを先に用意しておいて、それに全部正解したら正解」
「じゃあ今からお前が作れ」
「えー」


問題:作中で提示されたコードが十分高速に動作するか判定せよ。

包除原理

■いわゆる包除原理
|\cup_{i\in S} A_i|=\sum_{\emptyset\neq T \subset S} (-1)^{|T|+1} |\cap_{i\in T}A_i|
|\cap_{i\in S} A_i|=\sum_{\emptyset\neq T \subset S} (-1)^{|T|+1} |\cup_{i\in T}A_i|
N個の条件を全て満たすものの個数を求めてください→N個の条件いずれかに違反するものの個数を求めてください、と読み替えて包除しがち
2乗のDPになりがち

■min・max
\max(S)=\sum_{\emptyset\neq T \subset S} (-1)^{|T|+1}\min(T)
\min(S)=\sum_{\emptyset\neq T \subset S} (-1)^{|T|+1}\max(T)
期待値とかで使うらしい。ところでいわゆる包除原理とどういう関係にあるんですか?

■ゼータ変換・メビウス変換系(束上の累積和/imos・メビウスの反転公式)
累積和・imosは包除原理!(素振り)
自然数の自然な大小関係に関する順序に対してやるやつ
・集合の包含関係に関する順序に対してやるやつ
自然数の整除関係に関する順序に対してやるやつ
・分割の細分に関する順序に対してやるやつ

逆行列を掛けるやつ
二項係数
G(s) = \sum_{t=0}^s \binom{s}{t} F(t) \Longleftrightarrow F(s) = \sum_{t=0}^s (-1)^{s-t} \binom{s}{t} G(t)
スターリング数
G(s) = \sum_{t=0}^s {s \brace t} F(t) \Longleftrightarrow F(s) = \sum_{t=0}^s (-1)^{s-t} {s \brack t} G(t)
G(s) = \sum_{t=0}^s {s \brack t} F(t) \Longleftrightarrow F(s) = \sum_{t=0}^s (-1)^{s-t} {s \brace t} G(t)
係数がs-tのみで決まるなら畳み込み逆元だがそうではないので……?
追記:
これって集合の包含関係に関する順序についての反転、分割の細分に関する順序についての反転らしい。
集合の包含関係に関する順序についての反転は
G(S)=\sum_{T\subset S}F(T) \Longleftrightarrow F(S)=\sum_{T\subset S}(-1)^{|S|-|T|}G(T)
で、もしここで |S|=|T| \Longrightarrow F(S)=F(T) が成り立つなら、シグマの部分を \sum_{t=0}^{|S|}\sum_{T\subset S, |T|=t} と分解するとさっきの式が出てくる。知らなかったそんなの……

■主客転倒
これ包除じゃなくない? でもメビウス関数とかでてきたら実質包除だろ(ガバ判定)
・N以下のsquare-free numberの数え上げを\sum_{d\leq \sqrt{N}}\lfloor\frac{N}{d^2}\rfloor\mu(d)でやるやつ
[x=1]を(\zeta*\mu)(x)=\sum_{d|x}\mu(d)と読み替えるのが本質。(畳み込みはDirichlet convolution)
包除じゃなくない?
・累積和の変形
\sum_{x\leq N}F(x)=\sum_{x \leq N}(\mu*F)(x)\lfloor\frac{N}{x}\rfloor
(畳み込みはDirichlet convolution)
これは本当に主客転倒してるだけ。包除なんも関係ない

ABC220Ex O(N^3)解法

これを読解した
Submission #27805654 - AtCoder Beginner Contest 220

参考にしたツイート

なお以下の説明は、これらを自分なりに再解釈したものであり、#27805654の実際の実装は異なっているので混乱のなきよう

A_{i,j}を、 i< jかつi,j間に辺があるとき1、それ以外0とする。X_iを頂点iにカメラを置かないとき1、それ以外0とする。
・監視されていない辺の個数はQ_A(X):=\sum_{i,j}A_{i,j}X_iX_j={}^tXAXなので、Q_A(X)が偶数になるようなXの個数がわかれば十分。
・行列の成分を\mathbb{F}_2とみなして、Q_A(X)=0を考えれば良い。
正則行列PによってAを{}^tPAPに置き換えてもQ_A(X)=0を満たすXの個数は変わらない。
・適切な正則行列Pを取ることで{}^tPAPを二重対角行列にできる(←?)
・二重対角行列に変換したあとの行列を元の問題に戻すと、「パスグラフに自己辺がいくつかついたものの上で問題を解いてください」となり、自明にO(N)DPができる


「適切な正則行列Pを取ることで{}^tPAPを二重対角行列にできる」というのは嘘です。
しかし、よく考えると、任意の(i,j)A_{i,j}A_{j,i}をswapしてもQ_A(X)の値は変わらないので、「i行目を使ってi-1列目の成分を掃き出すとき、i行目に溜まった邪魔な成分はi列目に押しつける」とする掃き出し法で二重対角行列にできます。

おわり

追記
二重対角行列って言葉は存在しないらしいです。ここで二重対角行列と呼んだものは、帯行列の1,0のパターン、すなわち、三重対角行列かつ下三角(or上三角)なもののことを意図しています

Formal Power Series (FPS)

この記事を書いた4時間後に以下の記事が公開されました。これを読もうね-完-
maspypy.com

以上で本質情報は終了です。ありがとうございました。以下はおまけです。


まえがき

この記事を読んでも競プロに強くはなれませんよ。
FFT多項式乗算が高速にできる原理をしらなくても、FFTを実装すれば多項式乗算ができるのと同じです。

カジュアルな定義:"足し算"と"掛け算"が定義されている集合を環という。
もうすこし正確な定義:集合と"足し算"と"掛け算"の3つ組を環という。(同じ集合に対して、違う"足し算"と"掛け算"を定義して、違う環を作ることもできるので)
本当に正確な定義:wikipediaでも読んでろ→環 (数学) - Wikipedia
ここでいう"足し算"と"掛け算"はそういう名前の二項演算のことであって、別に足し算と掛け算のことではない。でも足し算と掛け算みたいな性質(例:分配法則)が成り立っていることを要求する。
さらに、"足し算"は暗黙のうちに"引き算"ができることを要求する。"掛け算"は別に"割り算"ができることを要求しない。

例1

整数全体の集合に、+を"足し算"、×を"掛け算"と定めたものは環になる

例2

0以上M未満の整数全体の集合に、mod Mでの足し算を"足し算"、mod Mでの掛け算を"掛け算"と定めたものは環になる

例3

uint32で表すことができる数全体の集合に、bitwise xorを"足し算"、bitwise andを"掛け算"と定めたものは環になる

例4

0以上2^2^N未満の整数全体に、bitwise xorを"足し算"、Nim productを"掛け算"と定めたものは環になる
これは例3と同じ集合に別の演算が入る例でもある

例5

0以上の整数全体の集合に、minを"足し算"、+を"掛け算"と定めたものは環ではない。minは"引き算"ができないので。ちなみに、環の定義から「"引き算"ができる」を抜いたものを半環という
(余談:半群は単位的とは限らないのに半環の加法群は単位的なんですね~)

例6

整数を成分とする2×2の正方行列全体の集合に、成分ごとの和を”足し算"、行列積を"掛け算"と定めたものは環になる。ただし、この環は掛け算が可換でない。つまり、"掛け算"を×であらわしたとき、A×B=B×Aが一般には成り立たない。
"掛け算"が可換な環を可換環といい、可換でない環を非可換環という。
可換環、直感に反するので困るんだよね。そういうのは面倒なので、以下この記事では単に環と言ったときは可換環を指すものとする

形式的べき級数

定義:数列(a_0,a_1,a_2,\ldots)のことを形式的べき級数(FPS)という。
多項式? 不定元X? なんの話ですか? べき級数というのは数列のことですよ。

形式的べき級数

次で定義される環を形式的べき級数環という。
集合:全ての数列からなる集合\{(a_0,a_1,a_2,\ldots)\}
"足し算":(a_0,a_1,a_2,\ldots)+(b_0,b_1,b_2,\ldots)=(a_0+b_0,a_1+b_1,a_2+b_2,\ldots)
"掛け算":(a_0,a_1,a_2,\ldots)*(b_0,b_1,b_2,\ldots)=(c_0,c_1,c_2,\ldots) としたとき、c_i=\sum_{k=0}^{i}a_kb_{i-k}
数列の話をしてたのに急に本性表してきたなこいつ。
"足し算"と"掛け算"の定義をみるとわかるとおり、数列A:=(a_0,a_1,a_2,\ldots) に対して、不定元Xを用いた無限級数f_A(X)=a_0+a_1X+a_2X^2+\ldotsを対応させると、この"足し算"と"掛け算"は無限級数の足し算と掛け算だと思うことができるんですね~。あーあ、せっかく数列の話ってごまかしてたのに。そういうわけで以下ではFPS不定元Xを用いた無限級数を用いて表します。無駄な努力だったな……。
ところでもちろん、数列の各要素に対しても"足し算"と"掛け算"が定まっている必要がある。つまり、FPS環を考えたいなら数列の要素はなんでもいいというわけではなく、それもまた環の元である必要がある。要素が環Rの元であるような数列の集合から作ったFPS環のことをR[[X]]と書く。このとき、RR[[X]]の係数環という。

例1

上の方でやった、整数全体に普通の足し算と普通の掛け算を定めるやつ、あれのことを\mathbb{Z}と表す。(単に集合としての整数全体をさすことももちろんあるけど、環として考えますよというのを強調しています)
\mathbb{Z}[[X]]は整数係数のFPS環である。

例2

上の方でやったmodMのやつのことを数学では\mathbb{Z}/M\mathbb{Z}と書きます。(この記法はふつう剰余環を意識したものなので、上でやったことを定義とするわけではないけど、できるものは同じなのでここでは気にしないことにしましょう)
(\mathbb{Z}/M\mathbb{Z})[[X]]は係数をmod Mで考えるFPS環。

環の乗法逆元

乗法逆元の話をするまえに加法逆元の話を思い出しておこう。
"引き算"というのは、二項演算ではなく、単項演算だったんですよね(!?)
どういうことかというと、xに対して、x+y=0となるようなyのことをxの加法逆元といい、-xと表して、一般にa-bというのはa+(-b)のことだった、という話です。
これを踏まえて乗法逆元の話を考えてみる。環の"掛け算"は"割り算"ができる必要はないといったが、6/-1=-6のように、できることももちろんある。
定義:xに対して、x*y=1となるようなyのことをxの乗法逆元といい、x^{-1}と表す。
一般にa/bというのはa*b^{-1}のことだった、ということになるわけですね。
(この説明にはちょっとごまかしがあって、例えば\mathbb{Z}において6/2を「2x=6となるx」として定義する感じで、部分的には二項演算としての割り算ができることもあるんですが、そういうのは考えません)
主張:乗法逆元は存在すれば一意。
証明は各自
定義:乗法逆元が存在するような元のことを可逆元という。

例1

\mathbb{Z}の可逆元は \pm 1

例2

\mathbb{Z}/9\mathbb{Z}の可逆元は1,2,4,5,7,8
(わかってる人向けのエクスキューズ:同値類だから整数そのものじゃないとかいう難しい話を初心者にするのはやめよう!だってここで同値類の定義してないし)

例3

\mathbb{Z}[[X]]の可逆元はなんでしょう?
答え:定数項が\pm 1であるような全ての元
なんで?
1-Xの乗法逆元を求めて見よう。そのようなものが存在するなら、定義から
(1-X)(b_0+b_1X+b_2X^2+b_3X^3+\ldots)=1となる。
次数ごとに左辺と右辺を比べてみよう。
定数項:1*b_0=1b_0=1
1次の項:1*b_1+(-1)*b_0=0b_1=1
2次の項:1*b_2+(-1)*b_1=0b_2=1

ということで、以下帰納的にb_i=1と求まる。つまり(1-X)^{-1}=1+X+X^2+\ldotsとなるということ。この求め方をぐっと睨むとわかってもらえる通り、定数項が1であるようなFPSの逆元を求めようとすると1*b_n+a_1*b_{n-1}+\ldots=0という形の方程式を解いてb_nを求めることになるが、これはnの小さい順にやると自明。

??

この話って要するに、実数の逆元を考えている時に、「1÷7は0.142857……と必要なだけ計算することができますね。だから逆元は存在するんです!」と同じ論法をしている。間違ってはないんだけど、その「……」ってどういう意味やねんという話になります。いやなるかどうかはしりませんが、俺はなったので、きっちりやっておきましょう。
「可逆なfとその逆元gに対して、帰納法で任意のnについてgのn次の係数を一意に決定することができ、このとき任意のn>0に対してfgのn次の係数が0になることを具体的に計算できる。証明終わり」めでたしめでたし。いやー、収束がどうこうとかいう話をする必要があるのかと思って一瞬焦った。ちなみに例に挙げた実数の逆元の話のときは、繰り上がりとかいう概念のせいで同じ論法ではうまくいかないので収束がどうこうとかいう話をする必要があります(多分)

主張:FPS環の元は、定数項が係数環の可逆元であるとき、かつその時に限り可逆である。
証明は各自

有限項で打ち切る話

コンピューターは有限しか扱えないので、(1-X)^{-1}すらナイーブには表すことができません。
でも実数を「1÷7は……うーんまあ0.142857で近似すればいいかw」と計算するように、FPSもn次の項までで打ち切って近似計算できます。
実数だと誤差評価は面倒な話ですが、FPSのときはn次の項で打ち切ってFPS環の計算をするとn次の項までの精度があり続けます。繰り上がりがないのでね。
本質的には、「整数\mathbb{Z}をmod Mの世界\mathbb{Z}/(M)に持っていってもコンパチ」というのと同様に、「FPSR[[X]]を有限項で打ち切ってR[[X]]/(X^n)に持っていってもコンパチ」という話なんですけども。

exp

定義:有理数を含む環を係数とするFPS環において、定数項が0であるようなの元fに対して、\exp(f)=\sum_{i\geq 0}\frac{1}{i!}f^iと定める。
有理数を含むという条件は、要するに1,2,3,4,…での割り算ができますという意味です。
この定義式は\exp(X)=1+X+\frac{1}{2}X^2+\frac{1}{6}X^3+\ldotsというおなじみの式を導きますが、あくまで定義であって、実関数e^Xマクローリン展開とはなんの関係もありません。
行列Aに対してexp(A)を考えるのと同じで定義です。
(同じ名前がついている以上、本当になんの関係も無いわけではないですが、実関数の常識は忘れましょう)
余談:定義域は「定数項が0」ほど厳しい必要はなく、「定数項が冪零」でいいと思うんですが、まあ面倒なのでここでは0にしておきましょう。
\mathbb{Q}を含んで、かつ0でない冪零元が存在するような環の例としては\mathbb{Q}[t]/(t^2)があり、(\mathbb{Q}[t]/(t^2))[[X]]において\exp(t)=1+tとなります。

exp(1)

「『定数項が0であるようなFPSの元fに対して』←??? \mathbb{R}[[X]]上では\exp(1)=eだし、定数項があっても大丈夫じゃん」
大丈夫ではありません。……という話がしたいんですが、この話をするためには収束がどうこうとかいう話をする必要がある。さっき頑張って回避したのに、結局やらなきゃだめなのか……

お断り

以下、うっかり付値環の話をしてしまったので、係数が体でないと話が通らなくなってしまいました。ということで以下では係数は体です。
"付値"という言葉を使っているものの、付値の性質は完備性しか使っていないので、それを別に証明すれば環を係数とするFPS環でも同様にいえます。というかここでは完備性の証明はしていないので全部一緒です。
他にも\{f+(X^n)\}を開基とする位相を入れて(距離空間ではなく)位相空間での収束を考えてもいえるみたいです。

証明の準備

expの話がしたいだけなので、expの話ができるギリギリまでいろいろ省略
定義:体\mathbb{F}を係数とするFPS\mathbb{F}[[X]]に対して、付値\nu:\mathbb{F}[[X]]\to\mathbb{Z}_{\geq 0}\cup\{\infty\}を、\nu(f)=\min\{n \mid f \text{のn次の係数が0でない}\} と定める。このとき、FPS環の元f,gに対して、その距離をd(f,g)=2^{-\nu(f-g)}で定める。
なんのこっちゃねんという感じですが、要するに「低次の項がいっぱい一致してたらだいたい一緒」という気持ちです。「0.12345……と0.12489……は2桁目まで一致してるから、距離は10^-2くらいかなーw」というのと同じで「1+2X+3X^2+4X^3+5X^4+\ldots1+2X+4X^2+8X^3+9X^4+\ldotsは2つ目の項まで一致してるから、距離は2^-2くらいかなーw」という気持ちです。
定義:距離空間の元の列a=(a_1,a_2,\ldots)に対して、\lim_n d(x,a_n)=0 が成り立つとき、aはxに収束するという。また、あるxが存在して数列aがxに収束するとき、aは収束するという。
無限に近づくなら収束、という普通の定義。これはFPS環とか関係なく、距離空間のお話です。
定義:体係数FPS環における収束は、付値によって定まる距離による収束とする。
それはそう。普通は「位相」という言葉を使うけど、面倒なので……。
定義:無限和\sum_{i=1}^{\infty}a_iは、数列A_n=\sum_{i=1}^{n}a_iが収束するとき、その収束先を値として定義する。
要するに、\sum_{i=1}^{\infty}\frac{1}{2^i}=\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\ldotsというやつは、部分和のなす列(\frac{1}{2},\frac{3}{4},\frac{7}{8},\ldots)が1に収束するので\sum_{i=1}^{\infty}\frac{1}{2^i}=1というようにここを等号で結んじゃいますねという話です。これもFPSとか関係なく、無限和の定義に関するお話。
主張:体係数FPS環は完備離散付値環である。
証明:忘れた。代数学の本を読みましょう。
この"完備"というのは、付値によって定まる距離による距離空間としてみたとき完備であるという意味。距離空間が完備であるというのは、任意のコーシー列が収束するという意味。数列(a_n)がコーシー列であるとは、\forall \epsilon>0 \exists N \forall n,m\geq N. d(a_n,a_m)<\epsilon を満たすということ。収束列⇒コーシー列は一般に成り立つので、逆が成り立てば完備ということ。
例えば、有理数は完備ではない。なぜなら、列(3,3.1,3.14,3.141,3.1415,\ldots)はコーシー列だが、収束先が有理数の中に存在しないので。

exp再び

主張:有理数を含む体を係数とするFPS環において定義された\exp(f)は、fの定数項が0のとき、かつそのときに限り定義される。
証明:
・定数項が0⇒定義される
\exp_n(f)=\sum_{i=0}^{n-1}\frac{1}{i!}f^iとする。ここで、列F_n=\exp_n(f)を考える。少し考えると、n,m\geq N のとき、F_nF_mのN次未満の項は一致していることがわかる。つまり、数列(F_n)はコーシー列である。したがって完備性からこの数列は収束し、無限和の定義から収束先が\exp(f)である。
・定数項が0でない⇒定義されない
fの定数項をa_0\neq 0とする。A_n=\exp_n(a_0)を考えると、a_0は冪零でないので任意のnでA_n\neq A_{n+1}となる。したがって、列F_n=\exp_n(f)は任意のnでd(F_n,F_{n+1})=1となり、コーシー列でないので、特に収束列でない。

係数環が一般の環のときは、Mをa_0^M=0を満たす正整数として、証明中の「F_nF_mのN次未満の項は一致していることがわかる」を、「F_nF_mのN+1-M次未満の項は一致していることがわかる」に書き換えると定数項が冪零のケースがいえる。

つまり?

\mathbb{R}[[X]]の世界では\exp(1)=eとはしないよというのは、\exp_n(1)の列(1,2,5/2,8/3,\ldots)の定数項がいつまで経っても収束しないからですね。実数でいうところの、上の方の桁がいつまでもガチャガチャ変わってたら収束とはいわねえよという気持ちです(←これはかなり嘘が入っています。プロ各位怒らないで)

ここまでで7500文字くらいらしいです。一通りのトピックは書いたと思うし飽きたのでそろそろやめます

追記

Q.「expは\mathbb{Q}を含む環を係数とするFPS環上で定義される」って書いてるけど、mod998244353でやっとるやんけ、なんやねんぽまえ
A.完全に正しい指摘。でもn次未満の項しか必要ない場合、つまりR[[X]]/(X^n)で考えているときは、\expの代わりに\exp_nを使っても出てくるものは同じになるから、1,2,…,n-1さえ可逆なら十分なんですね~。
正確には、R[[X]]でexpが定義可能なとき以下の図が可換図式であり、右行ってから下行くルートは1,2,…,n-1さえ可逆なら定義できるので、「expが定義不可能だが、1,2,…,n-1が可逆」というときはこっちルートを採用して使いましょう、という意味。

 \require{AMScd}
  \begin{CD}
     R[[X]] @>自然な射影>> R[[X]] / (X^n)\\
     @V{\exp}VV @V{\exp_n}VV     \\
     R[[X]] @>自然な射影>> R[[X]] / (X^n)
  \end{CD}
正当性をいうには、以下が可換であることを言う必要があると思う。(右上から右下への写像がもし\exp_mなら自明だけど、実際には\exp_nなので、可換になることはby definitionとはいかないはず……)

 \require{AMScd}
  \begin{CD}
     R[[X]] /(X^m)@>自然な射影>> R[[X]] / (X^n)\\
     @V{\exp_m}VV @V{\exp_n}VV     \\
     R[[X]]  /(X^m)@>自然な射影>> R[[X]] / (X^n)
  \end{CD}


Q.logは?
A.expの逆演算として定めるよりは、天下りに定義したあと、expの逆演算になっていることを確かめる方が簡単でしょう。
定義:FPS環の元であって、定数項が1であるようなfに対して、\log(f)=\sum_{i\geq 1}\frac{(-1)^{i+1}}{i}(f-1)^i とする。
\exp(\log(f))=\log(\exp(f))=fとなることを各自確かめること

Q.指数法則とかchain ruleとか……
A.実は成り立ちます。でも、あなたのよく知るそれは、たぶん実関数の話ですよね。FPS環上の演算としてみても成立するかどうかは各自確かめること