fork download
copy 
  1. /* Author haleyk10198 */
  2. /* 作者:  haleyk10198 */
  3. /* CF handle: haleyk100198*/
  4. #include <bits/stdc++.h>
  5.  
  6. #define MOD 1000000007
  7. #define LINF (1LL<<60)
  8. #define INF 2147483647
  9. #define PI 3.1415926535897932384626433
  10. #define ll long long
  11. #define pii pair<int,int>
  12. #define mp(x,y) make_pair((x),(y))
  13. #define pb(x) push_back((x))
  14.  
  15. using namespace std;
  16.  
  17. string itos(int x){
  18. 	stringstream ss;
  19. 	ss << x;
  20. 	return ss.str();
  21. }
  22.  
  23. int res, n, d[55], dp[55][55], sum[55];
  24.  
  25. int pwr(int b, int e){
  26. 	if(e == 0) return 1;
  27. 	if(e == 1) return b;
  28. 	return (1LL*pwr((1LL*b*b)%MOD, e/2)*pwr(b, e%2))%MOD;
  29. }
  30.  
  31. void upd(int &tar, int val){
  32. 	(tar += val) %= MOD;
  33. }
  34.  
  35. int help(int l, int r, int deb1, int deb2){
  36. 	if(deb1 < 0 || deb2 < 0) return 0;
  37. 	if(l > r)
  38. 		return deb1 == 0 && deb2 == 0;
  39. 	int res = 0, deb = deb1+deb2;
  40. 	vector<int> v1(4), v2(4);
  41. 	v1[0] = 1, v1[1] = deb1, v1[2] = (deb1-1)*deb1/2, v1[3] = (deb1-2)*(deb1-1)*deb1/6;
  42. 	v2[0] = 1, v2[1] = deb1, v2[2] = (deb2-1)*deb2/2, v2[3] = (deb2-2)*(deb2-1)*deb2/6;
  43. 	for(int ret = d[l]; ret >= 0; ret--){
  44. 		if(ret == d[l])
  45. 			for(int j = 0; j <= ret; j++)
  46. 				upd(res, (1LL*v1[j]*v2[ret-j]*help(l+1, r, deb1-j+(ret-j), deb2-(ret-j)))%MOD);
  47. 		else if(ret == 0)
  48. 			upd(res, help(l+1, r, deb1+(d[l] == 1), deb2+(d[l] == 2)));
  49. 		else
  50. 			upd(res, (1LL*deb1*help(l+1, r, deb1, deb2)+1LL*deb2*help(l+1, r, deb1+2, deb2-1))%MOD);			
  51. 	}
  52. 	return res;
  53. }
  54.  
  55. int dpf(int l, int r){
  56. 	if(r == n-1) return 1;
  57. 	if(r >= n) return 0;
  58. 	if(dp[l][r] != -1) return dp[l][r];
  59. 	dp[l][r] = 0;
  60. 	for(int i = 1; i <= min(n-1-r, sum[r+1]-sum[l]); i++){
  61. 		int val = help(l, r, i, 0);
  62. 		if(val)
  63. 			(dp[l][r] += (1LL*val*dpf(r+1, r+i))%MOD) %= MOD;
  64. 	}
  65. 	return dp[l][r];
  66. }
  67.  
  68. int main(){
  69. 	//freopen("input.txt","r",stdin);
  70. 	//freopen("output.txt","w",stdout);
  71. 	ios_base::sync_with_stdio(false);
  72. 	cin >> n;
  73. 	for(int i = 0; i < 55; i++) for(int j = 0; j < 55; j++) dp[i][j]--;
  74. 	for(int i = 0; i < n; i++)
  75. 		cin >> d[i];
  76. 	for(int i = 1; i < n; i++) d[i]--;
  77. 	for(int i = 1; i <= n; i++)	sum[i] = sum[i-1]+d[i-1];
  78. 	cout << dpf(0, 0) << endl;
  79. 	return 0;
  80. }
  81.  
Success #stdin #stdout 0s 16080KB
comments (?)
stdin
copy 
20
2 2 2 2 3 2 3 2 2 2 2 2 2 2 2 2 2 3 3 2
stdout
copy 
41472
https://ideone.com/kOBovo
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!