E. 인수열

9712 단어 DFS

E. 인수열


사고방식: 귀속, 관건은 귀속의 순서와 실현 과정이다. 분명히 순서대로 찾을 수 있다. 만약에 현재 이미 검색을 했다면 이와 유사한 제법 검색이 거꾸로 있다.매번 뒤질 때마다 뒤져봤는지 바꿔봐.
컨베이어 도어
#include
using namespace std;
typedef long long ll;
const int N=20,M=65,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair
#define fi first
#define se second
#define pb push_back
ll f[N][M];
int p[N],k[N],n;
bool vis[N]; 
void dfs(int id,ll x){
	if(id==n+1){
		printf("%lld
"
,x); return; } if(!vis[id]){ for(int i=0;i<=k[id];i++) dfs(id+1,x*f[id][i]); } else { for(int i=k[id];i>=0;i--) dfs(id+1,x*f[id][i]); } vis[id]^=1; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d%d",&p[i],&k[i]); f[i][0]=1; for(int j=1;j<=k[i];j++) f[i][j]=f[i][j-1]*p[i]; } dfs(1,1); return 0; }

좋은 웹페이지 즐겨찾기