51nod Problem Notes II (1048, 1167)

The previous entry was from 2017; surprisingly, more than a year has passed before this second 51nod note. 51nod seems to have made a major change only recently—there used to be far too many bugs.

I have been through a lot this year, yet made very little progress. Sometimes my mindset needs adjusting too.

51nod 1048

Let $g[i][le][ri]$ denote the number of ways to represent $2^i$ using $2^{le}$ through $2^{ri}$. Then

$g[i][le][ri] = \sum_{k=le}^{ri}g[i-1][le][k] * g[i-1][k][ri]$

Then observe that $g[i][le][ri] = g[i-k][le-k][ri-k]$, so one dimension can be removed:

$g[i][j] = \sum_{k=0}^{j}g[i-1][k] * g[i-1-k][j-k]$

Similarly, $f[i][j]$ denotes the number of possibilities whose largest value is $2^j$ after processing the first $i$ ones:

$f[i][j] = \sum_{k=0}^{j}f[i-1][k] * g[i-k][j-k]$

One complaint: why is modular arithmetic not allowed here? I had to use arbitrary-precision Java integers and still optimise the constants.

import java.util.Scanner;
import java.io.*;
import java.math.*;
import java.math.BigInteger;

public class Main
{
    public static void main(String[] args)
    {
        Scanner cin = new Scanner(System.in);
        BigInteger N = cin.nextBigInteger();
        BigInteger f[][] = new BigInteger[155][155];
        BigInteger g[][] = new BigInteger[155][155];
        
        for (int i=0;i<=120;i++) {
            for (int j=0;j<=120;j++) {
                f[i][j] = BigInteger.ZERO; 
                g[i][j] = BigInteger.ZERO; 
            }
        }
        f[0][0] = BigInteger.ONE;

        for (int i=1;i<=120;i++) {
            f[i][i] = BigInteger.ONE;
            for (int j=0;j<i;j++) {
                for (int k=0;k<=j;k++) {
                    f[i][j] = f[i][j].add(f[i-1][k].multiply(f[i-1-k][j-k]));
                }
            }
        }
        BigInteger Two = BigInteger.ONE.add(BigInteger.ONE);
        int tot = 0;
        for (int i=0;i<=120;i++) {
            if (N.mod(Two).toString().charAt(0) == '1') {
                tot++;
                if(tot==1) {
                    for (int j=0;j<=i;j++) {
                        g[1][j] = f[i][j];
                    }
                } else {
                    for (int j=0;j<=i;j++) {
                        for(int k=0;k<=j;k++) {
                            g[tot][j] = g[tot][j].add(g[tot-1][k].multiply(f[i-k][j-k]));
                        }
                    }
                }
            }
            N=N.divide(Two);
        }
        BigInteger ans=BigInteger.ZERO;

        for (int i=0;i<=120;i++) {
            ans = ans.add(g[tot][i]);
        }
         System.out.println(ans.toString());
    }
}

51nod 1167

This is an enhanced version of 1048. Instead of binary digits, every position has $k$ possibilities. In practice, the final DP stage needs $k$ additional merges.

import java.util.Scanner;
import java.io.*;
import java.math.*;
import java.math.BigInteger;

public class Main
{
    public static void main(String[] args)
    {
        Scanner cin = new Scanner(System.in);
        BigInteger tmp1 = cin.nextBigInteger();
        String tm = tmp1.toString();
        int K =Integer.valueOf(tm);
        BigInteger N = cin.nextBigInteger();
        BigInteger f[][] = new BigInteger[155][155];
        BigInteger g[][] = new BigInteger[155][155];
        BigInteger h[][] = new BigInteger[155][155];
        int maxn = 50;
        for (int i=0;i<=maxn;i++) {
            for (int j=0;j<=maxn;j++) {
                f[i][j] = BigInteger.ZERO;
                g[i][j] = BigInteger.ZERO;
            }
        }
        f[0][0] = BigInteger.ONE;

        for (int i=1;i<=maxn;i++) {
            for(int j=0;j<=maxn;j++) {
                for(int k=0;k<=maxn;k++) {
                    g[j][k] = BigInteger.ZERO;
                }
            }
            for(int j=0;j<=i-1;j++) {
                g[1][j] = f[i-1][j];
            }
            for(int j=2;j<=K;j++) {
                for(int k=0;k<i;k++) {
                    for(int x=0;x<=k;x++) {
                        g[j][k] = g[j][k].add(g[j-1][x].multiply(f[i-1-x][k-x]));
                    }
                }
            }

            for(int j=0;j<i;j++) {
                f[i][j] = g[K][j];
            }
            f[i][i]=BigInteger.ONE;
        }
        int tot = 0;
        int wz = 0;
        g[0][0] = BigInteger.ONE;
        for (int i=0;i<=maxn;i++) {
            String tmp = N.mod(tmp1).toString();
            int s =Integer.valueOf(tmp);
    
            for(int x=0;x<=maxn;x++) {
                for (int j=0;j<=maxn;j++) {
                     h[x][j] = BigInteger.ZERO;
                }
            }
            for(int j=0;j<=i;j++) h[0][j]=g[i][j];
            for(int x=1;x<=s;x++) {
                for (int j=0;j<=i;j++) {
                    h[x][j] = BigInteger.ZERO;
                    for (int k=0;k<=j;k++) {
                        h[x][j]=h[x][j].add(h[x-1][k].multiply(f[i-k][j-k]));
                    }
                }
            }
             for(int x=0;x<=maxn;x++) {
                for (int j=0;j<=maxn;j++) {
                     g[x][j] = BigInteger.ZERO;
                }
            }
            for (int j=0;j<=i;j++) g[i+1][j]=h[s][j];
            N=N.divide(tmp1);
            if(N.equals(BigInteger.ZERO)) {
                wz=i+1;
                break;
            }
        }

        BigInteger ans=BigInteger.ZERO;
        for (int i=0;i<=maxn;i++) {
            ans = ans.add(g[wz][i]);
        }
        System.out.println(ans.toString());
    }
}