Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
34475 liuziming 【S】T1 C++ 解答错误 40 334 MS 32808 KB 9939 2024-11-10 12:43:01

Tests(4/10):


#include<bits/stdc++.h> using namespace std; #define int long long #define mod 1000000007 int n,L[200010],R[200010],a,fac[300100],invfac[300100],dp[300100][20],ansl,ansr; bool who_choose_L[20],who_choose_R[20]; int qp(int a,int x){ int res=1; while(x){ if(x&1){ res=(res*a)%mod; }a=(a*a)%mod; x>>=1; }return res; }void init(){ fac[0]=1;invfac[0]=1; for(int i=1;i<=300000;i++){ fac[i]=(fac[i-1]*i)%mod; invfac[i]=qp(fac[i],mod-2)%mod; } }int C(int n,int m){//m>n; if(m<n||m<0||n<0) return 0; return (fac[m]*invfac[n]%mod)*invfac[m-n]%mod; }int A(int n,int m){//m>n; if(m<n||m<0||n<0) return 0; return (fac[m]*invfac[m-n]%mod); }signed main(){ //freopen("math.in","r",stdin); //freopen("math.out","w",stdout); cin>>n; init(); for(int i=1;i<=n;i++){ char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); L[i]=ch-'0'; //cout<<L[i]; }//cout<<'\n'; for(int i=1;i<=n;i++){ char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); R[i]=ch-'0'; //cout<<R[i]; }//cout<<'\n'; dp[0][0]=1; for(int i=1;i<=n;i++){ for(int j=1;j<=min((long long)10,i);j++){ dp[i][j]=(dp[i-1][j-1]+dp[i-1][j]*j)%mod; //cout<<dp[i][j]<<' '; }//cout<<'\n'; } cin>>a; int nowpos=n; while(1){ if(L[nowpos]!=0){ break; }nowpos--; }L[nowpos]-=1; //cout<<nowpos<<'\n'; for(int i=nowpos+1;i<=n;i++){ L[i]=9; }//cout<<L[1]<<L[2]; bool flag=0;int begin=0; for(int i=1;i<=n;i++){ if(L[i]!=0&&flag==0){flag=1;begin=i;} for(int j=0;j<=9;j++){ if(j==0){ if(i!=begin){ int front_thisone=0; for(int k=0;k<=9;k++){ if(who_choose_L[k]){ front_thisone++; } }if(who_choose_L[j]==0){ front_thisone++; } if(i==n&&j<L[i]){ if(front_thisone==a){ ansl++; }//continue; } int empty=front_thisone+n-i-1,sum=0; int Igotchoose=C(a-front_thisone,10-front_thisone); for(int nowchoose_in_last=a-front_thisone;nowchoose_in_last<=a&&i!=n;nowchoose_in_last++){ //cout<<front_thisone<<'\n'; int nums=C(nowchoose_in_last-a+front_thisone,front_thisone)*fac[nowchoose_in_last]%mod*Igotchoose%mod; //cout<<i<<' '<<j<<' '<<nowchoose_in_last<<' '<<nums*dp[n-i][nowchoose_in_last]<<'\n'; sum=(sum+nums*dp[n-i][nowchoose_in_last])%mod; //ansl=(ansl+nums*dp[n-i][nowchoose_in_last])%mod; }//cout<<i<<' '<<j<<' '<<sum<<'\n'; ansl=(ansl+sum)%mod; } }else{ int front_thisone=0; for(int k=0;k<=9;k++){ if(who_choose_L[k]){ front_thisone++; } }if(who_choose_L[j]==0){ front_thisone++; } if(i==n&&j<L[i]){ if(front_thisone==a){ ansl++; }//continue; } int empty=front_thisone+n-i-1,sum=0; int Igotchoose=C(a-front_thisone,10-front_thisone); if(j<L[i]){ for(int nowchoose_in_last=a-front_thisone;nowchoose_in_last<=a&&i!=n;nowchoose_in_last++){ //cout<<front_thisone<<'\n'; int nums=C(nowchoose_in_last-a+front_thisone,front_thisone)*fac[nowchoose_in_last]%mod*Igotchoose%mod; //cout<<i<<' '<<j<<' '<<nowchoose_in_last<<' '<<nums*dp[n-i][nowchoose_in_last]<<'\n'; sum=(sum+nums*dp[n-i][nowchoose_in_last])%mod; //ansl=(ansl+nums*dp[n-i][nowchoose_in_last])%mod; }//cout<<i<<' '<<j<<' '<<sum<<'\n'; } ansl=(ansl+sum)%mod; if(i!=begin){ sum=0; front_thisone=1; int Igotchoose=C(a-front_thisone,10-front_thisone); for(int nowchoose_in_last=a-front_thisone;nowchoose_in_last<=a;nowchoose_in_last++){ //cout<<front_thisone<<'\n'; int nums=C(nowchoose_in_last-a+front_thisone,front_thisone)*fac[nowchoose_in_last]%mod*Igotchoose%mod; //cout<<i<<' '<<j<<' '<<nowchoose_in_last<<' '<<nums*dp[n-i][nowchoose_in_last]<<'\n'; sum=(sum+nums*dp[n-i][nowchoose_in_last])%mod; //ansl=(ansl+nums*dp[n-i][nowchoose_in_last])%mod; }//cout<<i<<' '<<j<<' '<<sum<<'\n'; ansl=(ansl+sum)%mod; } } }if(flag) who_choose_L[L[i]]=1; } //cout<<begin<<'\n'; for(int i=1;i<=n;i++){ //if(L[i]!=0) flag=1; for(int j=0;j<=9;j++){ if(j==0){ if(i!=1){ int front_thisone=0; for(int k=0;k<=9;k++){ if(who_choose_R[k]){ front_thisone++; } }if(who_choose_R[j]==0){ front_thisone++; } if(i==n&&j<R[i]){ if(front_thisone==a){ ansr++; }//continue; } int empty=front_thisone+n-i-1,sum=0; int Igotchoose=C(a-front_thisone,10-front_thisone); for(int nowchoose_in_last=a-front_thisone;nowchoose_in_last<=a&&i!=n;nowchoose_in_last++){ //cout<<front_thisone<<'\n'; int nums=C(nowchoose_in_last-a+front_thisone,front_thisone)*fac[nowchoose_in_last]%mod*Igotchoose%mod; //cout<<i<<' '<<j<<' '<<nowchoose_in_last<<' '<<nums*dp[n-i][nowchoose_in_last]<<'\n'; sum=(sum+nums*dp[n-i][nowchoose_in_last])%mod; //ansl=(ansl+nums*dp[n-i][nowchoose_in_last])%mod; }//cout<<i<<' '<<j<<' '<<sum<<'\n'; ansr=(ansr+sum)%mod; } }else{ int front_thisone=0; for(int k=0;k<=9;k++){ if(who_choose_R[k]){ front_thisone++; } }if(who_choose_R[j]==0){ front_thisone++; } if(i==n&&j<R[i]){ if(front_thisone==a){ ansr++; } } int empty=front_thisone+n-i-1,sum=0; int Igotchoose=C(a-front_thisone,10-front_thisone); if(j<R[i]){ for(int nowchoose_in_last=a-front_thisone;nowchoose_in_last<=a&&i!=n;nowchoose_in_last++){ //cout<<front_thisone<<'\n'; int nums=C(nowchoose_in_last-a+front_thisone,front_thisone)*fac[nowchoose_in_last]%mod*Igotchoose%mod; //cout<<i<<' '<<j<<' '<<nowchoose_in_last<<' '<<nums*dp[n-i][nowchoose_in_last]<<'\n'; sum=(sum+nums*dp[n-i][nowchoose_in_last])%mod; //ansl=(ansl+nums*dp[n-i][nowchoose_in_last])%mod; }//cout<<i<<' '<<j<<' '<<sum<<'\n'; } ansr=(ansr+sum)%mod; if(i!=1){ sum=0; front_thisone=1; int Igotchoose=C(a-front_thisone,10-front_thisone); for(int nowchoose_in_last=a-front_thisone;nowchoose_in_last<=a;nowchoose_in_last++){ //cout<<front_thisone<<'\n'; int nums=C(nowchoose_in_last-a+front_thisone,front_thisone)*fac[nowchoose_in_last]%mod*Igotchoose%mod; //cout<<i<<' '<<j<<' '<<nowchoose_in_last<<' '<<nums*dp[n-i][nowchoose_in_last]<<'\n'; sum=(sum+nums*dp[n-i][nowchoose_in_last])%mod; //ansl=(ansl+nums*dp[n-i][nowchoose_in_last])%mod; }//cout<<i<<' '<<j<<' '<<sum<<'\n'; ansr=(ansr+sum)%mod; } } }who_choose_R[R[i]]=1; } int lcnt=0,rcnt=0; for(int i=0;i<=9;i++){ lcnt+=who_choose_L[i]; rcnt+=who_choose_R[i]; }if(lcnt==a) ansl++; if(rcnt==a) ansr++; //cout<<lcnt<<'\n'; //cout<<ansl<<' '<<ansr<<'\n'; cout<<(ansr-ansl+mod)%mod<<'\n'; } /*for(int j=0;j<L[i];j++){ if(j==0){ }else{ int front_thisone=0; for(int k=0;k<=9;k++){ if(who_choose_L[k]){ front_thisone++; } }if(who_choose_L[j]==0){ front_thisone++; } if(front_thisone+n-i<a){ continue; } } }*/


测评信息: