uva-12063-Zeros and Ones

出處 ： https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3215

解題策略

DP，a[len][one][mod]，len數字長度，one數字1的個數，mod餘數，a[1][1][1%k]=1，數字長度至少為1，至少一個1(開頭不能是0)，餘數是1，有一個。末尾補0，a[len+1][one][(mod<<1)%k]+=a[len][one][mod]；末尾補1，a[len+1][one+1][((mod<<1)|1)%k]+=a[len][one][mod]。n為奇數或k等於0，結果為0。