Liveddd's Blog

愛にできることはまだあるかい

LOJ#3730. 「SNOI2022」数位

发表于 更新于 分类于
本文字数： 4.9k 阅读时长 ≈ 11 分钟

非常不错的一道容斥 + 斯特林数 + 数位 DP。

考虑对于每个 $S=\sum_i a_i$ 求方案数。 因为有 $L\le a_i\le R$ 的限制，我们考虑经典容斥。设若只存在限制 $a_i\ge L$，那么方案数通过隔板法容易得到为 $\binom{S-k(L-1)-1}{k-1}$。于是容斥，设至少有 $x$ 个 $a_i$ 满足 $a_i>R$，再利用二项式反演得到：

观察到 $L,R$ 均为大整数，并且 $S$ 需满足数位单调不增，容易考虑数位 DP。但是在 DP 时不断添加下一位的过程中，组合数是不好处理的，考虑如下转化：

设 $x=S-k(L-1)-i(R-L+1)-1$，那么要求 $\binom{x}{k-1}$。$x$ 很大，在组合数上不好处理，我们尝试将限制转为 $k$。通过第一类斯特林数，我们可以将下降幂转为普通幂 $\displaystyle x^{\underline n}=\sum_{i=0}^n (-1)^{n-i} {n\brack i} x^i$，也就是有 $\displaystyle \binom{x}{n}=\frac{x^{\underline {n}}}{n!}=\frac{1}{n!}\sum_{i=0}^n (-1)^{n-i} {n\brack i} x^i$。普通幂之间的转移可以通过二项式定理得到（也就是指数生成函数之间进行卷积），问题转化为对于每个 $i\in[0,k-1]$ 求出 $x^i$ 即可。

但是此时 $S$ 没有上界，我们钦定一个上界满足所有 $(k-i)L+i(R+1)$ 均小于该上界。只需要钦定 $\operatorname{maxlen}=|R|+3$ 即可。

考虑 DP，依旧不断添加下一位的过程。过程中考虑卡满下届：若未卡满下界，则可以随便填；否则考虑下一位。具体地，考虑处理出 $f(i,j)$ 表示不考虑下界，当前已填 $i$ 位，当前位值为 $j$ 的 $S^x$。再从高到低填每一位，每次去除下界的答案。最终使用使用斯特林数再容斥求出答案即可。时间复杂度为 $\mathcal O(|R|mn^2)$，用 FFT 卷积并且使用 $\mathcal O(n\log n)$ 求第一类斯特林数可以做到 $\mathcal O(|R|mn\log n)$。

小丑小丑小丑小丑小丑小丑小丑。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;
const int N=1e3+10,K=50+10,mod=998244353;
struct BigInt
{
    vector<int>a;
    BigInt(){}
    BigInt(int s){while(s)a.push_back(s%10),s/=10;}
    int& operator[](const int &x){return a[x];}
    int len(){return a.size();}
    void get()
    {
        char ch=getchar();
        while(ch<'0'||ch>'9')ch=getchar();
        while(ch>='0'&&ch<='9')a.push_back(ch^48),ch=getchar();
        reverse(a.begin(),a.end());
    }
}L,R;
inline BigInt operator+(BigInt a,BigInt b)
{
    int si=max(a.len(),b.len()),s=0;
    BigInt res;
    a.a.resize(si,0),b.a.resize(si,0);
    for(int i=0;i<si;i++)res.a.push_back(a[i]+b[i]+s),s=res[i]>=10,res[i]%=10;
    if(s)res.a.push_back(s);
    return res;
};
inline BigInt operator*(BigInt a,int b)
{
    if(!b)return BigInt();
    int si=a.len(),s=0;
    BigInt res;
    a.a.resize(si,0);
    for(int i=0;i<si;i++)res.a.push_back(a[i]*b+s),s=res[i]/10,res[i]%=10;
    while(s)res.a.push_back(s%10),s/=10;
    return res;
};

int n,maxlen;
int pw[N];
int fac,C[N][N],S[K<<1][K<<1];
inline void adj(int &x){x+=x>>31&mod;}
inline int qpow(int x,int k=mod-2)
{
    int res=1;
    while(k)
    {
        if(k&1)res=1ll*res*x%mod;
        x=1ll*x*x%mod;
        k>>=1;
    }
    return res;
}
struct poly
{
    int a[K];
    poly(){memset(a,0,sizeof(a));}
    poly(int v){a[0]=1;for(int i=1;i<n;i++)a[i]=1ll*a[i-1]*v%mod;}
    int& operator[](const int &x){return a[x];}
    poly operator*(poly b)const
    {
        poly res;
        for(int i=0;i<n;i++)
            for(int j=0;j<n-i;j++)
                adj(res[i+j]+=1ll*a[i]*b[j]%mod*C[i+j][i]%mod-mod);
        return res;
    }
    void operator+=(poly b){for(int i=0;i<n;i++)adj(a[i]+=b[i]-mod);}
}f[N][10];
inline int sovle(BigInt s)
{
    poly res;
    int sum=0,len=s.len();
    for(int i=len-1;~i;i--)sum=(10ll*sum+s[i])%mod;
    for(int i=len+1;i<=maxlen;i++)
        for(int j=1;j<10;j++)
            res+=f[i][j]*poly(mod-sum);
    for(int i=len-1,pre=9;~i;i--)
    {
        for(int j=s[i]+1;j<=pre;j++)res+=f[i+1][j]*poly(mod-sum);
        if(s[i]>pre)break;
        adj(sum-=1ll*pw[i]*s[i]%mod);
        pre=s[i];
        if(!i)res+=poly(0);
    }
    res=res*poly(n-1);
    int ans=0;
    for(int i=0;i<n;i++)
        adj(ans+=1ll*((n-1-i)&1?mod-res[i]:res[i])*S[n-1][i]%mod-mod);
    return 1ll*ans*fac%mod;
}

int main()
{
    L.get(),R.get();
    scanf("%d",&n);
    maxlen=R.len()+3;
    for(int i=C[0][0]=1;i<=N-10;i++)
        for(int j=C[i][0]=1;j<=i;j++)
            adj(C[i][j]=C[i-1][j-1]+C[i-1][j]-mod);
    for(int i=S[0][0]=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            adj(S[i][j]=S[i-1][j-1]+1ll*S[i-1][j]*(i-1)%mod-mod);
    for(int i=fac=1;i<n;i++)fac=1ll*fac*i%mod;
    fac=qpow(fac);
    for(int i=pw[0]=1;i<=maxlen;i++)pw[i]=10ll*pw[i-1]%mod;
    for(int i=0;i<=9;i++)f[1][i]=poly(i);
    for(int i=1;i<maxlen;i++)
        for(int j=0;j<10;j++)
            for(int k=j;k<10;k++)
                f[i+1][k]+=f[i][j]*poly(1ll*pw[i]*k%mod);
    int ans=0;
    for(int i=0;i<=n;i++)
    {
        int res=1ll*sovle(L*(n-i)+(R+1)*i)*C[n][i]%mod;
        adj(ans+=(i&1?-res:res-mod));
    }
    printf("%d\n",ans); 
    return 0;
}