fork download 
  1. #include <iostream>
  2. #include <utility>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. typedef long long ll;
  9. typedef pair<int, int> pii;
  10. const int max_n = 250;
  11.  
  12. #define int ll
  13.  
  14. ll dp[max_n*2+1][max_n+1], m;
  15. int l[max_n], r[max_n<<1], n;
  16. pii a[max_n<<1];
  17.  
  18. inline void dwlr(int *src, int n, double msc)
  19. {
  20. 	for (int i = 0; i < n; i++)
  21. 		src[i] = int(sqrt(n * n - i * i) - msc);
  22. }
  23.  
  24. int solve(int k)
  25. {
  26. 	memset(dp, 0, sizeof dp);
  27. 	int lc = 0, rc = 0;
  28.  
  29. 	dp[0][0] = 1;
  30. 	for (int i = 0; i < (n << 1); i++)
  31. 	{
  32. 		if (a[i].second >= n)
  33. 		{
  34. 			for (int j = 0; j <= lc; j++)
  35. 				dp[i+1][j] = (dp[i+1][j] + dp[i][j] * (a[i].first - rc - j + 1)) % m;
  36. 			rc++;
  37. 		}
  38. 		else
  39. 		{
  40. 			for (int j = 0; j <= lc && j <= k; j++)
  41. 				dp[i+1][j] = (dp[i+1][j] + dp[i][j] * (r[a[i].second] - lc - k - n + j + 1)) % m;
  42. 			for (int j = 0; j < k && j <= lc; j++)
  43. 				dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j] * (a[i].first - rc - j + 1)) % m;
  44. 			lc++;
  45. 		}
  46. 	}
  47.  
  48. 	return dp[n<<1][k];
  49. }
  50.  
  51. signed main()
  52. {
  53. 	ios_base::sync_with_stdio(false);
  54. 	cin.tie(0);
  55.  
  56. 	cin >> n >> m;
  57. 	dwlr(l, n, 1e-7), dwlr(r, n << 1, 0), r[0] = 2 * n - 1;
  58.  
  59. 	for (int i = 0; i < n; i++)
  60. 	{
  61. 		a[i].first = l[i], a[i].second = i;
  62. 		a[i+n].first = r[i+n], a[i+n].second = i + n;
  63. 	}
  64. 	sort(a, a + (n << 1), [](pii& a, pii& b) { return (a.first != b.first)? (a.first < b.first):(a.second > b.second); });
  65.  
  66. 	int ans = 0;
  67. 	for (int i = 0; i <= n; i++)
  68. 		ans = (ans + solve(i) * ((i & 1)? -1:1)) % m;
  69. 	cout << (ans + m) % m << endl;
  70.  
  71. 	return 0;
  72. }
Success #stdin #stdout 0.01s 5484KB
comments (?)
stdin 
2 998244353
stdout 
4
https://ideone.com/hSueQo
language:
C++14 (gcc 8.3)
created:
2 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!