1043 幸运号码数位DP-白红宇

1043 幸运号码数位DP

阅读量：4676 次

发布时间：2019-06-09

本文共 1283 字，大约阅读时间需要 4 分钟。

设dp[i][j]表示前i位数中，i位数的和为j时的所有情况。

转移的时候和普通的数位dp是一样转移的，但是如果你压缩了空间的话，就是用滚动数组的话，记录情况数就要多开一个变量来保存，

然后看看怎么排除前导0的情况。

如果产生的和值是j，然后前i - 1位产生的和值也是j，那么第i为就是前导0了。需要排除。

然后前n部分的和值的所有情况（需要排除前导0） * 后n部分的和值情况。就是答案。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define IOS ios::sync_with_stdio(false)using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #include 
                 
                  #include 
                  
                   #include 
                   
                    const int MOD = 1e9 + 7;LL dp[2][9 * 1000 + 20];void work() { int n; cin >> n; dp[0][0] = 1; int now = 0; for (int i = 1; i <= n; ++i) { now = !now; for (int k = 0; k <= 9 * i; ++k) { LL sum = 0; for (int j = 0; j <= 9; ++j) { if (k >= j) { sum += dp[!now][k - j]; if (sum >= MOD) sum %= MOD; } } dp[now][k] = sum; } } LL ans = 0; for (int i = 1; i <= 9 * n; ++i) {// assert(dp[now][i] - dp[!now][i] >= 0); ans += ((dp[now][i] - dp[!now][i] + MOD) % MOD * dp[now][i]) % MOD; if (ans >= MOD) ans %= MOD; } cout << ans << endl;}int main() {#ifdef local freopen("data.txt", "r", stdin);// freopen("data.txt", "w", stdout);#endif work(); return 0;}