Code
This submission is logically correct, but purposefully ignores modulo operations so that you can focus on the logic.
#include <bits/stdc++.h>
using namespace std;
int mod;
void solve(int n) {
vector<vector<vector<int>>> dp(
n + 2, vector<vector<int>>(n + 3, vector<int>(3, 0)));
// dp[i][j][k] is the number of ways to delete j edges from the i-th prefix
// such that the resulting graph contains k connected components.
// Here, we are only utilizing k = 1 and k = 2.
// It is implicitly assumed that in case of 2 connected components, the top
// and bottom vertex of the i-th prefix are part of different connected
// components.
// For n = 1, if the vertical edge is removed, we have 2 connected comp.
dp[1][1][2] = 1;
// If it is not removed, we have 1 connected component.
dp[1][0][1] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= n; j++) {
// Case 1 : The current graph has 1 connected component.
// The next graph can either retain this connected component.
// by not deleting any incoming edge, or delete exactly one of
// the incoming edge.
dp[i + 1][j][1] += dp[i][j][1];
dp[i + 1][j + 1][1] += 3 * dp[i][j][1];
// Or, the next graph can split it into two connected components.
// For this to be possible, the incoming vertical edge needs to be
// deleted, along with exactly one of the top or bottom edge.
dp[i + 1][j + 2][2] += 2 * dp[i][j][1];
// Case 2 : The current graph has 2 connected components.
// The next graph can either retain these 2 connected components
// by removing the vertical edge.
dp[i + 1][j + 1][2] += dp[i][j][2];
// Or, the next graph can merge it back into a single connected
// component by not deleting any incoming edges.
dp[i + 1][j][1] += dp[i][j][2];
}
}
for (int i = 1; i < n; i++) {
cout << dp[n][i][1] << " ";
}
cout << endl;
}
int main() {
int n;
cin >> n >> mod;
solve(n);
}#include <bits/stdc++.h>
using namespace std;
int mod;
void inc(int &a, int b) {
a += b;
a %= mod;
}
int mult(int a, int b) {
long long res = 1LL * a * b;
res %= mod;
return res;
}
void solve(int n) {
vector<vector<vector<int>>> dp(
n + 2, vector<vector<int>>(n + 3, vector<int>(3, 0)));
// dp[i][j][k] is the number of ways to delete j edges from the i-th prefix
// such that the resulting graph contains k connected components.
// Here, we are only utilizing k = 1 and k = 2.
// It is implicitly assumed that in case of 2 connected components, the top
// and bottom vertex of the i-th prefix are part of different connected
// components.
// For n = 1, if the vertical edge is removed, we have 2 connected comp.
dp[1][1][2] = 1;
// If it is not removed, we have 1 connected component.
dp[1][0][1] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= n; j++) {
// Case 1 : The current graph has 1 connected component.
// The next graph can either retain this connected component.
// by not deleting any incoming edge, or delete exactly one of
// the incoming edge.
inc(dp[i + 1][j][1], dp[i][j][1]);
inc(dp[i + 1][j + 1][1], mult(3, dp[i][j][1]));
// Or, the next graph can split it into two connected components.
// For this to be possible, the incoming vertical edge needs to be
// deleted, along with exactly one of the top or bottom edge.
inc(dp[i + 1][j + 2][2], mult(2, dp[i][j][1]));
// Case 2 : The current graph has 2 connected components.
// The next graph can either retain these 2 connected components
// by removing the vertical edge.
inc(dp[i + 1][j + 1][2], dp[i][j][2]);
// Or, the next graph can merge it back into a single connected
// component by not deleting any incoming edges.
inc(dp[i + 1][j][1], dp[i][j][2]);
}
}
for (int i = 1; i < n; i++) {
cout << dp[n][i][1] << " ";
}
cout << endl;
}
int main() {
int n;
cin >> n >> mod;
solve(n);
}This submission is logically correct, but purposefully ignores modulo operations so that you can focus on the logic.
#include <bits/stdc++.h>
using namespace std;
int mod;
void solve(int n) {
vector<vector<vector<int>>> dp(
n + 1, vector<vector<int>>(n + 1, vector<int>(3, 0)));
// dp[i][j][k] is the number of ways to delete j edges from the i-th prefix
// such that the resulting graph contains k connected components.
// Here, we are only utilizing k = 1 and k = 2.
// It is implicitly assumed that in case of 2 connected components, the top
// and bottom vertex of the i-th prefix are part of different connected
// components.
// For n = 1, if the vertical edge is removed, we have 2 connected comp.
dp[1][1][2] = 1;
// If it is not removed, we have 1 connected component.
dp[1][0][1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= n; j++) {
// Case 1 : The previous graph had just 1 connected component.
// You can either keep that connected component by not deleting
// any edge, or deleting atmost one edge.
dp[i][j][1] += dp[i - 1][j][1];
if (j - 1 >= 0) {
dp[i][j][1] += 3 * dp[i - 1][j - 1][1];
}
// Or, you can break it into 2 by deleting exactly two edges.
// Note that one of these edge has to be the vertical edge, else
// the previous connected components can never be joined again.
if (j - 2 >= 0) {
dp[i][j][2] += 2 * dp[i - 1][j - 2][1];
}
// Case 2 : The previous graph had 2 connected components.
// You can either keep that connected component by removing the
// vertical edge.
if (j - 1 >= 0) {
dp[i][j][2] += dp[i - 1][j - 1][2];
}
// Or, you can join it back to a single connnected component by not
// removing any edge now.
dp[i][j][1] += dp[i - 1][j][2];
}
}
for (int i = 1; i < n; i++) {
cout << dp[n][i][1] << " ";
}
cout << endl;
}
int main() {
int n;
cin >> n >> mod;
solve(n);
}#include <bits/stdc++.h>
using namespace std;
int mod;
void inc(int &a, int b) {
a += b;
a %= mod;
}
int mult(int a, int b) {
long long res = 1LL * a * b;
res %= mod;
return res;
}
void solve(int n) {
vector<vector<vector<int>>> dp(
n + 1, vector<vector<int>>(n + 1, vector<int>(3, 0)));
// dp[i][j][k] is the number of ways to delete j edges from the i-th prefix
// such that the resulting graph contains k connected components.
// Here, we are only utilizing k = 1 and k = 2.
// It is implicitly assumed that in case of 2 connected components, the top
// and bottom vertex of the i-th prefix are part of different connected
// components.
// For n = 1, if the vertical edge is removed, we have 2 connected comp.
dp[1][1][2] = 1;
// If it is not removed, we have 1 connected component.
dp[1][0][1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= n; j++) {
// Case 1 : The previous graph had just 1 connected component.
// You can either keep that connected component by not deleting
// any edge, or deleting atmost one edge.
inc(dp[i][j][1], dp[i - 1][j][1]);
if (j - 1 >= 0) {
inc(dp[i][j][1], mult(3, dp[i - 1][j - 1][1]));
}
// Or, you can break it into 2 by deleting exactly two edges.
// Note that one of these edge has to be the vertical edge, else
// the previous connected components can never be joined again.
if (j - 2 >= 0) {
inc(dp[i][j][2], mult(2, dp[i - 1][j - 2][1]));
}
// Case 2 : The previous graph had 2 connected components.
// You can either keep that connected component by removing the
// vertical edge.
if (j - 1 >= 0) {
inc(dp[i][j][2], dp[i - 1][j - 1][2]);
}
// Or, you can join it back to a single connnected component by not
// removing any edge now.
inc(dp[i][j][1], dp[i - 1][j][2]);
}
}
for (int i = 1; i < n; i++) {
cout << dp[n][i][1] << " ";
}
cout << endl;
}
int main() {
int n;
cin >> n >> mod;
solve(n);
}