【省选模拟】这道题（数位DP）（容斥）（组合数学）

• 神仙题
• 枚举每一个的下界容斥，对种情况算方案数，令最后的数位，当前的下界加起来+1 为，那么贡献就是，所以
  我们对每一个求出，然后用范德蒙恒等式：
  
  所以我们只需要算，考虑把用范德蒙恒等式拆成每一位的贡献，就是，这样就可以按每一位的贡献统计，然后就是按套路算的方案数，需要钦定当前位原来的，那么我们每一位预处理预处理一个前后缀和就可以。
  预处理复杂度，询问复杂度

#include<bits/stdc++.h>
#define cs const
using namespace std;
cs int Mod = 1e9 + 7;
int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b; }
int mul(int a, int b){ return 1ll * a * b % Mod; }
int dec(int a, int b){ return a - b < 0 ? a - b + Mod : a - b; }
void Add(int &a, int b){ a = add(a, b); }
void Mul(int &a, int b){ a = mul(a, b); }
void Dec(int &a, int b){ a = dec(a, b); }
cs int N = 550, M = 15;
int n, D, inv[M], C[N][N][M], pre[N][N][M], suf[N][N][M], good[N];
struct atom{
vector<int> G;
atom(){ G.clear(); }
void input(){
static char S[N*10]; scanf("%s",S); int len=strlen(S);
for(int i=len-1; ~i; i--) G.push_back(S[i]-'0');
}
int operator % (cs int &b){ int as = 0; for(int i=(int)G.size()-1;~i;i--) as=(as*10+G[i])%b; return as; }
void operator /= (cs int &b){
for(int i=(int)G.size()-1,x=0;~i;i--){
int now=x*10+G[i]; x=now%b; G[i]=now/b;
} while(G.size()&&G.back()==0) G.pop_back();
}
bool iszero(){ return G.empty(); }
};
struct num{
vector<int>G;
num(){ G.clear(); }
void reset(){ G.clear(); }
void input(){
atom T; T.input();
while(!T.iszero()) G.push_back(T%D), T/=D;
}
void minus(){
--G[0];
for(int i=0; i<(int)G.size()-1; i++){
if(G[i]<0) G[i]+=D,--G[i+1];
} if(!G.back()) G.pop_back();
}
void inc(){
++G[0]; G.push_back(0);
for(int i=0; i<(int)G.size(); i++){
if(G[i]>=D) G[i]-=D,++G[i+1];
} if(!G.back()) G.pop_back();
}
num operator + (cs num &A) cs{
num B; int deg=max(A.G.size(),G.size()); B.G.resize(deg);
for(int i=0; i<deg; i++) B.G[i]=((int)G.size()>i?G[i]:0)+((int)A.G.size()>i?A.G[i]:0);
B.G.push_back(0); for(int i=0; i<deg; i++) if(B.G[i]>=D) B.G[i]-=D, ++B.G[i+1];
if(!B.G.back()) B.G.pop_back(); return B;
}
int fnd(int x){ return (int)G.size()>=x?G[x-1]:0; }
int len(){ return G.size(); }
int val(){ int as=0; for(int i=G.size()-1;~i;i--)as=add(mul(as,D),G[i]); return as; }
};
num L[M], R[M];
num dnw;
int work(){
static int dp[2][M],nxt[2][M],coef[N];
memset(coef,0,sizeof(coef));
memset(nxt,0,sizeof(nxt));
nxt[1][0]=1;
for(int i=1; i<=510; i++){
memcpy(dp,nxt,sizeof(dp));
memset(nxt,0,sizeof(nxt));
for(int x=0; x<n; x++) if(dp[0][x]||dp[1][x]){
int trs=add(dp[0][x],dp[1][x]);
int now=dnw.fnd(i);
for(int y=0; x+y<n; y++){
if(now>0) Add(nxt[0][x+y],mul(trs,pre[i][now-1][y]));
if(now+1<D){
Add(nxt[1][x+y],mul(trs,suf[i][now+1][y]));
if(i>=dnw.len()) Add(coef[x+y],mul(trs,suf[i][now+1][y]));
}
Add(nxt[0][x+y],mul(dp[0][x],C[i][now][y]));
Add(nxt[1][x+y],mul(dp[1][x],C[i][now][y]));
if(i==dnw.len()) Add(coef[x+y],mul(dp[1][x],C[i][now][y]));
}
}
}
int v=dec(0,dnw.val()), as=0;
for(int x=0,c=1; x<n; x++){
if(x) c=mul(c,mul(dec(v,x-1),inv[x]));
Add(as,mul(c,coef[n-1-x]));
} return as;
}
int main(){
scanf("%d%d",&n,&D);
for(int i=0; i<D; i++) scanf("%d",&good[i]);
inv[0]=inv[1]=1;
for(int i=2; i<=n; i++) inv[i]=mul(Mod-Mod/i,inv[Mod%i]);
for(int i=0; i<n; i++) L[i].input(),R[i].input(),L[i].minus();
for(int i=1,coe=1; i<=510; i++,Mul(coe,D)){
for(int d=0; d<D; d++) if(good[d]){
C[i][d][0]=1;
for(int j=1; j<n; j++)
C[i][d][j]=mul(mul(C[i][d][j-1],dec(mul(coe,d),j-1)),inv[j]);
}
for(int d=0; d<D; d++) for(int j=0; j<n; j++)
pre[i][d][j]=add(d?pre[i][d-1][j]:0, C[i][d][j]);
for(int d=D-1; d>=0; d--) for(int j=0; j<n; j++)
suf[i][d][j]=add(d==D-1?0:suf[i][d+1][j], C[i][d][j]);
}
int ans = 0;
for(int S=0; S<(1<<n); S++){
dnw.reset(); int t=0;
for(int i=0; i<n; i++)
if(S>>i&1) ++t,dnw=dnw+R[i];
else dnw=dnw+L[i];
dnw.inc();
if(t&1) Dec(ans,work());
else Add(ans,work());
} cout<<ans; return 0;
}