九度OJ 1491 求1和2的個數 組合數學

題目連結

對數位dp，不太熟，組合的方法可能更好想，實現把所有的情況都考慮清楚。

例如算1的個數的時候。

假如第一位為n > 1，第一位可能為0-n-1，後面len-1位中1的和有（sum = (len-1)*10^(len-2))(列舉每一位是1,其他位置有10種可能);

這樣還要注意第一位是1,這樣有10^(len-1)個1;

第一位是n,繼續遞迴下去。 

假如第一位為0，直接遞迴下去。

假如第一位為1情況，為sum + (後邊數字+1(有0))+dfs(str+1);

二的情況與一類似，認真分析各種情況。

1 #include 2 #include 3 #include 4 #include 

5using
namespace
std;
6#define mod 20123
7int o[201];8
int judge(char *str)917
return
mod;18}
19int dfs(char *str)
2030     sum = (len-1)*o[len-2
];31
if(str[0] == '0'
)32return dfs(str+1)%mod;
33else
if(str[0] == '1'
)34return (sum + judge(str+1)+1 + dfs(str+1))%mod;
35else
if(str[0] > '1'
)36return ((str[0]-'
0')*sum + o[len-1] + dfs(str+1))%mod;
37return0;
38}39int dfs2(char *str)
4050     sum = (len-1)*o[len-2
];51
if(str[0] == '0'
)52return dfs2(str+1)%mod;
53else
if(str[0] == '1'
)54return (sum + dfs2(str+1))%mod;
55else
if(str[0] == '2'
)56return (2*sum + judge(str+1)+1 + dfs2(str+1))%mod;
57else
if(str[0] > '2'
)58return ((str[0]-'
0')*sum + o[len-1] + dfs2(str+1))%mod;
59return0;
60}61int
main()
62