動的計画法を行います
dp[l][r]=s[l…r]dp[l][r]=s[l…r]dp[l][r]=s[l…r]に限定した時の全分割に対する積の総和
と定義するとこれはO(N3)O(N^3)O(N3)で求められます
答えは明らかにdp[0][n−1]2n−1\frac{dp[0][n-1]}{2^{n-1}}2n−1dp[0][n−1]です
