Olya and magical square

Created by LXC on Fri Nov 3 13:22:53 2023

https://codeforces.com/problemset/problem/1080/D

ranting: 2000

tag: constructive algorithms, implementation, math

problem

给出一个数n和k，代表着有一个$2^n\times2^n$的正方形，和操作k次。

每次操作可以从当前局面中选出一个正方形，将其划分为四个小正方形。

问能否在k次操作后，使得左下角的正方形和右上角的正方形边长都为l，且两者间存在一条边长都为l的正方形组成的路径。

输出可能的l。

solution

先考虑每个$2^n\times2^n$最多能分割的次数。

对于$2^i\times2^i$分割的次数为$a_i$，则$a_1=1,a_i = 4a_{i-1}+1$。

利用母函数求其通项公式。

设$G(x) = a_1x + a_2x^2 + a_3x^3 + \cdots$

对于i>1的$a_i$替换为$4a_{i-1}+1$

$G(x) = a_1x + (4a_1+1)x^2 + (4a_2+1)x^3 + \cdots = (x+x^2+x^3+\cdots)+4xG(x)$

由于$\frac{1}{1-x} = 1+x+x^2+x^3+\cdots$

$G(x) = \frac{x}{1-x} + 4xG(x) \Rightarrow G(x) = \frac{x}{(1-x)(1-4x)} = \frac{1}{3}(\frac{1}{1-4x}-\frac{1}{1-x}) = \frac{1}{3}[(1+4x+4^2x^2+\cdots)-(1+x+x^2+\cdots)]$

$x^i$的系数$a_i = \frac{4^i-1}{3}$即为通项公式。

显然如果可以分割次数小于k，是无法做到的。另一个情况就是如果$a_{n-1} \ge k-1$，我们可以花费一次操作，然后右下角的正方形可以操作$a_{n-1}$次，这个次数如果大于等于k-1说明一定行。我们只需输出n-1即可。

否则，我们可以从n-1到1枚举路径边长l。让k减去能形成这条路径的代价操作次数。统计非路径上的正方形可分割的次数c。如果k在非负的情况下k不大于c。则说明当前非路径上的正方形可以分配剩余的步数。答案就是l。

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    ll opt[32] = {0};
    opt[1] = 1;
    for (int i = 2; i < 32; i++) {
        opt[i] = (opt[i - 1]) * 4 + 1;
        // cout << i << " " << opt[i] << endl;
    }
    ll n, k;
    cin >> n >> k;
    if (n > 31) {
        cout << "YES " << n - 1 << "\n";
        return;
    }
    ll c = 0, a = 1;
    for (int i = n - 1; i >= 0; i--) {
        k -= a;
        c += (a * 2 - 1) * opt[i];
        // cout << i << " " << k << " " << c << endl;
        if (0 <= k && k <= c) {
            cout << "YES " << i << "\n";
            return;
        }
        a = a * 2 + 1;
    }
    cout << "NO\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}