本番ラスト30秒でギリギリ通った。
http://community.topcoder.com/stat?c=problem_statement&pm=13712
http://community.topcoder.com/stat?c=problem_statement&pm=13720
問題
10進数かつleading zeroを含めM桁の数値がある。
このM桁の数についてN個の質問に対する回答が与えられる。
各質問は、M桁のうちどの桁を残したかの情報からなる。
残した桁を連結してできる数値を9で割った余りは0であることがわかっている。
これらの質問の内容と回答から、Mとしてあり得る数値の組み合わせ数を求めよ。
Div2 HardではMの範囲が小さくなっている。
解法
数値を９で割った余りは、各桁の総和を９で割った余りに等しい。
よって、各質問に対し、残った桁の総和が９の倍数となる組み合わせを求めればよい。
Nの上限が5なので、以後N==5の場合で説明する。
安直な方法としては、上の桁からDPを行い0～9を入れたときの各問題における余りに対応する組み合わせを求めていく手が考えられる。
この場合、DP[桁][1問目に相当する桁の総和の9の剰余][2問目][3問目][4問目][5問目]=組み合わせ数を更新していく。
ただ、この問題はMの上限が5000、5問分の9の剰余の組み合わせは9^5、さらに各桁で0～9の10通りを試すことを考えると5000*9^5*10回のループが必要でTLEする。
ここで、各桁において各質問における残す・残さないの組み合わせは32通りしかない(実際は問題文の条件より31通り)事に注目する。
そこで各32通りに対し、そのような桁が何個あるかを求めておく。
次に、(0～9)の数字をx回足したとき、9で割った余りがyになるような組み合わせ数F(x,y)を先にDPで求めておく。
これはx≦Mの範囲で求めると5000*9*10回ループでDPすればいいので十分に間に合う。
このF(x,y)を用い、左記のDP[桁][1問目][2問目][3問目][4問目][5問目]を高速化する。
桁毎にDPを行うのではなく、質問の組み合わせ毎32通りについて処理を行う。
質問p番目に相当する質問がq個ある場合、0～8の各yに対し
DP[p+1][1問目+M1*y][2問目+M2*y][3問目+M3*y][4問目+M4*y][5問目+M5*y] += DP[p][1問目][2問目][3問目][4問目][5問目] * F(q,y)
で値を更新していく。M1～M5は、p番目の質問が各桁を含むものかどうかを示す。
すなわち、q個の(0～9)の和で剰余がyとなる組み合わせがF(q,y)通りあると分かっているので、p問目が対象とする桁に対してyを加算した状態に対し、答えを足しこんでいく。
こうすると処理回数は(2^N * 9^(N+1))なのでなんとか間に合う。
ll mo=1000000007; ll p9[8]; int num[50]; ll dp[5050][10]; ll dp2[2][9*9*9*9*10]; class Nine { public: int count(int N, vector <int> d) { int x,y,i,z,ad; p9[0]=1; FOR(i,6) p9[i+1]=p9[i]*9; ZERO(num); FOR(i,d.size()) num[d[i]]++; ZERO(dp); dp[0][0]=1; FOR(i,5020) { FOR(x,9) FOR(y,10) dp[i+1][(x+y)%9] += dp[i][x]; FOR(x,9) dp[i+1][x]%=mo; } ZERO(dp2); dp2[0][0]=1; FOR(i,1<<N) { int cur=i&1,tar=cur^1; ZERO(dp2[tar]); FOR(x,p9[N]) if(dp2[cur][x]) { dp2[cur][x] %= mo; FOR(ad,9) if(dp[num[i]][ad]) { int nex=x; FOR(y,5) if(i&(1<<y)) { int cu=nex/p9[y]%9; nex -= cu*p9[y]; cu=(cu+ad)%9; nex += cu*p9[y]; } dp2[tar][nex] += dp2[cur][x]*dp[num[i]][ad]%mo; } } } return dp2[0][0] % mo; } }
まとめ
本番提出1分前までこの9倍かかるコードを書いていた。
ややこしい問題だが解ききれて良かった。
