方針はたちやすい。
https://community.topcoder.com/stat?c=problem_statement&pm=17591
問題
D桁の正整数のうち、S次updown数であるものはいくつあるか。
ある整数がS次updown数であるとは、S次up数でもありS字down数でもあることを意味する。
S次up数とは、D桁の整数からS桁抜き出したとき、前から順に狭義単調増加になる部分があることを意味する。
S次up数とは同様に狭義単調減少となる部分があることを意味する。
解法
LIS/LDSを作るときに、「k要素のLISを作れるときにk個目の要素の最小値」を管理するような数列を作る。
狭義単調増加の場合、この数列は各要素distinctであるはずである。
そのため、これをbitmaskで表現すれば、LIS側で10bit、LDS側で10bit使えば、上記配列をLIS/LDS双方管理できる。
あとは、D桁分0~9のそれぞれを選んだ時にどうなるかを総当たりしていけばよい。
const ll mo=1000000007; ll from[1<<10][1<<10]; ll to[1<<10][1<<10]; int Utable[1<<10][10]; int Dtable[1<<10][10]; class UpdownNumbers { public: int count(int D, int S) { ZERO(Utable); ZERO(Dtable); int m1,m2; int mask,i,j; FOR(mask,1<<10) { FOR(i,10) { for(j=i;j<10;j++) if(mask&(1<<j)) break; if(j==10) Utable[mask][i]=mask^(1<<i); else Utable[mask][i]=mask^(1<<j)^(1<<i); for(j=i;j>=0;j--) if(mask&(1<<j)) break; if(j==-1) Dtable[mask][i]=mask^(1<<i); else Dtable[mask][i]=mask^(1<<j)^(1<<i); } } ZERO(from); from[0][0]=1; int first=1; while(D--) { ZERO(to); FOR(m1,1<<10) FOR(m2,1<<10) if(from[m1][m2]) { FOR(i,10) { if(first&&i==0) continue; (to[Utable[m1][i]][Dtable[m2][i]]+=from[m1][m2])%=mo; } } first=0; swap(from,to); } ll ret=0; FOR(m1,1<<10) FOR(m2,1<<10) if(from[m1][m2]) { if(__builtin_popcount(m1)>=S&&__builtin_popcount(m2)>=S) ret+=from[m1][m2]; } } return ret%mo; } }
まとめ
方針はすぐたってもコード量がちょっと膨らんで面倒だった。