CS academy Round 71

D Russian Dolls

Each of the N balls has a corresponding size, and small balls can be nested inside large balls. A ball can only nest one small ball, but it can be nested recursively. Now you can make $1$ balls of size $X$ into $2$ balls of size $X-1$. It is required that when there is no way to nest in the end, the size of each ball is the same. Ask how many operations are required at least.

The final situation achieved is that the largest number of balls is the largest.

Start enumerating from the current largest number of balls to see how many operations are needed. Then change the largest ball into two second largest balls, and then enumerate the number of operations required for the current number.

Complexity $O(log^2N)$.

ll n;
map<ll, ll>hax;

int split(map<ll, ll>&h, int mx)
{
	int value, num;
	tie(value, num) = *h.rbegin();

	if (num < mx || value == 1)
	{
		return 0;
	}
	h[value] = mx;
	h[value - 1] += (num - mx) * 2;
	return num - mx;
}

int cal(map<ll, ll>h, int up)
{
	int ans = 0;
	while (h.size())
	{
		int cur = split(h, up);
		if (cur >= up)return 1e9;
		ans += cur;

		int value, num;
		tie(value, num) = *h.rbegin();
		if (value == 1)
		{
			if (num>up)
			{
				return 1e9;
			}
			break;
		}
		h.erase(value);
	}
	return ans;
}

void solve()
{
	slla(n);
	int maxx = 0;
	repp(i, 1, n)
	{
		int x;
		sa(x);
		hax[x]++;
	}
	int ans = 1e9;
	int cnt = 0;
	for (int i = 0; i<30 && hax.size(); i++)
	{
		int value, num;
		tie(value, num) = *hax.rbegin();
		int tmp = cnt + cal(hax, num);
		ans = min(ans, tmp);

		cnt += split(hax, 0);
		hax.erase(hax.rbegin()->first);

		if (hax.size() && hax.rbegin()->second >= n)
		{
			ans = min(ans, cnt);
			break;
		}

	}
	cout << ans << endl;
}

E Losing Nim

Output the number of solutions whose sum is $N$ divided into $K$ piles, and the XOR is $0$. Each pile is at least $1$, $K$ from $1$ to $N$. $1<N<500$

I wrote a dp of $O(N^4)$. . . Then I saw that all the operations were repeated, but I didn’t know how to optimize it to $O(N^3)$.

ans[i][j][k] represents the number of solutions to the i-th heap, the sum is j, the XOR is k, and then the last heap is enumerated.

TLE.

ll n,p;
ll ans[505][505][520];

void solve()
{
    slla(n),slla(p);
    repp(i,1,n)
    {
        ans[1][i][i]=1;
    }
    cout<<0<<endl;
    repp(i,2,n)
    {
        repp(last,1,n)
        {
            repp(presum,i-1,n)
            {
                if(last+presum>n)
                {
                    break;
                }
                repp(prexor, 0, 512)
                {
                    ans[i][last + presum][last ^ prexor] += ans[i - 1][presum][prexor];
                    ans[i][last + presum][last ^ prexor] %= p;
                }
            }
        }
        printf("%lld\n",ans[i][n][0]);
    }
}

Later, I asked others and found that dp[i][k] can represent the number of options in which the sum of the first i digits is k and the XOR is 0. The inside is transferred through the combination number.

ll n,p;
ll C[505][505];
ll dp[505][505];

void solve()
{
    slla(n),slla(p);
    C[0][0] = 1;
    repp(i,1,n)
    {
        C[i][0]=1;
        repp(j,1,i)
        {
            C[i][j] = C[i-1][j-1] + C[i-1][j];
            C[i][j] %= p;
            //DE(C[i][j])
        }
    }
    repp(i,1,n)
    {
        dp[i][0] = 1;
    }
    ll w = 1;
    while(w <= n)
    {
        repp(i,2,n)
        {
            for(int j=n;j>=0;j--)
            {
               for(int k=1;k<=n;k++)
               {
                   if(!dp[i][j])continue;
                   if(j + 2*k*w <= n && 2*k <= i) {
                       dp[i][j + 2 * k * w] += dp[i][j] * C[i][2 * k] % p;
                       dp[i][j + 2 * k * w] %= p;
                   }
                   else
                   {
                       break;
                   }
               }
            }
        }
        w *= 2;
    }
    repp(i,1,n)
    {
        rep(j,1,i)
        {
            dp[i][n] -= dp[j][n]*C[i][j] % p;
            dp[i][n] = (dp[i][n] % p + p) % p;
        }
        cout<<dp[i][n]<<endl;
    }
}