cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み
スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、
SRM | |
SRM452 の成績・ソース (要ログイン) : AC/-/- : rng_58さんの出題だったらしい。面白かったけどむずかった…
bool stone[1000][1000] = {}; int cnt = 0; for(int y=0; y<H; ++y) for(int x=0; x<W; ++x) if( (y-2<0 || !stone[y-2][x]) && (x-2<0 || !stone[y][x-2]) ) ++cnt, stone[y][x]=true;
あとで | |
LayCurseさんの記録 と Petr のソースを参考にしながら…うーむ思いつける気がしない。
// mod 演算用ユーティリティ LL MODVAL = 1000000007LL; LL ADD(LL x, LL y) { return (x+y)%MODVAL; } LL SUB(LL x, LL y) { return (x-y+MODVAL)%MODVAL; } LL MUL(LL x, LL y) { return (x*y)%MODVAL; } LL POW(LL x, LL e) { LL v = 1; for(;e;x=MUL(x,x),e>>=1) if(e&1) v = MUL(v, x); return v; } // 本体 class IOIString { public: string s; LL nI, nQ; int countIOIs(vector <string> mask) { s = accumulate( mask.begin(), mask.end(), string("") ); nI = count( s.begin(), s.end(), 'I' ); nQ = count( s.begin(), s.end(), '?' ); return SUB( POW(2,nQ), non_IOI() ); // IOIじゃないものを数えて引く } LL non_IOI() { LL ans = 0; if( nI == 0 ) ans = ADD(ans, 1); // #I == 0 if( nI == 0 ) ans = ADD(ans, nQ); // #I == 1 if( nI == 1 ) ans = ADD(ans, 1); // #I == 1 for(int D=1; D<s.size(); D+=2) for(int S=0; S<D; ++S) ans = ADD(ans, non_IOI_2(S, D)); // #I >= 2 return ans; } LL non_IOI_2( int S, int D ) { string t; for(int i=S; i<s.size(); i+=D) t += s[i]; // t 以外の部分は全部 'O' でないとダメ if( count(t.begin(), t.end(), 'I') < nI ) return 0; // t は /O*II+O*/ にマッチしないとダメ。4状態のオートマトンでDP LL q0=1, q1=0, q2=0, q3=0; for(int i=0; i<t.size(); ++i) { LL p0 = (t[i]=='O' ? q0 : t[i]=='I' ? 0 : q0); LL p1 = (t[i]=='O' ? 0 : t[i]=='I' ? q0 : q0); LL p2 = (t[i]=='O' ? 0 : t[i]=='I' ? ADD(q1,q2) : ADD(q1,q2)); LL p3 = (t[i]=='O' ? ADD(q2,q3) : t[i]=='I' ? 0 : ADD(q2,q3)); q0=p0, q1=p1, q2=p2, q3=p3; } return ADD(q2, q3); } };
あとで | |
rng_58さんのコメントを参考に。
// mod 演算用ユーティリティ LL MODVAL = 1000000007LL; LL ADD(LL x, LL y) { return (x+y)%MODVAL; } LL SUB(LL x, LL y) { return (x-y+MODVAL)%MODVAL; } LL MUL(LL x, LL y) { return (x*y)%MODVAL; } LL POW(LL x, LL e) { LL v = 1; for(;e;x=MUL(x,x),e>>=1) if(e&1) v = MUL(v, x); return v; } LL DIV(LL x, LL y) { return MUL(x, POW(y, MODVAL-2)); } LL C(LL n, LL k) { LL v = 1; k = min(k, n-k); for(LL i=1; i<=k; ++i) v = DIV(MUL(v, n-i+1), i); return v; } // 本体 class IncreasingNumber { public: int countNumbers(long long digits, int divisor) { LL N = digits; int D = divisor; // ちょうど N 桁の Increasing number //＝ // 0<=Σa<=8 な a[] を使って // 1*a[0] + 11*a[1] + ... + 111..111*(a[N-1]+1) // の形で書ける数 // //なので // // D で割れるちょうど N 桁の Increasing number の個数 //＝ // 0<=Σa<=8 な a[] で // coeff[0]*a[0] + coeff[1]*a[1] + ... + coeff[N-1]*(a[N-1]+1) = 0 // なものの個数 ( where coeff[i] := "1がi+1個並んだもの" % D ) // ステージ１ vector<LL> nc(D); // nc[m] = (coeff[i]%D==m な i の数) int ceLast; // coeff[N-1] { // coeff は高々 D 回でループしてるはず vector<int> coeff; int loop_start = -1; for(int v=1%D ;;) { loop_start = find(coeff.begin(), coeff.end(), v) - coeff.begin(); if( loop_start != coeff.size() ) break; coeff.push_back( v ); v = (v*10 + 1) % D; } int loop_len = coeff.size() - loop_start; for(int i=0; i<coeff.size() && i<N; ++i) if( i < loop_start ) nc[coeff[i]] = 1; else nc[coeff[i]] = (N-i+loop_len-1)/loop_len % MODVAL; ceLast = N-1 < loop_start ? coeff[N-1] : coeff[(N-1-loop_start)%loop_len+loop_start]; } // ステージ1.5 (毎回計算してると間に合わなかったのでキャッシュ) vector< vector<LL> > choice(D, vector<LL>(9)); for(int m=0; m<D; ++m) for(int n=0; n<=8; ++n) // nc[m] 種類のものから n 個取る取り方 choice[m][n] = (n==0 ? 1 : nc[m]==0 ? 0 : C(n+nc[m]-1, nc[m]-1)); // ステージ２ // dp[m][n][q] = 余り [0, 1, ... m] の係数から n 個使って総和を余り q にするやり方は何通り？ vector< vector< vector<LL> > > dp(D, vector< vector<LL> >(9, vector<LL>(D))); for(int m=0; m<D; ++m) dp[m][0][ceLast] = 1; for(int n=1; n<=8; ++n) dp[0][n][ceLast] = choice[0][n]; for(int m=1; m<D; ++m) for(int n=1; n<=8; ++n) for(int q=0; q<D; ++q) for(int k=0,q2=q; k<=n; ++k,q2=(q2-m+D)%D) dp[m][n][q] = ADD( dp[m][n][q], MUL( dp[m-1][n-k][q2], choice[m][k] ) ); LL ans = 0; for(int n=0; n<=8; ++n) ans = ADD(ans, dp[D-1][n][0]); return ans; } };
presented by
cafelier/k.inaba
under
