fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int m=1e9+7;
  4. #define ll long long
  5. ll p(ll a,ll b=m-2){
  6. 	ll r=1;
  7. 	while(b){
  8. 		if(b&1)r=r*a%m;
  9. 		a=a*a%m;
  10. 		b>>=1;
  11. 	}
  12. 	return r;
  13. }
  14. ll C(ll n,int k,vector<ll>&invf){
  15. 	if(n<k)return 0;
  16. 	ll r=1;
  17. 	for(int i=1;i<=k;i++){
  18. 		ll t=(n-k+i)%m;
  19. 		if(t<0)t+=m;
  20. 		r=r*t%m;
  21. 	}
  22. 	return r*invf[k]%m;
  23. }
  24. int main(){
  25. 	ios::sync_with_stdio(0);
  26. 	cin.tie(0);
  27. 	int n;
  28. 	ll k;
  29. 	cin>>n>>k;
  30. 	vector<ll>a(n);
  31. 	for(int i=0;i<n;i++)cin>>a[i];
  32. 	vector<ll>f(n+1,1),invf(n+1,1);
  33. 	for(int i=1;i<=n;i++)f[i]=f[i-1]*i%m;
  34. 	invf[n]=p(f[n]);
  35. 	for(int i=n;i>=1;i--)invf[i-1]=invf[i]*i%m;
  36.  
  37. 	ll res=0;
  38. 	long long ans = 1;
  39. 	for(int s = 9; s <= k; s+= 9){
  40. 	for(int mask=0;mask<(1<<n);mask++){
  41. 		ll sum=0;
  42. 		int b=__builtin_popcount(mask);
  43. 		for(int i=0;i<n;i++)if(mask&(1<<i)){
  44. 			sum+=a[i]+1;
  45. 			if(sum>s+n)break;
  46. 		}
  47. 		ll r=s-sum;
  48. 		if(r<0)continue;
  49. 		ll w=C(r+n-1,n - 1,invf);
  50. 		if(b&1)res=(res-w)%m;
  51. 		else res=(res+w)%m;
  52. 	}
  53. 	if(res<0)res+=m;
  54. 	ans = (ans + res) % m;
  55. 	}
  56. 	cout << ans;
  57. 	return 0;
  58. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
2 10
10 10
stdout
copy 
11
https://ideone.com/K3tG55
language:
C++14 (gcc 8.3)
created:
5 days 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!