Advertisement
welleyth

Day4. A (N^2logK)

Jul 2nd, 2022
833
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 10.42 KB | None
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace __gnu_pbds;
  5. using namespace std;
  6.  
  7. #define int long long
  8. #define mp make_pair
  9. #define pb push_back
  10.  
  11. #pragma GCC optimize("Ofast")
  12. #pragma GCC optimize("unroll-loops")
  13. //#pragma GCC target("avx2")
  14.  
  15. constexpr long long INF = (long long)4e9;
  16. constexpr int N = (int)5e5 + 111;
  17. constexpr int md = (int)1e9 + 7;
  18. constexpr int mdPower = (int)1e9+7 - 1;
  19. constexpr int P = (int)998244343;
  20.  
  21. //typedef __int128 _uint;
  22. typedef long long ll;
  23.  
  24. mt19937_64 rnd(time(nullptr));
  25.  
  26. void add(int& a,int b){
  27.     a += b; if(a >= md) a -= md;
  28. }
  29. void sub(int& a,int b){
  30.     a -= b; while(a < 0) a += md;
  31. }
  32.  
  33. int bpow(int a,int b){
  34.     if(b == 0)
  35.         return 1;
  36.     if(b % 2 == 0){
  37.         int t = bpow(a,b>>1);
  38.         return 1ll*t*t%md;
  39.     }
  40.     return 1ll * a*bpow(a,b-1) % md;
  41. }
  42.  
  43. int inv(int a){
  44.     return bpow(a,md-2);
  45. }
  46.  
  47. //int fac[N],invfac[N];
  48. //
  49. //void init(){
  50. //    fac[0] = 1;
  51. //    for(int i = 1; i < N; i++){
  52. //        fac[i] = (fac[i-1] * i) % md;
  53. //    }
  54. //    invfac[N-1] = inv(fac[N-1]);
  55. //    for(int i = N-2; i >= 0; i--){
  56. //        invfac[i] = (invfac[i+1] * (i+1))%md;
  57. //    }
  58. //    return;
  59. //}
  60. //
  61. //int C(int n,int k){
  62. //    if(k > n)
  63. //        return 0;
  64. //    return fac[n] * invfac[k] % md * invfac[n-k] % md;
  65. //}
  66. //
  67. //int A(int n,int k){
  68. //    if(k > n)
  69. //        return 0;
  70. //    return fac[n] * invfac[n-k] % md;
  71. //}
  72.  
  73. struct DSU{ /// currently there is dsu on array
  74.     vector<int> parent;
  75.     vector<int> sz;
  76.     vector<int> deep;
  77.     DSU(){}
  78.     DSU(int n){
  79.         n = n+10;
  80.         parent.resize(n);
  81.         sz.resize(n);
  82.         deep.resize(n);
  83.         for(int i = 0; i < n; i++)
  84.             parent[i] = i, sz[i] = 1,deep[i] = 0;
  85.     }
  86.     int get(int x){
  87.         return parent[x] == x ? x : parent[x] = get(parent[x]);
  88.     }
  89.     void union_sets(int a,int b){
  90.         a = get(a), b = get(b);
  91.         if(a == b)
  92.             return;
  93. //        #warning DSU is written badly
  94.         if(deep[b] > deep[a])
  95.             swap(a,b);
  96.         parent[a] = b;
  97.         deep[b] = max(deep[b],deep[a]+1);
  98.         sz[b] += sz[a];
  99.         return;
  100.     }
  101.     bool connected(int a,int b){
  102.         return get(a) == get(b);
  103.     }
  104. };
  105.  
  106. vector<vector<int>> subMatrix(int x1,int y1,int x2,int y2,vector<vector<int>>& gr){
  107.     vector<vector<int>> ans;
  108.     if(y1 > y2)
  109.         swap(y1,y2);
  110.     if(x1 > x2)
  111.         swap(x1,x2);
  112.     for(int i = x1; i <= x2; i++){
  113.         ans.pb(vector<int>());
  114.         for(int j = y1; j <= y2; j++){
  115.             ans.back().pb(gr[i][j]);
  116.         }
  117.     }
  118.     return ans;
  119. }
  120.  
  121. bool ok(vector<vector<int>> gr){
  122.     int n = gr.size();
  123. //    cerr << "n = " << n << "\n";
  124. //    for(auto& x : gr){
  125. //        for(auto& y : x)
  126. //            cout << y << " ";
  127. //        cout << "\n";
  128. //    }
  129.     if(n == 1)
  130.         return true;
  131. //    cerr << "+ok\n";
  132.     for(int i = 0; i < n; i++){
  133.         for(int j = 0; j <= i; j++){
  134.             assert(n-1-i >= 0);
  135.             assert(n-1-j >= 0);
  136.             assert(n-1-j < n);
  137.             assert(n-1-i < n);
  138.             if(gr[i][j] != gr[j][i])
  139.                 return false;
  140.         }
  141.     }
  142.     for(int i = 0; i < n; i++){
  143.         for(int j = 0; j < n-i; j++){
  144.             if(gr[i][j] != gr[n-j-1][n-i-1])
  145.                 return false;
  146.         }
  147.     }
  148.     int d = (n+1)/2;
  149.     for(int i = 0; i < n; i++){
  150.         for(int j = 0; j < n/2; j++){
  151.             if(gr[i][j] != gr[i][j+d])
  152.                 return false;
  153.         }
  154.     }
  155.     for(int i = 0; i < n/2; i++){
  156.         for(int j = 0; j < n; j++){
  157.             if(gr[i][j] != gr[i+d][j])
  158.                 return false;
  159.         }
  160.     }
  161.     d = n/2;
  162. //    cerr << "-ok\n";
  163.     auto g1 = subMatrix(0,0,d-1,d-1,gr);
  164.     if(!ok(g1))
  165.         return false;
  166.     auto g2 = subMatrix(n-1-d+1,n-d,n-1,n-1,gr);
  167.     if(!ok(g2))
  168.         return false;
  169.     auto g3 = subMatrix(0,n-1,d-1,n-d,gr);
  170.     if(!ok(g3))
  171.         return false;
  172.     auto g4 = subMatrix(n-1,0,n-d,d-1,gr);
  173.     if(!ok(g4))
  174.         return false;
  175.     assert(g1 == g2 && g2 == g3 && g3 == g4);
  176.     return true;
  177. }
  178. int n;
  179. int g[30][30];
  180.  
  181. int val(vector<vector<int>>& gr){
  182.     int ans = 0;
  183.     for(int i = 0; i < gr.size(); i++){
  184.         for(int j = 0; j < gr[i].size(); j++){
  185.             ans = (ans << 1) + gr[i][j];
  186.             ans %= md;
  187.         }
  188.     }
  189.     return ans;
  190. }
  191.  
  192. vector<int> v;
  193.  
  194. void rec(int x,int y){
  195.     if(y == n){
  196.         y = 0;
  197.         x++;
  198.     }
  199.     if(x == n){
  200.         vector<vector<int>> gr;
  201.         for(int i = 0; i < n; i++){
  202.             gr.pb(vector<int>());
  203.             for(int j = 0; j < n; j++){
  204.                 gr.back().pb(g[i][j]);
  205.             }
  206.         }
  207.         if(ok(gr)){
  208.             for(int i = 0; i < n; i++){
  209.                 for(int j = 0; j < n; j++){
  210.                     cout << g[i][j] << " ";
  211.                 }
  212.                 cout << "\n";
  213.             }
  214.             cout << "val = " << val(gr) << "\n";
  215.             cout << "\n";
  216.             v.pb(val(gr));
  217.         }
  218.         return;
  219.     }
  220.     g[x][y] = 0;
  221.     rec(x,y+1);
  222.     g[x][y] = 1;
  223.     rec(x,y+1);
  224.     return;
  225. }
  226.  
  227. //int n,m;
  228. //vector<int> inc(vector<int> A,int d){
  229. //    for(auto& x : A)
  230. //        x = (x + d) % m;
  231. //    return A;
  232. //}
  233. //
  234. //vector<int> arr(int k){
  235. //    if(k == 0)
  236. //        return vector<int>{0};
  237. //    vector<int> A = arr(k-1);
  238. //    vector<int> ans;
  239. //    for(int i = 0; i < m; i++){
  240. //        auto t = inc(A,i);
  241. //        for(auto& x : t)
  242. //            ans.pb(x);
  243. //    }
  244. //    return ans;
  245. //}
  246.  
  247. string divide8(string& s){
  248.     for(int i = 0; i < 2 && !s.empty(); i++){
  249.         s.pop_back();
  250.     }
  251.     if(s == "")
  252.         s = "0";
  253.     return s;
  254. }
  255.  
  256. int getRem8(string& s){
  257.     int r = 0;
  258.     int n = s.size();
  259.     for(int i = 1; i >= 0; i--){
  260.         r = 2*r;
  261.         if(n - 1 - i >= 0)
  262.             r += s[n-1-i] - '0';
  263.     }
  264.     return r;
  265. }
  266.  
  267. vector<vector<int>> make(vector<vector<int>>& t){
  268.     vector<vector<int>> ans;
  269.     int n = t.size();
  270.     ans = t;
  271.     for(int i = 0; i < n; i++){
  272.         for(int j = 0; j < n; j++){
  273.             ans[i].pb(ans[i][j]);
  274.         }
  275.     }
  276.     for(int i = 0; i < n; i++){
  277.         ans.pb(ans[i]);
  278.     }
  279.     return ans;
  280. }
  281.  
  282. vector<vector<int>> get(int n,string s){
  283. //    cerr << "n = " << n << ", k = " << s << "\n";;
  284.     if(n == 1){
  285.         if(s == "1")
  286.             return vector<vector<int>>{{1}};
  287.         else
  288.             return vector<vector<int>>{{0}};
  289.     }
  290.     if(n % 2 == 0){
  291. //        cerr << "ok2+ " << n << "\n";
  292.         auto t = get(n>>1,s);
  293. //        cerr << "ok2- " << n << "\n";
  294.         return make(t);
  295.     }
  296.     int r = getRem8(s);
  297.     r %= 4;
  298. //    cerr << "ok+ " << n << "\n";
  299.     auto t = get(n>>1,divide8(s));
  300. //    cerr << "ok- " << n << "\n";
  301. //    cerr << "r = " << r << "\n";
  302.     if(r == 0){
  303.         vector<vector<int>> ans;
  304.         int nn = t.size();
  305.         ans = t;
  306.         for(int i = 0; i < nn; i++){
  307.             ans[i].pb(0);
  308.             for(int j = 0; j < nn; j++){
  309.                 ans[i].pb(ans[i][j]);
  310.             }
  311.         }
  312.         ans.pb(vector<int>(n,0));
  313.         for(int i = 0; i < nn; i++){
  314.             ans.pb(ans[i]);
  315.         }
  316.         return ans;
  317.     }
  318.     if(r == 1){
  319.         vector<vector<int>> ans;
  320.         int nn = t.size();
  321.         ans = t;
  322.         for(int i = 0; i < nn; i++){
  323.             ans[i].pb(0);
  324.             for(int j = 0; j < nn; j++){
  325.                 ans[i].pb(ans[i][j]);
  326.             }
  327.         }
  328.         ans.pb(vector<int>(n,0));
  329.         for(int i = 0; i < nn; i++){
  330.             ans.pb(ans[i]);
  331.         }
  332.         ans[nn][nn] = 1;
  333. //        cerr << "o!\n";
  334.         return ans;
  335.     }
  336.     if(r == 2){
  337.         vector<vector<int>> ans;
  338.         int nn = t.size();
  339.         ans = t;
  340.         for(int i = 0; i < nn; i++){
  341.             ans[i].pb(1);
  342.             for(int j = 0; j < nn; j++){
  343.                 ans[i].pb(ans[i][j]);
  344.             }
  345.         }
  346.         ans.pb(vector<int>(n,1));
  347.         for(int i = 0; i < nn; i++){
  348.             ans.pb(ans[i]);
  349.         }
  350.         ans[nn][nn] = 0;
  351.         return ans;
  352.     }
  353.     if(r == 3){
  354.         vector<vector<int>> ans;
  355.         int nn = t.size();
  356.         ans = t;
  357.         for(int i = 0; i < nn; i++){
  358.             ans[i].pb(1);
  359.             for(int j = 0; j < nn; j++){
  360.                 ans[i].pb(ans[i][j]);
  361.             }
  362.         }
  363.         ans.pb(vector<int>(n,1));
  364.         for(int i = 0; i < nn; i++){
  365.             ans.pb(ans[i]);
  366.         }
  367.         return ans;
  368.     }
  369.     assert(false);
  370.     return {};
  371. }
  372.  
  373. void decrease1(string& s){
  374.     for(int i = s.size()-1; i >= 0; i--){
  375.         if(s[i] == '0'){
  376.             s[i] = '1';
  377.             continue;
  378.         } else {
  379.             s[i] = '0';
  380.             break;
  381.         }
  382.     }
  383.     if(s[0] == '0')
  384.         s.erase(0,1);
  385.     if(s == "")
  386.         s = "0";
  387.     return;
  388. }
  389.  
  390. void solve(){
  391. //    cin >> n >> m;
  392. //
  393. //    auto v = arr(n);
  394. //
  395. //    for(auto& x : v){
  396. //        cout << x << " ";
  397. //    }
  398. //    cout << "\n";
  399.  
  400.     string k;
  401.     cin >> n;
  402.     rec(0,0);
  403.     sort(v.begin(),v.end());
  404.     for(auto& x : v)
  405.         cout << x << " ";
  406.     cout << "\n";
  407.     return;
  408. //    cin >> k;
  409.     decrease1(k);
  410.  
  411.     auto gr = get(n,k);
  412.     int ans = 0;
  413.     assert(gr.size() == n);
  414.     for(int i = 0; i < n; i++){
  415.         for(int j = 0; j < n; j++){
  416. //            cout << gr[i][j] << " ";
  417.             ans = 2 * ans + gr[i][j];
  418.             ans %= md;
  419.         }
  420. //        cout << "\n";
  421.     }
  422.     cout << ans << "\n";
  423.     return;
  424. }
  425.  
  426. signed main(){
  427.     ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
  428.     int tests = 1;
  429. //    cin >> tests;
  430.     for(int test = 1; test <= tests; test++){
  431. //        cerr << "test = " << test << "\n";
  432.         solve();
  433.     }
  434.     return 0;
  435. }
  436. /**
  437. 5
  438. 0 0 0 0 0
  439. 0 0 0 0 0
  440. 0 0 0 0 0
  441. 0 0 0 0 0
  442. 0 0 0 0 0
  443. val = 0
  444.  
  445. 0 0 0 0 0
  446. 0 0 0 0 0
  447. 0 0 1 0 0
  448. 0 0 0 0 0
  449. 0 0 0 0 0
  450. val = 4096
  451.  
  452. 0 0 1 0 0
  453. 0 0 1 0 0
  454. 1 1 0 1 1
  455. 0 0 1 0 0
  456. 0 0 1 0 0
  457. val = 4353156
  458.  
  459. 0 0 1 0 0
  460. 0 0 1 0 0
  461. 1 1 1 1 1
  462. 0 0 1 0 0
  463. 0 0 1 0 0
  464. val = 4357252
  465.  
  466. 1 1 0 1 1
  467. 1 1 0 1 1
  468. 0 0 0 0 0
  469. 1 1 0 1 1
  470. 1 1 0 1 1
  471. val = 29197179
  472.  
  473. 1 1 0 1 1
  474. 1 1 0 1 1
  475. 0 0 1 0 0
  476. 1 1 0 1 1
  477. 1 1 0 1 1
  478. val = 29201275
  479.  
  480. 1 1 1 1 1
  481. 1 1 1 1 1
  482. 1 1 0 1 1
  483. 1 1 1 1 1
  484. 1 1 1 1 1
  485. val = 33550335
  486.  
  487. 1 1 1 1 1
  488. 1 1 1 1 1
  489. 1 1 1 1 1
  490. 1 1 1 1 1
  491. 1 1 1 1 1
  492. val = 33554431
  493.  
  494. 0 4096 4353156 4357252 29197179 29201275 33550335 33554431
  495. **/
  496.  
Advertisement
RAW Paste Data Copied
Advertisement