cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み
スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、
cafelier2011/03/21 12:211000、Σを消そうとして頑張って式変形したけれど、よく考えたらこのΣは1～9までしか回らないので、普通に最初に立式した通りに計算すればよかったのではないだろうか。反省
delta23232011/03/22 01:36初めまして，いつも勉強させて頂いています。自分のコードでなのですが，式変形した場合，テストケースで最大約600msかかり，しないとTLEを起こしてしまいました。式変形をする事も出題した方の意図だったのでしょうか。
cafelier2011/03/22 10:58自分のコードでも試してみたところ、確かにmint X = 0;for(int d=1; d<=9; ++d){ mint f = d*v[d]*FACT[N-1]; for(int i=1; i<=9; ++i) f = f * FACT_INV[v[i]]; X = X + f;}answer = answer + X * ONES[N];でTLEでした。なるほど。Σ と C(...) の計算で x9x9 で 2Mx81 回の整数演算となると厳しかったですね。なかなか絶妙なラインの問題設定でした。
presented by cafelier/k.inaba under
自分のコードでなのですが，式変形した場合，テストケースで最大約600msかかり，しないとTLEを起こしてしまいました。式変形をする事も出題した方の意図だったのでしょうか。
mint X = 0;
for(int d=1; d<=9; ++d){
mint f = d*v[d]*FACT[N-1];
for(int i=1; i<=9; ++i)
f = f * FACT_INV[v[i]];
X = X + f;
}
answer = answer + X * ONES[N];
でTLEでした。なるほど。Σ と C(...) の計算で x9x9 で 2Mx81 回の整数演算となると厳しかったですね。なかなか絶妙なラインの問題設定でした。