CF908G New Year and Original Order 數位DP

傳送門

---

看到數據范圍到\(10^{700}\)毫無疑問數位DP。那么我們最重要的問題是如何有效地維護所有數位排序之后的數的值。

對于某一個數\(x\)，設\(f_{x,i} (i \in [1,9])\)表示\(x\)中的所有數位的值\(\geq i\)的數位數量，比如說\(f_{6345982 , 7} = 2 , f_{1982777 , 7} = 5\)。那么\(x = \sum\limits_{i=1}^9 \sum\limits_{j=0}^{f_{x,i} - 1} 10^i = \frac{\sum\limits_{i=1}^9 10^{f_{x,i}} - 1}{9}\)。

經過這一個轉化，我們需要維護的就是\(f_{x,i}\)。而\(f_{x,i}\)在數位DP的時候很好動態地維護。

具體來說，數位DP時記錄當前填入部分的\(f_{x,i}\)，預處理\(dp_{i,j}\)表示對于位數恰好等于\(i-1\)（可以有前導\(0\)）的所有數\(p\)的\(10^{f_{p,j}}\)之和，然后就可以直接算了。

#include<bits/stdc++.h>
using namespace std;const int MOD = 1e9 + 7;
string s;
int dp[707][10] , cur[10] , L , ans , inv9;inline int poww(long long a , int b){int times = 1;while(b){if(b & 1) times = times * a % MOD;a = a * a % MOD;b >>= 1;}return times;
}void init(){for(int i = 1 ; i < 10 ; ++i)dp[0][i] = (10 - i) * 10 + i;for(int i = 1 ; i < L ; ++i)for(int j = 1 ; j < 10 ; ++j)dp[i][j] = dp[i - 1][j] * ((10ll - j) * 10 + j) % MOD;
}void calc(int l){int sum = (MOD - 9ll * poww(10 , l + 1) % MOD) % MOD;for(int i = 1 ; i < 10 ; ++i)sum = (sum + 1ll * (l == -1 ? 1 : dp[l][i]) * poww(10 , cur[i])) % MOD;ans = (ans + 1ll * sum * inv9) % MOD;
}void dfs(int l){if(l < 0){int sum = 0;for(int i = 1 ; i < 10 ; ++i)sum = (sum + poww(10 , cur[i]) - 1) % MOD;ans = (ans + 1ll * sum * inv9) % MOD;return;}for(int i = 0 ; i <= s[l] - '0' ; ++i){++cur[i];i != s[l] - '0' ? calc(l - 1) : dfs(l - 1);}
}int main(){#ifndef ONLINE_JUDGEfreopen("in","r",stdin);//freopen("out","w",stdout);#endifinv9 = poww(9 , MOD - 2);cin >> s; L = s.size(); reverse(s.begin() , s.end());init(); dfs(L - 1);cout << ans % MOD;return 0;
}