Help to Understand A solution to 1515E Phoenix and Computers

Правка en2, от hello99acres, 2021-09-11 16:30:27

Hello Codeforces, I was trying to understand this problem 1515E - Phoenix and Computers , I've read the editorial and understood it. But then I found this solution :114947787 by Marcus0510 which I've copied here for convenience:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,b,a) for(i=b;i>=a;i--)
#define ll long long
#define db double
using namespace std;

const int maxn=505;

ll f[maxn][maxn],ans;
int i,j,k,n,md;

int main(){
	scanf("%d%d",&n,&md);
	f[1][1]=1;
	fo(i,1,n){
		fo(j,1,i){
			f[i+1][j]=(f[i+1][j]+f[i][j]*j*2)%md;
			f[i+2][j+1]=(f[i+2][j+1]+f[i][j]*(j+1))%md;
			if (i==n) ans=(ans+f[i][j])%md;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

which is much smaller than the editorial and I wasn't able to understand what the author has done here, except that it uses D.P. and the variable 'i' represents if there were i computers in the question and thus we do a sum over all j from 1 to n where i = n in the end. So please help me understand what's being done here and what is the significance of the variable j?

Теги #combinatorics, #dp

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский hello99acres 2021-09-11 16:31:38 5 Tiny change: ' the end. So please help' -> ' the end. Please help'
en2 Английский hello99acres 2021-09-11 16:30:27 31
en1 Английский hello99acres 2021-09-11 16:29:12 1298 Initial revision (published)