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

2022-04-10 12:46:46 字數 1381 閱讀 6441

題目連結

對數位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