回文なのでXは前半分だけを考える 後半分は自動的に決まる 前半分が完全にSと同じになるXについて$ X \le Sを満たしているか確認しておく $ dp[i][j][k] で$ i文字目まで見てその文字が$ jで$ Sより真に小さいかどうかの場合の数 0文字目については$ dp[0][S_0][0] = 1 , $ dp[0][i(i \lt S_0)][1] = 1 $ i文字目については…