Guest User

Untitled

a guest
Jan 11th, 2023
763
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.05 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define el "\n"
  3. using namespace std;
  4.  
  5. const int N = 4e5 + 50;
  6.  
  7. int f[5][1500][1500], M, a;
  8.  
  9. int get_P(int n) {
  10.     int a = sqrt(n);
  11.     if (a * a < n && a * a + a >= n) {
  12.         return 2 * a + 1;
  13.     }
  14.     if (a * a + a < n && n <= (a + 1) * (a + 1)) {
  15.         return 2 * (a + 1);
  16.     }
  17.     return 2 * a;
  18. }
  19.  
  20. void precalc() {
  21.     a = sqrt(N) + 5;
  22.     f[0][0][a] = 1;
  23.     for (int i = 0; i < 4; i++) {
  24.         for (int j = 0; j <= a; j++) {
  25.             for (int was = a; was >= 0; was--) {
  26.                 if (was && j + was <= a) {
  27.                     (f[i][j + was][was] += f[i][j][was]) %= M;
  28.                 }
  29.                 if (was) {
  30.                     (f[i][j][was - 1] += f[i][j][was]) %= M;
  31.                 }
  32.             }
  33.             (f[i + 1][j][a] += f[i][j][0]) %= M;
  34.         }
  35.     }
  36. }
  37.  
  38. int main() {
  39.     ios::sync_with_stdio(false);
  40.     cin.tie(NULL);
  41.  
  42.     int q, type;
  43.     cin >> q >> type;
  44.     if (type == 2) {
  45.         cin >> M;
  46.         precalc();
  47.     }
  48.     while (q--) {
  49.         int n;
  50.         cin >> n;
  51.         int p = get_P(n);
  52.         if (type == 1) {
  53.             int _n, _m;
  54.             for (int x = 1; x <= p; x++) {
  55.                 int y = p - x;
  56.                 if (x + y == p && x * y >= n) {
  57.                     _n = x; _m = y;
  58.                     break;
  59.                 }
  60.             }
  61.             vector <vector <char> > ans(_n, vector <char> (_m, '#'));
  62.             cout << _n << " " << _m << "\n";
  63.             for (int i = 0; i < _n * _m - n; i++) {
  64.                 ans[i][0] = '.';
  65.             }
  66.             for (int i = 0; i < _n; i++, cout << el) {
  67.                 for (int j = 0; j < _m; j++) {
  68.                     cout << ans[i][j];
  69.                 }
  70.             }
  71.  
  72.             continue;
  73.         }
  74.  
  75.         int ans = 0;
  76.         for (int x = 1; x <= p; x++) {
  77.             int y = p - x;
  78.             if (x + y == p && x * y >= n) {
  79.                 (ans += f[4][x * y - n][a]) %= M;
  80.             }
  81.         }
  82.         cout << p * 2 << " " << ans << "\n";
  83.     }
  84. }
  85.  
  86.  
Add Comment
Please, Sign In to add comment