API tools faq
paste
Advertisement
_no0B

Untitled

_no0B
Apr 25th, 2019
206
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 30.91 KB | None | 0 0
raw download clone embed print report
  1. /// Longest common increasing subsequence of A and B in O(n * m)
  2. #define MAX 2057
  3. int lcis(int n, int* A, int m, int* B){
  4.     int i, j, l, res, dp[MAX] = {0};
  5.     for (i = 0; i < n; i++){
  6.         for (l = 0, j = 0; j < m; j++){
  7.             if (A[i] == B[j] && dp[j] <= l) dp[j] = l + 1;
  8.             else if (B[j] < A[i] && dp[j] > l) l = dp[j];
  9.         }
  10.     }
  11.     for (i = 0, res = 0; i < m; i++){
  12.         if (dp[i] > res) res = dp[i];
  13.     }
  14.     return res;
  15. }
  16.  
  17.  
  18.  
  19. /// Knight's Tour In Infinite Chessboard
  20. /// Minimum number of knight moves from (x,y) to (0,0) in non-negative infinite chessboard
  21. int knight_move(int x, int y){
  22.     int a, b, z, c, d;
  23.     x = abs(x), y = abs(y);
  24.     if (x < y) a = x, x = y, y = a;
  25.     if (x == 2 && y == 2) return 4;
  26.     if (x == 1 && y == 0) return 3;
  27.     if (y == 0 || (y << 1) < x){
  28.         c = y & 1;
  29.         a = x - (c << 1), b = a & 3;
  30.         return ((a - b) >> 1) + b + c;
  31.     }
  32.     else{
  33.         d = x - ((x - y) >> 1);
  34.         z = ((d % 3) != 0), c = (x - y) & 1;
  35.         return ((d / 3) * 2) + c + (z * 2 * (1 - c));
  36.     }
  37. }
  38.  
  39.  
  40. /// Maximum XOR Subest
  41. #define MAX 100010
  42. #define bitlen(x) ((x) == 0 ? (0) : (64 - __builtin_clzll(x)))
  43. long long ar[MAX];
  44. long long solve(int n, long long* ar){ /// hash = 220650
  45.     vector <long long> v[64];
  46.     for (int i = 0; i < n; i++) v[bitlen(ar[i])].push_back(ar[i]);
  47.     long long m, x, res = 0;
  48.     for (int i = 63; i > 0; i--){
  49.         int l = v[i].size();
  50.         if (l){
  51.             m = v[i][0];
  52.             res = max(res, res ^ m);
  53.  
  54.             for (int j = 1; j < l; j++){
  55.                 x = m ^ v[i][j];
  56.                 if (x) v[bitlen(x)].push_back(x);
  57.             }
  58.             v[i].clear();
  59.         }
  60.     }
  61.     return res;
  62. }
  63.  
  64.  
  65.  
  66. /// N queen
  67. int n, lim, counter;
  68. void backtrack(int i, int c, int l, int r){
  69.     if (!i){
  70.         counter++;
  71.         return;
  72.     }
  73.     int bitmask, x;
  74.     --i, bitmask = lim & ~(l | r | c);
  75.     while (bitmask){
  76.         x = (-bitmask & bitmask);
  77.         if (!x) return;
  78.         bitmask ^= x;
  79.         backtrack(i, c | x, (l | x) << 1, (r | x) >> 1);
  80.     }
  81. }
  82. int main(){
  83.     while (scanf("%d", &n)){
  84.         counter = 0, lim = (1 << n) - 1;
  85.         backtrack(n, 0, 0, 0);
  86.         printf("%d solutions for a %d x %d chessboard\n", counter, n, n);
  87.     }
  88.     return 0;
  89. }
  90.  
  91.  
  92.  
  93. /// next small
  94. #define MAX 250010
  95. int ar[MAX], L[MAX], R[MAX], stack[MAX], time[MAX];
  96. void next_small(int n, int* ar, int* L){
  97.     int i, j, k, l, x, top = 0;
  98.  
  99.     for (i = 0; i < n; i++){
  100.         x = ar[i];
  101.         if (top && stack[top] >= x){
  102.             while (top && stack[top] >= x) k = time[top--];
  103.             L[i] = (i - k + 2);
  104.             stack[++top] = x;
  105.             time[top] = k;
  106.         }
  107.         else{
  108.             L[i] = 1;
  109.             stack[++top] = x;
  110.             time[top] = i + 1;
  111.         }
  112.     }
  113. }
  114. /*** L[i] contains maximum length of the range from i to the left such that the minimum of this range
  115.      is not less than ar[i].
  116.      Similarly, R[i] contains maximum length of the range from i to the right such that the minimum
  117.      of this range is not less than ar[i]
  118.  
  119.      For example, ar[] = 5 3 4 3 1 2 6
  120.                   L[]  = 1 2 1 4 5 1 1
  121.                   R[]  = 1 3 1 1 3 2 1
  122. ***/
  123. void fill(int n, int* ar, int* L, int* R){
  124.     int i, j, k;
  125.     for (i = 0; i < n; i++) L[i] = ar[n - i - 1];
  126.     next_small(n, L, R);
  127.     next_small(n, ar, L);
  128.     i = 0, j = n - 1;
  129.     while (i < j){
  130.         k = R[i], R[i] = R[j], R[j] = k;
  131.         i++, j--;
  132.     }
  133. }
  134. int main(){
  135.     int n, i, j, k;
  136.     scanf("%d", &n);
  137.     for (i = 0; i < n; i++) scanf("%d", &ar[i]);
  138.     fill(n, ar, L, R);
  139.     for (i = 0; i < n; i++) printf("%d ", ar[i]);
  140.     puts("");
  141.     for (i = 0; i < n; i++) printf("%d ", R[i]);
  142.     puts("");
  143.     for (i = 0; i < n; i++) printf("%d ", L[i]);
  144.     puts("");
  145.     return 0;
  146. }
  147.  
  148.  
  149.  
  150. /// output compression
  151. int base = 0, mp[256];
  152. char digit[256], str[256], temp[256];
  153. void Generate(){
  154.     int i;
  155.     for (i = 32; i < 127; i++){
  156.         if (i == 32 || i == 34 || i == 39 || i == 44 || i == 92) continue;
  157.         digit[base] = i;
  158.         mp[i] = base;
  159.         base++;
  160.     }
  161.     digit[base] = 0;
  162. }
  163. void encode(char* str, int v){
  164.     int i, j, k = 0, l = 0;
  165.     do{
  166.         temp[k++] = digit[v % base];
  167.         v /= base;
  168.     } while (v);
  169.     for (i = k - 1; i >= 0; i--) str[l++] = temp[i];
  170.     str[l] = 0;
  171. }
  172. int decode(char* str){
  173.     int i, v = 0;
  174.     for (i = 0; str[i]; i++) v = (v * base) + mp[str[i]];
  175.     return v;
  176. }
  177. int main(){
  178.     read();
  179.     Generate();
  180.     encode(str, 12345);
  181.     printf("%d\n", decode(str));
  182.     return 0;
  183. }
  184.  
  185.  
  186.  
  187. /// Permutation Index
  188. #define MAX 12
  189. #define hash(ar)  dp[ar[0]][ar[1]][ar[2]][ar[3]][ar[4]][ar[5]]
  190. #define lexic(ar) pos[ar[0]][ar[1]][ar[2]][ar[3]][ar[4]][ar[5]]
  191. char ar[MAX];
  192. int n, m, counter, factorial[MAX];
  193. int last[1 << MAX], dp[MAX][MAX][MAX][MAX][MAX][MAX], pos[MAX][MAX][MAX][MAX][MAX][MAX];
  194. void backtrack(int i, int bitmask, int flag){
  195.     if (i == m){
  196.         if (flag & 1) hash(ar) = ++counter;
  197.         if (flag & 2) lexic(ar) = last[bitmask]++;
  198.         return;
  199.     }
  200.     int j;
  201.     for (j = 0; j < n; j++){
  202.         if (!(bitmask & (1 << j))){
  203.             ar[i] = j;
  204.             backtrack(i + 1, bitmask | (1 << j), flag);
  205.         }
  206.     }
  207. }
  208. void Generate(){
  209.     int i, j;
  210.     clr(ar), clr(last);
  211.     counter = 0, m = n >> 1, factorial[0] = 1;
  212.     for (i = 1; i < MAX; i++) factorial[i] = factorial[i - 1] * i;
  213.     if (n & 1){
  214.         backtrack(0, 0, 1);
  215.         m++;
  216.         backtrack(0, 0, 2);
  217.         m--;
  218.     }
  219.     else backtrack(0, 0, 3);
  220. }
  221. int F(int P[MAX]){
  222.     int i, a = 0, b = 0;
  223.     char A[6] = {0}, B[6] = {0};
  224.     for (i = 0; i < m; i++) A[a++] = P[i];
  225.     for (i = m; i < n; i++) B[b++] = P[i];
  226.     return ((hash(A) - 1) * factorial[b]) + lexic(B) + 1;
  227. }
  228. int main(){
  229.     int i, j, P[MAX];
  230.     while (scanf("%d", &n) != EOF){
  231.         Generate();
  232.         for (i = 0; i < n; i++) scanf("%d", &P[i]);
  233.         for (i = 0; i < n; i++) P[i]--;
  234.         int res = F(P);
  235.         printf("%d\n", res);
  236.     }
  237.     return 0;
  238. }
  239.  
  240.  
  241.  
  242. /// Permutation Rank
  243. /// Find's the rank of permutation
  244. /// Rank and permutation elements are 1 base indexed
  245. long long find_rank(vector <int> permutation){
  246.     long long res = 1;
  247.     int i, j, n = permutation.size();
  248.     vector <bool> visited(n + 1, false);
  249.     vector <long long> factorial(n + 1, 1);
  250.     for (i = 1; i <= n; i++) factorial[i] = factorial[i - 1] * i;
  251.     for (i = 1; i <= n; i++){
  252.         for (j = 1; j <= n; j++){
  253.             if (!visited[j]){
  254.                 if (permutation[i - 1] == j){
  255.                     visited[j] = true;
  256.                     break;
  257.                 }
  258.                 res += factorial[n - i];
  259.             }
  260.         }
  261.     }
  262.     return res;
  263. }
  264. /// Find's the k'th permutation of 1 to n
  265. /// Rank and permutation elements are 1 base indexed
  266. vector <int> find_rank(int n, long long k){
  267.     int i, j;
  268.     vector <int> res(n, 0);
  269.     vector <bool> visited(n + 1, false);
  270.     vector <long long> factorial(n + 1, 1);
  271.     for (i = 1; i <= n; i++) factorial[i] = factorial[i - 1] * i;
  272.     for (i = 1; i <= n; i++){
  273.         for (j = 1; j <= n; j++){
  274.             if (!visited[j]){
  275.                 if (factorial[n - i] >= k){
  276.                     visited[j] = true;
  277.                     res[i - 1] = j;
  278.                     break;
  279.                 }
  280.                 k -= factorial[n - i];
  281.             }
  282.         }
  283.     }
  284.     return res;
  285. }
  286.  
  287.  
  288.  
  289. /// Josephus
  290. /// Josephus problem, n people numbered from 1 to n stand in a circle.
  291. /// Counting starts from 1 and every k'th people dies
  292. /// Returns the position of the m'th killed people
  293. /// For example if n = 10 and k = 3, then the people killed are 3, 6, 9, 2, 7, 1, 8, 5, 10, 4 respectively
  294. /// O(n)
  295. int josephus(int n, int k, int m){
  296.     int i;
  297.     for (m = n - m, i = m + 1; i <= n; i++){
  298.         m += k;
  299.         if (m >= i) m %= i;
  300.     }
  301.     return m + 1;
  302. }
  303. /// O(k log(n))
  304. long long josephus2(long long n, long long k, long long m){ /// hash = 583016
  305.     m = n - m;
  306.     if (k <= 1) return n - m;
  307.  
  308.     long long i = m;
  309.     while (i < n){
  310.         long long r = (i - m + k - 2) / (k - 1);
  311.         if ((i + r) > n) r = n - i;
  312.         else if (!r) r = 1;
  313.         i += r;
  314.         m = (m + (r * k)) % i;
  315.     }
  316.     return m + 1;
  317. }
  318. int main(){
  319.     int n, k, m;
  320.     printf("%d\n", josephus(10, 1, 2));
  321.     printf("%d\n", josephus(10, 1, 10));
  322. }
  323.  
  324.  
  325.  
  326. /// IDAStar
  327. int ida(int g, int lim, int l, int last, int idx){ /// last = last taken move, don't go there!
  328.     int h = heuristic(l);
  329.     if (!h){ /// Goal reached
  330.         sequence[idx] = 0;
  331.         puts(sequence);
  332.         return g;
  333.     }
  334.     int f = g + h;
  335.     if (f > lim) return f;
  336.     int i, j, res = inf;
  337.     for (i = 0; i < 12; i++){
  338.         if (dis[l][i] == 1 && i != last){
  339.             sequence[idx] = str[i];
  340.             swap(str[l], str[i]);
  341.             int x = ida(g + 1, lim, i, l, idx + 1);
  342.             if (x < res) res = x; /// Update next limit in iterative deepening
  343.             swap(str[l], str[i]);
  344.             if (res <= lim) return res; /// Since iterative deepening, return if solution found
  345.         }
  346.     }
  347.     return res;
  348. }
  349. int Solve(int l){
  350.     int lim = heuristic(l);
  351.     for (; ;){
  352.         int nlim = ida(0, lim, l, l, 0);
  353.         if (nlim <= lim) return nlim;
  354.         else lim = nlim;
  355.     }
  356.     return -1;
  357. }
  358.  
  359.  
  360.  
  361. /// Histogram Area
  362. #define MAX 2010
  363. int n, ar[MAX];
  364. /*** Largest area in a histogram ***/
  365. /*** Be careful, long long might be required ***/
  366. int histogram(int n, int* ar){
  367.     int i = 0, j, a, x, top = 0, res = 0;
  368.     stack[0] = -1;
  369.     while (i < n){
  370.         if (!top || (ar[stack[top]] <= ar[i]) ) stack[++top] = i++;
  371.         else{
  372.             x = stack[top--];
  373.             a = ar[x] * (i - stack[top] - 1);
  374.             if (a > res) res = a;
  375.         }
  376.     }
  377.     while (top){
  378.         x = stack[top--];
  379.         a = ar[x] * (i - stack[top] - 1);
  380.         if (a > res) res = a;
  381.     }
  382.     return res;
  383. }
  384.  
  385.  
  386.  
  387. /// HashMap
  388. using namespace std;
  389. struct hashmap{
  390.     int t, sz, hmod;
  391.     vector <int> id;
  392.     vector <long long> key, val;
  393.     inline int nextPrime(int n){
  394.         for (int i = n; ;i++){
  395.             for (int j = 2; ;j++){
  396.                 if ((j * j) > i) return i;
  397.                 if ((i % j) == 0) break;
  398.             }
  399.         }
  400.         return -1;
  401.     }
  402.     void clear(){t++;}
  403.     inline int pos(unsigned long long x){
  404.         int i = x % hmod;
  405.         while (id[i] == t && key[i] != x) i++;
  406.         return i;
  407.     }
  408.     inline void insert(long long x, long long v){
  409.         int i = pos(x);
  410.         if (id[i] != t) sz++;
  411.         key[i] = x, val[i] = v, id[i] = t;
  412.     }
  413.     inline void erase(long long x){
  414.         int i = pos(x);
  415.         if (id[i] == t) key[i] = 0, val[i] = 0, id[i] = 0, sz--;
  416.     }
  417.     inline long long find(long long x){
  418.         int i = pos(x);
  419.         return (id[i] != t) ? -1 : val[i];
  420.     }
  421.     inline bool contains(long long x){
  422.         int i = pos(x);
  423.         return (id[i] == t);
  424.     }
  425.     inline void add(long long x, long long v){
  426.         int i = pos(x);
  427.         (id[i] == t) ? (val[i] += v) : (key[i] = x, val[i] = v, id[i] = t, sz++);
  428.     }
  429.     inline int size(){
  430.         return sz;
  431.     }
  432.     hashmap(){}
  433.     hashmap(int m){
  434.         srand(time(0));
  435.         m = (m << 1) - ran(1, m);
  436.         hmod = nextPrime(max(100, m));
  437.         sz = 0, t = 1;
  438.         id.resize(hmod + 0x1FF, 0);
  439.         key.resize(hmod + 0x1FF, 0), val.resize(hmod + 0x1FF, 0);
  440.     }
  441. };
  442.  
  443.  
  444.  
  445. /// HakmemItem175
  446. /// Only for non-negative integers
  447. /// Returns the immediate next number with same count of one bits, -1 on failure
  448. long long hakmemItem175(long long n){
  449.     if (n == 0) return -1;
  450.     long long x = (n & -n);
  451.     long long left = (x + n);
  452.     long long right = ((n ^ left) / x) >> 2;
  453.     long long res = (left | right);
  454.     return res;
  455. }
  456. /// Returns the immediate previous number with same count of one bits, -1 on failure
  457. long long lol(long long n){
  458.     if (n == 0 || n == 1) return -1;
  459.     long long res = ~hakmemItem175(~n);
  460.     return (res == 0) ? -1 : res;
  461. }
  462.  
  463.  
  464.  
  465. /// Greedy Coin Change
  466. const int n = 10;
  467. const long long INF = 0x7FFFFFFFFFFFFFFF;
  468. const int coins[] = {0, 1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000}; /// 1 based indexing for coins
  469. long long res, counter[44], sum[44]; /// counter[i] = number of coins of type i
  470. void backtrack(int i, long long p, long long c){ /// Complexity 2^n
  471.     if (p == 0 && c < res) res = c; /// Change min to max here
  472.     if (i == 0 || p <= 0) return;
  473.  
  474.     long long k, x = 0;
  475.     if ((p - sum[i - 1]) > x) x = p - sum[i - 1];
  476.     k = (x / coins[i]) + (x % coins[i] != 0);
  477.     if (k <= counter[i]) backtrack(i - 1, p - k * coins[i], c + k);
  478.     if (++k <= counter[i]) backtrack(i - 1, p - k * coins[i], c + k); /// Do this multiple times if WA (around 5 or 10 should do)
  479. }
  480. /// Minimum number of coins required to make s from coin values and count of coin values
  481. /// -1 if no solution
  482. long long solve(long long s){
  483.     int i, j;
  484.     for (i = 1; i <= n; i++) sum[i] = sum[i - 1] + coins[i] * counter[i];
  485.     res = INF;
  486.     backtrack(n, s, 0);
  487.     if (res == INF) res = -1;
  488.     return res;
  489. }
  490.  
  491.  
  492.  
  493. /// gray codes
  494. long long gray_code(long long x){
  495.     return x ^ (x >> 1);
  496. }
  497. long long inverse_gray_code(long long x){
  498.     long long h = 1, res = 0;
  499.     do{
  500.         if (x & 1) res ^= h;
  501.         x >>= 1, h = (h << 1) + 1;
  502.     } while (x);
  503.     return res;
  504. }
  505.  
  506.  
  507.  
  508. /// Gambler's ruin problem
  509. /// First player has n1 coins, second player has n2 coins
  510. /// After each move, first player wins with probability p and second player wins with probability q (p + q == 1)
  511. /// The loser gives 1 coin to the winner
  512. /// When number of coins reaches 0, a player loses
  513. /// Returns the probability of first player winning
  514. long double expo(long double x, int n){
  515.     if (n == 0) return 1;
  516.     if (n & 1) return expo(x, n - 1) * x;
  517.     else{
  518.         long double res = expo(x, n >> 1);
  519.         return res * res;
  520.     }
  521. }
  522. long double gamblers_ruin(int n1, int n2, long double p, long double q){
  523.     if (fabs(p - q) <= 1e-9){
  524.         return (long double)n2 / (n1 + n2);
  525.     }
  526.  
  527.     long double x = 1.0 - expo(q / p, n2);
  528.     long double y = 1.0 - expo(q / p, n1 + n2);
  529.     return (x / y);
  530. }
  531.  
  532.  
  533.  
  534. /// Faulhaber's Formula
  535. #define MAX 2510
  536. #define MOD 1000000007
  537. int S[MAX][MAX], inv[MAX];
  538. int expo(long long x, int n){
  539.     x %= MOD;
  540.     long long res = 1;
  541.     while (n){
  542.         if (n & 1) res = (res * x) % MOD;
  543.         x = (x * x) % MOD;
  544.         n >>= 1;
  545.     }
  546.     return (res % MOD);
  547. }
  548. void Generate(){
  549.     int i, j;
  550.     for (i = 0; i < MAX; i++) inv[i] = expo(i, MOD - 2);
  551.     S[0][0] = 1;
  552.     for (i = 1; i < MAX; i++){
  553.         S[i][0] = 0;
  554.         for (j = 1; j <= i; j++){
  555.             S[i][j] = ( ((long long)S[i - 1][j] * j) + S[i - 1][j - 1]) % MOD;
  556.         }
  557.     }
  558. }
  559. int faulhaber(long long n, int k){
  560.     n %= MOD;
  561.     if (!k) return n;
  562.     int j;
  563.     long long res = 0, p = 1;
  564.     for (j = 0; j <= k; j++){
  565.         p = (p * (n + 1 - j)) % MOD;
  566.         res = (res + (((S[k][j] * p) % MOD) * inv[j + 1])) % MOD;
  567.     }
  568.     return (res % MOD);
  569. }
  570. int main(){
  571.     Generate();
  572.     printf("%d\n", faulhaber(1001212, 1000));
  573.     return 0;
  574. }
  575.  
  576.  
  577.  
  578. /// Faulhaber's Formula (Custom Algorithm)
  579. #define MAX 1010
  580. #define MOD 1000000007
  581. namespace fool{
  582.     #define MAXN 10000
  583.     tr1::unordered_map <unsigned long long, int> mp;
  584.     int inv, P[MAX], binomial[MAX][MAX], dp[MAXN][MAX];
  585.     long long expo(long long x, long long n){
  586.         x %= MOD;
  587.         long long res = 1;
  588.         while (n){
  589.             if (n & 1) res = (res * x) % MOD;
  590.             x = (x * x) % MOD;
  591.             n >>= 1;
  592.         }
  593.         return (res % MOD);
  594.     }
  595.     void init(){
  596.         int i, j;
  597.         mp.clear();
  598.         inv = expo(2, MOD - 2);
  599.         P[0] = 1;
  600.         for (i = 1; i < MAX; i++){
  601.             P[i] = (P[i - 1] << 1);
  602.             if (P[i] >= MOD) P[i] -= MOD;
  603.         }
  604.         for (i = 0; i < MAX; i++){
  605.             for (j = 0; j <= i; j++){
  606.                 if (i == j || !j) binomial[i][j] = 1;
  607.                 else{
  608.                     binomial[i][j] = (binomial[i - 1][j] + binomial[i - 1][j - 1]);
  609.                     if (binomial[i][j] >= MOD) binomial[i][j] -= MOD;
  610.                 }
  611.             }
  612.         }
  613.         for (i = 1; i < MAXN; i++){
  614.             long long x = 1;
  615.             for (j = 0; j < MAX; j++){
  616.                 dp[i][j] = dp[i - 1][j] + x;
  617.                 if (dp[i][j] >= MOD) dp[i][j] -= MOD;
  618.                 x = (x * i) % MOD;
  619.             }
  620.         }
  621.     }
  622.     /// Returns (1^k + 2^k + 3^k + .... n^k) % MOD
  623.     long long F(unsigned long long n, int k){
  624.         if (n < MAXN) return dp[n][k];
  625.         if (n == 1) return 1;
  626.         if (n == 2) return (P[k] + 1) % MOD;
  627.         if (!k) return (n % MOD);
  628.         if (k == 1){
  629.             n %= MOD;
  630.             return (((n * (n + 1)) % MOD) * inv) % MOD;
  631.         }
  632.         unsigned long long h = (n << 10LL) | k; /// Change hash function according to limits of n and k
  633.         long long res = mp[h];
  634.         if (res) return res;
  635.         if (n & 1) res = F(n - 1, k) + expo(n, k);
  636.         else{
  637.             long long m, z;
  638.             m = n >> 1;
  639.             res = (F(m, k) * P[k]) % MOD;
  640.             m--, res++;
  641.             for (int i = 0; i <= k; i++){
  642.                 z = (F(m, i) * binomial[k][i]) % MOD;
  643.                 z = (z * P[i]) % MOD;
  644.                 res += z;
  645.             }
  646.         }
  647.         res %= MOD;
  648.         return (mp[h] = res);
  649.     }
  650.     long long faulhaber(unsigned long long n, int k){
  651.         ///fool::init();
  652.         return F(n, k);
  653.     }
  654. }
  655. int main(){
  656.     fool::init();
  657.     int t, i, j;
  658.     long long n, k, res;
  659.     cin >> t;
  660.     while (t--){
  661.         cin >> n >> k;
  662.         res = fool::faulhaber(n, k);
  663.         cout << res << endl;
  664.     }
  665.     return 0;
  666. }
  667.  
  668.  
  669.  
  670. /// CKY algo
  671. The Cocke–Younger–Kasami algorithm (alternatively called CYK, or CKY) is a parsing algorithm for context-free grammars,
  672. named after its inventors, John Cocke, Daniel Younger and Tadao Kasami. It employs bottom-up parsing and dynamic programming.
  673.  
  674. The standard version of CYK operates only on context-free grammars given in Chomsky normal form (CNF).
  675. However any context-free grammar may be transformed to a CNF grammar expressing the same language.
  676.  
  677. The importance of the CYK algorithm stems from its high efficiency in certain situations. Using Landau symbols,
  678. the worst case running time of CYK is O(N^3 * |G|), where N is the length of the parsed string and |G| is the
  679. size of the CNF grammar G. This makes it one of the most efficient parsing algorithms in terms of worst-case
  680. asymptotic complexity, although other algorithms exist with better average running time in many practical scenarios.
  681.  
  682. Pseudocode:
  683.  
  684. let the input be a string S consisting of n characters: a1 ... an.
  685. let the grammar contain r nonterminal symbols R1 ... Rr.
  686. This grammar contains the subset Rs which is the set of start symbols.
  687. let P[n,n,r] be an array of booleans. Initialize all elements of P to false.
  688. for each i = 1 to n
  689.   for each unit production Rj -> ai
  690.     set P[1,i,j] = true
  691. for each i = 2 to n -- Length of span
  692.   for each j = 1 to n-i+1 -- Start of span
  693.     for each k = 1 to i-1 -- Partition of span
  694.       for each production RA -> RB RC
  695.         if P[k,j,B] and P[i-k,j+k,C] then set P[i,j,A] = true
  696. if any of P[n,1,x] is true (x is iterated over the set s, where s are all the indices for Rs) then
  697.   S is member of language
  698. else
  699.   S is not member of language
  700.  
  701.  
  702.  
  703. /// Combsort
  704. #define MAX 1000010
  705. int n, ar[MAX];
  706. void combsort(int n, int* ar){
  707.     if (n <= 1) return;
  708.     int i, j, x, g = n, flag = 0;
  709.     while ((g != 1) || flag){
  710.         flag = 0;
  711.         if (g != 1) g *= 0.77425;
  712.         for (i = 0; (i + g) < n; i++){
  713.             if (ar[i] > ar[i + g]){
  714.                 flag = 1;
  715.                 x = ar[i], ar[i] = ar[i + g], ar[i + g] = x;
  716.             }
  717.         }
  718.     }
  719. }
  720. int main(){
  721.     int i, j;
  722.     n = MAX - 10;
  723.     for (i = 0; i < n; i++) ar[i] = (rand() << 15 ^ rand()) % MAX;
  724.     combsort(n, ar);
  725.     for (i = 0; (i + 1) < n; i++){
  726.         if (ar[i] > ar[i + 1]) puts("fail");
  727.     }
  728.     return 0;
  729. }
  730.  
  731.  
  732. /// bit hacks
  733. unsigned int reverse_bits(unsigned int v){
  734.     v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
  735.     v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
  736.     v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
  737.     v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
  738.     return ((v >> 16) | (v << 16));
  739. }
  740. /// Returns i if x = 2^i and 0 otherwise
  741. int bitscan(unsigned int x){
  742.     __asm__ volatile("bsf %0, %0" : "=r" (x) : "0" (x));
  743.     return x;
  744. }
  745. /// Returns next number with same number of 1 bits
  746. unsigned int next_combination(unsigned int x){
  747.     unsigned int y = x & -x;
  748.     x += y;
  749.     unsigned int z = x & -x;
  750.     z -= y;
  751.     z = z >> bitscan(z & -z);
  752.     return x | (z >> 1);
  753. }
  754.  
  755.  
  756. /// Bitset Iteration
  757. char bithash[67];
  758. void init(){
  759.     int i;
  760.     for (i = 0; i < 64; i++) bithash[(1ULL << i) % 67] = i;
  761. }
  762. void iterate(unsigned long long x){
  763.     while (x){
  764.         unsigned long long y = (x & -x);
  765.         int i = bithash[y % 67];
  766.         x ^= y;
  767.         printf("%d\n", i);
  768.     }
  769. }
  770. int main(){
  771.     init();
  772.     unsigned long long x = 0b100000001011000100100101001010101001010100;
  773.     iterate(x);
  774.     return 0;
  775. }
  776.  
  777.  
  778.  
  779. /// Algorithm X + Dancing Links
  780. #define MAXR 100010
  781. #define MAXC 100010
  782. #define MAXNODE 100010
  783. /// Define MAX limits appropriately, set to large values for safety
  784. /// Dancing Links data structure to solve exact cover problems
  785. /// There are some constraints as columns and a number of rows
  786. /// Each row satisfies some constraints
  787. /// Objective is to select a subset of rows so that each constraint is satisfied exactly once
  788. /// Don't forget to initialize first by calling init()
  789. namespace dlx{ /// hash = 641985
  790.     int row[MAXNODE], col[MAXNODE];
  791.     int L[MAXNODE], R[MAXNODE], U[MAXNODE], D[MAXNODE];
  792.     int n, idx, len, selected_rows[MAXR], column_count[MAXC];
  793.     void init(int ncolumn){ /// initialize first with total number of columns (1 based)
  794.         memset(column_count, 0, sizeof(column_count));
  795.         n = ncolumn, idx = n + 1;
  796.         for (int i = 0; i <= n; i++) U[i] = D[i] = i, L[i] = i - 1, R[i] = i + 1;
  797.         L[0] = n, R[n] = 0;
  798.     }
  799.     /// r = index of row (1 based)
  800.     /// the vector columns contain the columns which are satisfied with this row
  801.     inline void addrow(int r, vector <int>& columns){ /// hash = 438353
  802.         int i, c, l = columns.size(), first = idx;
  803.         for (i = 0; i < l; i++){
  804.             c = columns[i];
  805.             L[idx] = idx - 1, R[idx] = idx + 1, D[idx] = c, U[idx] = U[c];
  806.             D[U[c]] = idx, U[c] = idx, row[idx] = r, col[idx] = c;
  807.             column_count[c]++, idx++; /// column_count[c] is the number of rows which satisfies constraint column c
  808.         }
  809.         R[idx - 1] = first, L[first] = idx - 1;
  810.     }
  811.     /// Removes column c from the structure
  812.     inline void remove(int c){ /// hash = 377852
  813.         L[R[c]] = L[c], R[L[c]] = R[c];
  814.         for (int i = D[c]; i != c; i = D[i]){
  815.             for (int j = R[i]; j != i; j = R[j]){
  816.                 column_count[col[j]]--;
  817.                 U[D[j]] = U[j], D[U[j]] = D[j];
  818.             }
  819.         }
  820.     }
  821.     /// Restores the position of column c in the structure
  822.     inline void restore(int c){ /// hash = 804101
  823.         for (int i = U[c]; i != c; i = U[i]){
  824.             for (int j = L[i]; j != i; j = L[j]){
  825.                 column_count[col[j]]++;
  826.                 U[D[j]] = j, D[U[j]] = j;
  827.             }
  828.         }
  829.         L[R[c]] = c, R[L[c]] = c;
  830.     }
  831.     /// Recursively enumerate to solve exact cover
  832.     bool algorithmX(int depth){ /// hash = 308201
  833.         if(R[0] == 0){
  834.             len = depth;
  835.             return true;
  836.         }
  837.         int i, j, c = R[0];
  838.         for (i = R[0]; i != 0; i = R[i]){ /// Select a column deterministically
  839.             if(column_count[i] < column_count[c]) c = i; /// if multiple columns exist, choose the one with minimum count
  840.         }
  841.         remove(c);
  842.         bool flag = false;
  843.         for (i = D[c]; i != c && !flag; i = D[i]){ /// While solution is not found
  844.             selected_rows[depth] = row[i];
  845.             for (j = R[i]; j != i; j = R[j]) remove(col[j]);
  846.             flag |= algorithmX(depth + 1); /// May be select rows non-deterministically here with random_shuffle?
  847.             for (j = L[i]; j != i; j = L[j]) restore(col[j]);
  848.         }
  849.         restore(c);
  850.         return flag;
  851.     }
  852.     bool exact_cover(vector<int>& rows){ /// Returns the subset of rows satisfying exact cover, false otherwise
  853.         rows.clear();
  854.         if(!algorithmX(0)) return false;
  855.         for(int i = 0; i < len; i++) rows.push_back(selected_rows[i]);
  856.         return true;
  857.     }
  858. }
  859. namespace sudoku{
  860.     inline int encode(int n, int a, int b, int c){ /// Encode information
  861.         return (a * n * n) + (b * n) + c + 1;
  862.     }
  863.     inline void decode(int n, int v, int& a, int& b, int& c){ /// Decode information
  864.         v--;
  865.         c = v % n, v /= n;
  866.         b = v % n, a = (v / n) % n;
  867.     }
  868.     bool solve(int n, int ar[25][25]){
  869.         int i, j, k, l, c;
  870.         int m = sqrt(n + 0.5); /// m * m sub-grid
  871.         int ncolumn = n * n * 4; /// n * n for cells, n * n for rows, n * n for columns and n * n for boxes
  872.         dlx::init(ncolumn);
  873.         for (i = 0; i < n; i++){
  874.             for (j = 0; j < n; j++){
  875.                 for (k = 0; k < n; k++){
  876.                     if (ar[i][j] == 0 || ar[i][j] == (k + 1)){
  877.                         vector <int> columns;
  878.                         columns.push_back(encode(n, 0, i, j)); /// Each cell can contain only 1 value
  879.                         columns.push_back(encode(n, 1, i, k)); /// Row[i] can contain only ar[i][j], if ar[i][j] != 0, otherwise it can contain any value
  880.                         columns.push_back(encode(n, 2, j, k)); /// Column[j] can contain only ar[i][j], if ar[i][j] != 0, otherwise it can contain any value
  881.                         columns.push_back(encode(n, 3, (i / m) * m + j / m, k)); /// Similarly for box numbered i / m * m + j / m
  882.                         /// Current row selection, place number k in the cell[i][j] and doing so will cover all columns in the columns vector
  883.                         int cur_row = encode(n, i, j, k);
  884.                         dlx::addrow(cur_row, columns);
  885.                     }
  886.                 }
  887.             }
  888.         }
  889.         vector<int> res;
  890.         if (!dlx::exact_cover(res)) return false;
  891.         for (l = 0; l < res.size(); l++){
  892.             decode(n, res[l], i, j, k);
  893.             ar[i][j] = k + 1;
  894.         }
  895.         return true;
  896.     }
  897. }
  898.  
  899.  
  900.  
  901. /// 15-Puzzle (Manhattan distance + Linear conflict heuristic)
  902. #define inf 1010
  903. #define swap(x, y) (x ^= y, y ^= x, x ^= y)
  904. #define F(i, j) (abs(((ar[i][j] - 1) >> 2) - i) + abs( ((ar[i][j] - 1) & 3) - j))
  905. bool flag;
  906. char str[60];
  907. char dir[] = "LRUD";
  908. int dx[] = {0, 0, -1, 1};
  909. int dy[] = {-1, 1, 0, 0};
  910. int len[4] = {0}, idx[4][4], ar[4][4], transpose[4][4];
  911. int row_conflict(int rc){
  912.     int i, j, k, x, y, res = 0;
  913.     for (i = 0; i < 4; i++){
  914.         x = (ar[rc][i] >> 2);
  915.         if (ar[rc][i] != 16) idx[x][len[x]++] = ar[rc][i];
  916.     }
  917.     for (i = 0; i < 4; i++){
  918.         if (len[i] > 1){
  919.             for (j = 0; j < len[i]; j++){
  920.                 for (k = j + 1; k < len[i]; k++){
  921.                     if (idx[i][j] > idx[i][k]) res += 2;
  922.                 }
  923.             }
  924.         }
  925.         len[i] = 0;
  926.     }
  927.     return res;
  928. }
  929. int column_conflict(int rc){
  930.     int i, j, k, x, y, res = 0;
  931.     for (i = 0; i < 4; i++){
  932.         x = (ar[i][rc] & 3);
  933.         if (ar[i][rc] != 16) idx[x][len[x]++] = ar[i][rc];
  934.     }
  935.     for (i = 0; i < 4; i++){
  936.         if (len[i] > 1){
  937.             for (j = 0; j < len[i]; j++){
  938.                 for (k = j + 1; k < len[i]; k++){
  939.                     if (idx[i][j] > idx[i][k]) res += 2;
  940.                 }
  941.             }
  942.         }
  943.         len[i] = 0;
  944.     }
  945.     return res;
  946. }
  947. int heuristic(int bx, int by){
  948.     int i, j, k, l, res, linear_conflict = 0, manhattan_distance = 0;
  949.     for (i = 0; i < 4; i++){
  950.         for (j = 0; j < 4; j++){
  951.             transpose[j][i] = ar[i][j];
  952.             if (ar[i][j] != 16){
  953.                 manhattan_distance += F(i, j);
  954.             }
  955.         }
  956.         linear_conflict += row_conflict(i);
  957.         linear_conflict += column_conflict(i);
  958.     }
  959.     res = manhattan_distance + linear_conflict;
  960.     return res;
  961. }
  962. int ida(int bx, int by, int lx, int ly, int g, int lim, int d, int h){
  963.     if (flag) return;
  964.     if (!h){
  965.         if (!flag){
  966.             flag = true;
  967.             str[d] = 0;
  968.             puts(str);
  969.         }
  970.         return g;
  971.     }
  972.     int f = g + h;
  973.     if (f > lim) return f;
  974.     int i, k, l, nh, r, res = inf;
  975.     for (i = 0; i < 4; i++){
  976.         k = bx + dx[i], l = by + dy[i];
  977.         if (k >= 0 && k < 4 && l >= 0 && l < 4 && !(k == lx && l == ly)){
  978.             nh = h;
  979.             nh -= F(k, l);
  980.             if (bx != k) nh -= row_conflict(bx), nh -= row_conflict(k);
  981.             if (by != l) nh -= column_conflict(by), nh -= column_conflict(l);
  982.             swap(ar[bx][by], ar[k][l]);
  983.             nh += F(bx, by);
  984.             if (bx != k) nh += row_conflict(bx), nh += row_conflict(k);
  985.             if (by != l) nh += column_conflict(by), nh += column_conflict(l);
  986.             str[d] = dir[i];
  987.             r = ida(k, l, bx, by, g + 1, lim, d + 1, nh);
  988.             swap(ar[bx][by], ar[k][l]);
  989.             if (r < res) res = r;
  990.             if (r <= lim) return r;
  991.         }
  992.     }
  993.     return res;
  994. }
  995. int Solve(int bx, int by){
  996.     int res, lim = heuristic(bx, by);
  997.     flag = false;
  998.     for (; ;){
  999.         res = ida(bx, by, bx, by, 0, lim, 0, heuristic(bx, by));
  1000.         if (res <= lim) return res;
  1001.         else lim = res;
  1002.     }
  1003. }
  1004. bool Solvable(int bx, int by){
  1005.     int i, j, r = 0, counter = 0;
  1006.     for (i = 0; i < 16; i++){
  1007.         if (ar[i >> 2][i & 3] == 16) r = (i >> 2);
  1008.         else{
  1009.             for (j = i + 1; j < 16; j++){
  1010.                 if (ar[j >> 2][j & 3] < ar[i >> 2][i & 3]) counter++;
  1011.             }
  1012.         }
  1013.     }
  1014.     return ((counter + r) & 1);
  1015. }
  1016. int main(){
  1017.     int t, i, j, k, bx, by;
  1018.     scanf("%d", &t);
  1019.     while (t--){
  1020.         for (i = 0; i < 4; i++){
  1021.             for (j = 0; j < 4; j++){
  1022.                 scanf("%d", &ar[i][j]);
  1023.                 if (!ar[i][j]){
  1024.                     bx = i, by = j;
  1025.                     ar[i][j] = 16;
  1026.                 }
  1027.             }
  1028.         }
  1029.         if (!Solvable(bx, by)) puts("This puzzle is not solvable.");
  1030.         else{
  1031.             int res = Solve(bx, by);
  1032.             if (res > 50) puts("This puzzle is not solvable.");
  1033.         }
  1034.     }
  1035.     return 0;
  1036. }
  1037. /*
  1038.  
  1039. 5
  1040.  
  1041. 2 3 4 0
  1042. 1 5 7 8
  1043. 9 6 10 12
  1044. 13 14 11 15
  1045.  
  1046.  
  1047. 6 2 8 4
  1048. 12 14 1 10
  1049. 13 15 3 9
  1050. 11 0 5 7
  1051.  
  1052. 6 8 4 2
  1053. 12 14 1 10
  1054. 13 15 3 9
  1055. 11 0 5 7
  1056.  
  1057. 13 1 2 4
  1058. 5 0 3 7
  1059. 9 6 10 12
  1060. 15 8 11 14
  1061.  
  1062. 0 12 9 13
  1063. 15 11 10 14
  1064. 3 7 2 5
  1065. 4 8 6 1
  1066. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!