gzz讲过，可我到今天还是不会

有点trick的数位DP

比较显然的思路是，考虑所有数中排序后每一位的贡献。cnt(i,x)表示S(1)~S(x)第i位是x的数的个数

设这个数大于x的出现j次，等于x的出现k次，充分必要条件是，j<i&&j+k>=i

所以f[i][j][k][x][0/1]前i位，j个>x，k个=x，有无限制

O(n^3*10^2)GG

 

讨厌的是，要记录j和k

恰好——>至少

dlt(i,x)第i位>=x的个数

充分必要条件是，>=x的出现>=i次

所以f[i][j][x][0/1]

O(n^2*10^2)

DP起来非常愉悦没有细节~

#include
     
      #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')#define pb push_back#define solid const auto &#define enter cout<
      
       using namespace std;typedef long long ll;template
       
        il void rd(T &x){    char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);}template
        
         il void output(T x){
   if(x/10)output(x/10);putchar(x%10+'0');}template
         
          il void ot(T x){
   if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
          
           il void prt(T a[],int st,int nd){ for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Modulo{const int mod=1e9+7;il int ad(int x,int y){ return x+y>=mod?x+y-mod:x+y;}il int sub(int x,int y){ return ad(x,mod-y);}il int mul(int x,int y){ return (ll)x*y%mod;}il void inc(int &x,int y){x=ad(x,y);}il void inc2(int &x,int y){x=mul(x,y);}il int qm(int x,int y=mod-2){ int ret=1;while(y){ if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;}template
           
            il int ad(const int a,const int b,const Args &...args) { return ad(ad(a,b),args...);}template
            
             il int mul(const int a,const int b,const Args &...args) { return mul(mul(a,b),args...);}}using namespace Modulo;namespace Miracle{const int N=707;char a[N];int f[N][N][11][2];int n;int mi[N];void dp(){ for(reg i=1;i<=9;++i) f[n+1][0][i][1]=1; for(reg i=n;i>=1;--i){ int c=(a[i]-'0'); for(reg j=0;j<=n-i;++j){ for(reg x=1;x<=9;++x){ int v1=f[i+1][j][x][1],v0=f[i+1][j][x][0]; if(v1){ for(reg p=0;p
             
              =x)][x][0],v1); } inc(f[i][j+(c>=x)][x][1],v1); } if(v0){ for(reg p=0;p<=9;++p){ inc(f[i][j+(p>=x)][x][0],v0); } } } } }}int dlt[N][11];int main(){ scanf("%s",a+1); n=strlen(a+1); reverse(a+1,a+n+1); dp(); mi[0]=1; for(reg i=1;i<=n;++i) mi[i]=mul(mi[i-1],10); int ans=0; for(reg i=1;i<=n;++i){ for(reg x=1;x<=9;++x){ for(reg j=i;j<=n;++j){ inc(dlt[i][x],ad(f[1][j][x][1],f[1][j][x][0])); } } } for(reg i=1;i<=n;++i){ for(reg x=1;x<=9;++x){ int tmp=sub(dlt[i][x],dlt[i][x+1]); inc(ans,mul(tmp,x,mi[i-1])); } } printf("%d",ans); return 0;}}signed main(){ Miracle::main(); return 0;}/* Author: *Miracle**/
             
            
           
          
         
        
       
      
     

恰好——>至少，再差分

往往可以少记录很多东西，或者少转移很多东西！

前提是最后可以差分计算恰好的答案。