fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. #define pb push_back
  5. #define mk make_pair
  6. #define ll long long
  7. #define fastio ios_base::sync_with_stdio(0); cin.tie();
  8. using namespace std;
  9. typedef pair<int, int> pii;
  10. const ll MOD=1e9+7;
  11. const int N=0;
  12.  
  13. int par[1];
  14. int find(int x){return x==par[x]?x:par[x]=find(par[x]);}
  15. void join(int x,int y){par[find(x)]=y;}
  16. ll expo(ll a,ll b,ll mod){ll ans=1; while(b){if(b&1) ans=(ans*a)%mod; a=(a*a)%mod; b>>=1;} return ans;}
  17. int gcd(int a,int b,int& x,int& y) {if(a==0){x=0;y=1;return b;}int x1, y1;int d=gcd(b%a, a, x1, y1);x=y1-(b/a)*x1;y=x1;return d;}
  18.  
  19. ll c[20][20],p[10][20];
  20. int a[10],b[10];
  21. int fix[10];
  22. int dig[20];
  23. int fix_n,dig_n;
  24.  
  25. ll ways_to_place(int places){
  26. 	ll ans=1;
  27. 	for(int i=0;i<fix_n;++i){
  28. 		if(b[fix[i]]<0){
  29. 			return 0;
  30. 		}
  31. 		ans*=c[places][b[fix[i]]];
  32. 		places-=b[fix[i]];
  33. 		if(places<0){
  34. 			return 0;
  35. 		}
  36. 	}
  37. 	ans*=p[10-fix_n][places];
  38. 	//cout<<ans<<"\n";
  39. 	return ans;
  40. }
  41.  
  42. ll calc(ll x){
  43. 	if(x==0) return 0;
  44. 	//cout << x << ", ";
  45.     for(dig_n=0;x;x/=10){
  46. 		dig[dig_n++]=x%10;
  47. 	}
  48.     //cout << dig_n << "  --  ";
  49. 	int i,j,be;
  50. 	for(i=0;i<10;++i){
  51. 		b[i]=a[i];
  52. 	}
  53. 	ll ans=0;
  54. 	for(i=0;i<dig_n-1;++i){
  55. 		for(j=1;j<10;++j){
  56. 			b[j]--;
  57. 			ans+=ways_to_place(i);
  58. 			b[j]++;
  59. 		}
  60. 	}
  61. 	for(i=dig_n-1;i>=0;--i){
  62. 		be=(i==dig_n-1 ? 1 : 0);
  63. 		for(j=be;j<dig[i];++j){
  64. 			b[j]--;
  65. 			ans+=ways_to_place(i);
  66. 			b[j]++;
  67. 		}
  68. 		b[dig[i]]--;
  69. 	}
  70. 	ans+=ways_to_place(0);
  71. 	return ans;
  72. }
  73.  
  74. ll solve(ll x){
  75. 	int i,end=(1<<10);
  76. 	ll ans=x;
  77. 	for(int mask=1;mask<end;++mask){
  78. 		fix_n=0;
  79. 		for(i=0;(1<<i)<=mask;++i){
  80. 			if(mask&(1<<i)){
  81. 				fix[fix_n++]=i;
  82. 			}
  83. 		}
  84. 		if(fix_n&1){
  85. 			ans-=calc(x);
  86. 		} else{
  87. 			ans+=calc(x);
  88. 		}
  89. 	}
  90. 	return ans;
  91. }
  92.  
  93. void init(){
  94. 	int i,j;
  95. 	for(i=0;i<20;++i){
  96. 		c[i][0]=1;
  97. 	}
  98. 	for(i=1;i<20;++i){
  99. 		for(j=1;j<=i;++j){
  100. 			c[i][j]=c[i-1][j-1]+c[i-1][j];
  101. 		}
  102. 	}
  103. 	p[0][0]=1;
  104. 	for(i=1;i<=10;++i){
  105. 		p[i][0]=1;
  106. 		for(j=1;j<20;++j){
  107. 			p[i][j]=p[i][j-1]*i;
  108. 		}
  109. 	}
  110.     //for(int i = 0; i <= 5; i++){
  111.     //    for(int j = 0; j <= 5; j++){
  112.     //        cout << p[i][j] << " ";
  113.     //    }
  114.     //    cout << endl;
  115.     //}
  116. }
  117.  
  118. int main(){
  119. 	int test,i;
  120. 	ll r,l;
  121. 	ll res;
  122. 	init();
  123. 	scanf("%d",&test);
  124. 	while(test--){
  125. 		scanf("%lld",&l);scanf("%lld",&r);
  126. 		for(i=0;i<10;++i){
  127. 			scanf("%d",&a[i]); 
  128. 		}
  129. 		res=solve(r)-solve(l-1);
  130. 		printf("%lld\n", res);
  131. 	}	
  132. 	return 0;
  133. }
Success #stdin #stdout 0s 4184KB
comments (?)
stdin
copy 
3
21 28
5 4 3 2 1 1 2 3 4 5
233 23333
2 3 3 3 3 2 3 3 3 3
1 999
2 1 2 1 1 1 1 1 1 1
stdout
copy 
6
19627
59
https://ideone.com/Zo7X18
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!