[過去ﾛｸﾞ] プログラミングのお題スレ Part21 (1002ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
781(1): デフォルトの名無しさん [] 2023/06/15(木) 01:02:15.13 ID:h+F4OSrU(1/2) AAS
>>780
780(1): デフォルトの名無しさん [] 2023/06/15(木) 00:31:42.16 ID:K1O29FUe(1/3) AAS
>>774
フーリエ変換でなぜ計算できるのか知らないが、とりあえずRに移植してみたら
5秒で完了できなかった。www.ideone.com/nhGFqi

tio.runで実行したら5.975秒かかった。fft関数がRのよりnumpyのの方が速いのか?
RのはUses C translation of Fortran code in Singleton (1979)だそうだが。
数え上げの問題を形式的冪級数の議論に対応づけることができる
形式的冪級数同士の積は長さ n が2の冪なら高速フーリエ変換による畳み込みで O(n log n) で計算できる
Rのfftはおそらく高速になる2の冪の長さのfftをしていないんだと思う
788: デフォルトの名無しさん [] 2023/06/15(木) 23:56:30.25 ID:h+F4OSrU(2/2) AAS
>>787
787(1): デフォルトの名無しさん [sage] 2023/06/15(木) 23:01:51.41 ID:4JYva2qR(2/2) AAS
だからそこでfft使うなんてのがわかってないって言ってるの
わからんかね？
忖度して読み取ると多倍長整数の乗算の話をしているのだと思うけれど >>738
738(13): デフォルトの名無しさん [] 2023/06/08(木) 22:14:54.10 ID:B/+C/EDE(2/2) AAS
お題：1234567以下の素数 a, b, c で a + b + c = 1234567 かつ a ≤ b ≤ c を満たす組み合わせは何通りあるか計算せよ。
の問題を解く上ではそもそもあまり関係がない
素数になる次数の係数が 1 でそれ以外が 0 の形式的冪級数を考えてそれを3回乗算して N = 1234567 の次数の係数を求める問題に帰着させているだけ
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.215s