Variety of Digits

[Link](F - Variety of Digits (atcoder.jp))

meaning of the title

Give you a number n n n. And m m m single digits, ask 1 1 1 to n n This is contained in the middle digit of n m m Number of m numbers s u m sum How much is sum.

thinking

Consider digit d p dp dp, enumerate each bit from front to back, classify, discuss and transfer the legal filling method of each bit, and then divide the set without repetition and omission to calculate the contribution.

Assume the current number is a b c d e abcde abcde, when we enumerate to the third place, we divide the current set into:

1. Prefix belongs to [ 1 , a b − 1 ] [1,ab-1] [1,ab − 1] so the third digit can be filled in [ 0 , 9 ] [0,9] [0,9] because the prefix is less than a b ab ab so filling anything in the third place will not lead to more than a b c d e abcde abcde
2. Prefix belongs to 0 0 0, so the third digit can fill in [ 1 , 9 ] [1,9] [1,9] because the prefix is 0 0 0 less than a b ab ab, you can fill in the third, but 0 0 0 is meaningless, so you can only fill it in [ 1 , 9 ] [1,9] [1,9]
3. Prefix belongs to a b ab ab is the number, then the third digit can be filled in [ 0 , c − 1 ] [0,c-1] [0,c − 1], because it needs to be within the range, so fill in [ 0 , c − 1 ] [0,c-1] [0,c − 1] are legal. Why not c c What about c? Because we fill in c c c this situation will be recorded by us with a prefix. (in this way, I can choose my status at will when I transfer next time)

Here we use state compression to record this m m The number of m is assumed to be the third i i i, i need to know before i − 1 i-1 The sum of different states of i − 1 bit. If it is transferred, enumerate what to fill in the current bit, because there is one more bit i − 1 i-1 Sum of i − 1 digit × 10 \times 10 × 10. It is found that we do not know how many different schemes can be received after the number filled in by this person, so we have to maintain a front i − 1 i-1 i − 1 number of different schemes.

The status is expressed as: f c [ i ] [ j ] : fill Yes front i position And shape state by j of square case number ， f s [ i ] [ j ] : fill Yes front i position And shape state by j of place have square case of total and fc[i][j]: the number of schemes with the first I digit and status of j, fs[i][j]: the sum of all schemes with the first I digit and status of j fc[i][j]: the number of schemes with the first I digit and status of j, fs[i][j]: the sum of all schemes with the first I digit and status of j

State transition: for each bit, the transition can be divided according to the set.

Finally, we should judge whether the prefix (original number) is legal.

Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
#include <queue>
#include <vector>
#include <map>
#include <bitset>
#include <unordered_map>
#include <cmath> 
#include <stack>
#include <iomanip>
#include <deque> 
#include <sstream>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 1e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 998244353;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
#define tpyeinput int
inline char nc() {static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
inline void read(tpyeinput &sum) {char ch=nc();sum=0;while(!(ch>='0'&&ch<='9')) ch=nc();while(ch>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+(ch-48),ch=nc();}
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
    e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
int a[N];
LL fc[N][(1 << 10) + 1], fs[N][(1 << 10) + 1];
// fc[i][j]: the number of schemes with the first I digits and the status of j
// fs[i][j]: the sum of the first I numbers with the status of j
// Digital DP - > classification discussion: for each bit, the number of guaranteed contributions is within the range, focusing on the contribution to the state
// Xxxxxxxxx is divided into three categories
//1. If xxxxx is non-zero and less than the original number, the ith bit can take [0,9] arbitrarily
//2. If XXXX is zero, the i-th bit can take [1,9]  
//3. If XXXX is the original number, the i-th bit can obtain [0, a - 1]
// Finally, calculate whether the original number is consistent
// Transfer from the front
// Become a continuous problem and take it directly 
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    string str; cin >> str;
    int n = str.size();
    for (int i = 0; i < n; i ++) a[i] = str[i] - '0';
    
    cin >> m;
    int mask = 0;
    for (int i = 0; i < m; i ++) {
        int x; cin >> x;
        mask |= 1 << x;
    }

    int last = a[0], prebit = 1 << a[0];
    // Equivalent to the prefix and all 0, so it can only be transferred from [1, a[i])
    for (int i = 1; i < a[0]; i ++) {
        (fc[0][1 << i] += 1) % mod;
        (fs[0][1 << i] += i) % mod;
    }

    for (int i = 1; i < n; i ++) {
        // Ensure that this one can be selected at will during the transfer
        for (int j = 1; j < (1 << 10); j ++) 
            for (int x = 0; x < 10; x ++) {
                fc[i][j | (1 << x)] = (fc[i][j | (1 << x)] + fc[i - 1][j] + mod) % mod;
                fs[i][j | (1 << x)] = (fs[i][j | (1 << x)] + fs[i - 1][j] * 10 + fc[i - 1][j] * x + mod) % mod;
            }

        for (int x = 1; x < 10; x ++) {
            fc[i][1 << x] = (fc[i][1 << x] + 1 + mod) % mod;
            fs[i][1 << x] = (fs[i][1 << x] + x + mod) % mod;
        }
        
        // If this bit is filled in a[i], the existing states of f[i - 1][j] will exist, and abcd cannot be transferred directly, which is equivalent to a classification discussion
        for (int x = 0; x < a[i]; x ++) {
            fc[i][prebit | (1 << x)] = (fc[i][prebit | (1 << x)] + 1 + mod) % mod;
            fs[i][prebit | (1 << x)] = (fs[i][prebit | (1 << x)] + (LL)last * 10 + x + mod) % mod;
        }
        last = ((LL)last * 10 + a[i] + mod) % mod;
        prebit = prebit | (1 << a[i]);
    }
   // cout << last << endl;
    LL res = 0;
    for (int j = 0; j < (1 << 10); j ++)
        if ((j & mask) == mask) res = (res + fs[n - 1][j]) % mod;

    if ((prebit & mask) == mask) res = (res + last) % mod;

    cout << res << endl;
    return 0;
}