「998244353 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita
1. なぜ 998244353 で割るのか？ 最初はこのような設問を見るとぎょっとしてしまいますが、実はとても自然な問題設定です。 $998244353$ で割らないと、答えの桁数がとてつもなく大きくなってしまうことがあります。このとき以下のような問題が生じます: 多倍長整数がサポートされている言語とされていない言語とで有利不利が生じる 10000 桁にも及ぶような巨大な整数を扱うとなると計算時間が膨大にかかってしまう 1 番目の事情はプログラミングコンテストに特有のものと思えなくもないですが、2 番目の事情は切実です。整数の足し算や掛け算などを実施するとき、桁数があまりにも大きくなると桁数に応じた計算時間がかかってしまいます。実用的にもそのような巨大な整数を扱うときは、いくつかの素数で割ったあまりを計算しておいて、最後に中国剰余定理を適用して復元することも多いです。 なぜ 9982443
vim使い向けのGDBフロントエンド、CGDBが便利という話 - id:anatooのブログ
最近PHPの中身を探ることが多くなってきました。以前PHPカンファレンス2011で話した「PHPをハックしてオレオレ文法を追加する」のなかでは、PHPの内部の動きを知るにはソースコードリーティングだけだと実際にどんな動きをしているのかわかりづらいので、そういう時はGDB使ってやるといいよ、というふうなことを言いました。とかいいつつ、実際にはGDBを直接使ってはいません。操作がプリミティブ過ぎて使いづらいからです。代わりに、GDBフロントエンドの一つであるCGDBというソフトウェアを利用しています。 この記事ではこのCGDBの概要について簡単に説明します。 CGDBの何が便利なのか GDBフロントエンドには、DDD、Insightなどがあります。また、純粋なGDBフロントエンドの他にも、Eclipse CDT、XcodeなどGDBフロントエンドとしての機能を有しているIDEなどがあります。こ
エラーハンドリングモデル考察
エラーハンドリングモデルに関する考察。 エラーハンドリング勉強会 ( http://partake.in/events/9874b92a-4cf0-4a20-a3fe-951239da5612 )にて発表。Read less
一歩先行くJavaプログラマが読むべきオープンソースソフトウェア10選 - 設計と実装の狭間で。
10万行コード読んだらJava分かるよってTwitterに書いたらすげぇ勢いでRTされたので、調子に乗って捕捉エントリ書くよ。 Java Core API JDKインストールしたディレクトリに入ってるsrc.zipを展開すると入ってるから読むと良いよ。 すぐ近くにあるのから読むってのはメンタル的に楽でいい。 厳密にはOSSじゃなくて単に公開されてるってだけなんだけども、JavaプログラマなのにコアAPIのコード読んでないとか無いよね？ どれから読めば良いか分からんかったら、 java.lang java.util java.io java.text 辺りをまずはキチンと理解すること。当然コードを読み終わったら、それを使ってコードを書く事。 OpenJDK http://hg.openjdk.java.net/jdk7/jdk7 OpenJDKを読むことで、プログラム言語してのJavaではな
プログラミングコンテストチャレンジブックを読みながらダイクストラ法を実装したよ - nokunoの日記
前回のベルマンフォード法から時間があいてしまいましたが、プログラミングコンテストチャレンジブック（通称アリ本）を読みながらグラフの最短経路を求めるためのアルゴリズム、ダイクストラ法を実装しました。 ベルマンフォード法 - nokunoの日記ダイクストラ法 - Wikipedia ダイクストラ法ではグラフ中のノードを次の3つに分類します。 未探索 探索済み 次の探索候補この「次の探索候補」の中から最もコストの小さいノードを選んで探索済みとし、その隣接ノードのコストを更新するというのがダイクストラ法の根本のアルゴリズムとなります。 最初の実装それでは実装を見ていきましょう。まず最初の実装では次に探索済みとなる要素を線形探索しているためあまり効率的ではありません。 #include using namespace std; #define MAX_E 20 #define MAX_V 7 #d
GRASPパターン - Strategic Choice
GRASPについてGeneral（汎用）Responsibility（責任）Assignment（割り当て）Software（ソフトウェア）Patterns（パターン）オブジェクト指向設計の基本とは、適切なクラスに適切な責任を割り当てることであるここでいう責任とは、クラスが何らかの処理を実行する責任（実行責任）と、クラスが持つ情報を把握する責任（情報把握責任）のことである。そして、この責任割り当ての指針がGRASPである。責任駆動開発設計responsibility-driven design : RDD「責任」「役割」「強調」の観点から設計を行う。GRASPはRDD一部であり、その手段である。一覧責任を割り当てる際の指針 生成者情報エキスパートコントローラ保守性・拡張性・再利用性を高めるための指針 疎結合性高凝集性クラスを洗練する時に使用 多相性人工品間接化バリエーション防護壁参考実践U
Welcome to Scala hack-a-thon #1’s documentation! — Scala hack-a-thon #1 v1.0 documentation
Welcome to Scala hack-a-thon #1’s documentation!¶ Contents: 1. Scala開発環境の準備 1.1. Scala実行環境のインストール 1.2. 開発環境のセットアップ 1.3. その他やっておくと便利なこと 2. Scalaの開発スタイル 2.1. ソースコードとコンパイル 2.2. アプリケーションを作り、実行する 2.3. インタプリタでの実行 3. Scalaの基本 3.1. 基本的な文法 3.2. 関数編 3.3. クラス、オブジェクト、トレイト 3.4. トレイト(trait) 3.5. importとpackage 3.6. ケースクラスとパターンマッチ 4. Scalaの高度な機能 4.1. Implicit ConversionとImplicit Parameter 4.2. 型のパラメータ化 4.3. 遅延評価
overlasting.net
overlasting.net 2019 Copyright. All Rights Reserved. The Sponsored Listings displayed above are served automatically by a third party. Neither the service provider nor the domain owner maintain any relationship with the advertisers. In case of trademark issues please contact the domain owner directly (contact information can be found in whois). Privacy Policy
誤り許容カウント法(lossy count method)のサンプルプログラム
誤り許容カウント法(lossy count method)のサンプルプログラム 2010-05-12-1 [Programming][Algorithm] 1行1ラベル形式で、 1万種類のラベルを持つ、 100万行のデータがあるとします （ラベルの頻度分布はジップの法則にだいたい準拠するとします）。 各ラベルの頻度をハッシュを使ってカウントするとなると、ハッシュエントリ1万個分のメモリ容量が必要になります。（1万じゃたいしたことないな、という人はもっと大きな数に置き換えて読んでください。） しかし、カウント後に高頻度のものしか使わないということも多いと思います。例えば頻度5000以上のもののみ取り出してあとはいらない、とか。 そうなると、全部のラベルのカウントデータを最後まで保持するのは無駄に思えます。 そこで登場するのが「誤り許容カウント法(lossy count method)」。 低
Contracts for Java
The latest news from Google on open source releases, major projects, events, and student outreach programs. If you’ve ever spent hours debugging your Java code, today’s blog post is for you. Often bugs that are frustratingly elusive and hard to track down appear simple or even trivial once you have found their cause (the fault). Why are those bugs hard to track down? One possibility is that the fa
深さ優先探索と幅優先探索 - juntkの日記
木構造のコレを元に探索コード書いてみた。 Tree#search 深さ優先探索。 user system total real depth-first search: 0.000000 0.000000 0.000000 ( 0.000058) 0.000000 0.000000 0.000000 ( 0.000033) Tree#search_b 幅優先探索。 Beadth first search: 0.000000 0.000000 0.000000 ( 0.000104) 0.000000 0.000000 0.000000 ( 0.000078) 実行時間 最も深いノード*1を探索対象にしたので、幅優先探索よりも深さ優先探索の実行時間が短ければ正しい動作のはず。 コード require "benchmark" class Tree attr_reader :root, :chil
トライ（ダブル配列，簡潔データ構造）と STL コンテナの比較（最新版） - ny23の日記
[2011/11/30 更新; std::(unordered_)map でメモリ使用量を見積もる - ny23の日記に従い，STL コンテナのメモリ使用量を計測] [2011/02/21 更新: marisa-trie 0.1.3; 発表資料（Prefix/Patricia Trie の入れ子による辞書圧縮） - やた＠はてな日記 にてこの記事の実験結果を引用されているので，以後原則更新しないこととする．なお，marisa-trie は 検索時間が短くなりました - やた＠はてな日記 にあるように，marisa-0.2.0-beta3 以降ではさらに検索が速くなっています．] [2011/02/18 更新: marisa-trie の仕様変更に伴い，追記の記述を整合性が取れるよう変更; 最新版では未確認] id:s-yata さんが marisa-trie を公開されたので，例によってベ
wat-arrayを使った2次元探索プログラム - tsubosakaの日記
岡野原氏の作成したwavelet木を使った高速配列処理ライブラリwat-arrayを利用して、2次元探索のプログラムを書いてみた。 なお、自分はwavelet木のアルゴリズムについては全く分かってないですが、wat-arrayでは配列に対して、操作を行うインターフェイスがしっかり与えられているのでそれを見ながら作りました。 問題定義 2次元座標の集合P={(x,y)}が与えられる。Queryとして(xs,xe,ys,ye)が与えられたときにPの中でxs <= x < x, ys <= y < yeを満たす点の数を答えるというものを考える。 なお、Pの内容は途中で変化したりすることはないものとする(変更が加わった場合は一から作り直す)。 インターフェースとしては次のようになる、2次元座標の表現にはpairを用いることにする。 namespace wat2DSearch{ typedef st
新しいトライのライブラリを公開しました - やた＠はてな日記
概要 トライのライブラリを公開しました．ドキュメントはまったく用意できていませんが，とりあえず使えます．（追記 2011-01-09）ドキュメントを追加しました． http://code.google.com/p/marisa-trie/ ドキュメント ベンチマーク 使い方 インタフェース ツール インストール ビルド・インストールの方法は configure と make です．以下のようにすればインストールできます． ./configure make make check sudo make install インストールせずに試したいという方は，make install を省略して，tools/ 内部のツールを使うなり，lib/marisa/trie.h を見て使い方を確認するなりしてください．インストールせずにライブラリを利用するには，lib/ 以下のヘッダすべてと lib/libm
オープンソースのTrieライブラリまとめ - nokunoの日記
最近、趣味で開発しているStaKKのためにTrieライブラリを書いているのですが、参考にするためオープンソースのTrieライブラリについて調べました。簡潔データ構造を用いたものが中心です。 @hillbig氏によるもの tx LOUDSによる圧縮でメモリ使用量を削減したTrieライブラリ。 関連記事：Tx: Succinct Trie Data Structure Engineering the LOUDS Succinct Tree Representation - 射撃しつつ前転ux txの改良版。tailの圧縮によりtxの1/2くらいのサイズになるらしい。要チェック。 関連記事：ux... - ny23の日記id:s-yata 氏によるもの taiju LOUDSを含む簡潔データ構造を用いた大規模Trieライブラリ。sumire-triesインメモリの簡潔データ構造を実装した大規模T
バイナリシリアライズ形式「MessagePack」 - Blog by Sadayuki Furuhashi
Googleが公開したバイナリエンコード手法であるProtocol Buffersは、クライアントとサーバーの両方でシリアライズ形式を取り決めておき（IDL）、双方がそれに従ってデータをやりとりするようにします。 この方法では高速なデータのやりとりができる反面、IDLを書かなければならない、仕様を変えるたびにIDLを書き直さなければならない（あらかじめしっかりとIDLを設計しておかないとプログラミングを始められない）という面倒さがあります。 ※追記：Protocol BuffersのデシリアライザはIDLに記述されていないデータが来ても無視するので（Updating A Message Type - Protocol Buffers Language Guide）、仕様を拡張していっても問題ないようです。 一方JSONやYAMLなどのシリアライズ形式では、何も考えずにシリアライズしたデータ
Tutorial on Curry [CurryWiki]
This web page contains a tutorial introduction to the declarative programming language Curry. Note that the tutorial is not yet finalized. However, it might be already useful for people who want to learn programming with Curry. For a detailed definition of all features of Curry, you should look into the Curry Report. PDF all example programs as a zip file If you are interested in the slides of an
BigQueryってなんぞ？ - スティルハウスの書庫の書庫
Google I/O 2010では、Google Storageと合わせて利用する新機能「BigQuery」が発表されました（これもApp Engineとは個別のプロダクトです）。ひとことで言えば「何100億件のデータも数秒〜数10秒で集計できる、大規模並列クエリサービス」です。既存のOLAPやデータウェアハウスに相当するもので、更新処理には使えません。 MapReduceとはどう違う？ 大規模なデータセットに対して多数のサーバで並列処理するという点ではMapReduceに似ていますが、処理結果がすぐに得られる点、そしてSQLっぽいクエリ言語で表現できる集計処理しか実行できない（mapperやreducerを定義してデータを任意の方法で加工したりできない）点がMRとは異なります。MRよりさらに高水準の分散処理サービスです（MR＋Hiveに近いかもしれません）。 リンク集 BigQuery
自分のマシン上でpython走らせたときのパフォーマンス - 科学と非科学の迷宮
kinabaさんのアルゴリズムコンテストの挑み方を真面目に読み直していると、こんな一文が。 自分の持っている計算機が、どのくらいのスピードで「計算」できるか、ご存じでしょうか？ 感覚的には億のオーダー、つまり 10^8 超えたらGCJ Largeでは黄色信号かなあ(制限時間8分のため)、というぐらいには理解しているのですが、確かに正確な性能はわかりません。 というわけで測ってみることにしました。 測定環境 マシン HW Thinkpad X61 CPU Intel Core2 Duo T7500 2.20GHz Disk SSD 80GB Memory 2GB ソフトウェア OS Fedora 12 kernel 2.6.32-12-115.fc12.i686.PAE python 2.6.2 使用言語 python 測定結果 大体表の通り。 時間はほぼ全てリニアに伸びてます。 ループ回数
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
[GCJ] Round1-A参加報告 #gcj - nokunoの日記