2.递推与递归

1.递归实现指数型枚举

//利用二进制来进行状态的描述#include
#include
#includeusing namespace std;int n;void dfs(int u,int status)
{if(u>n){for(int i=1;i<=n;i++){if(status>>i&1)cout<>n;dfs(1,0);
}

2.递归实现组合型枚举

#include 
#include 
#include using namespace std;int n, m;void dfs(int u, int s, int state)
{if (s > m){for (int i = 1; i <= n; i ++ )if (state >> i & 1)cout << i  << ' ';cout << endl;return;}if (u>n) return;for (int i = u; i <=n; i ++ ){dfs(i + 1, s + 1, state + (1 << i));}
}int main()
{cin >> n >> m;dfs(1, 1, 0);return 0;
}

3.递归实现排列型枚举

#include
#include
#includeusing namespace std;const int N=10;int n;
int path[N];
bool st[N];void dfs(int u)
{if(u>n)//说明此时将一种情况的全排列找到{for(int i=1;i<=n;i++)cout<>n;dfs(1);return 0;
}

4.费解的开关

#include 
#include 
#include 
#include using namespace std;const int N=10;char g[N][N];
int dx[] = {-1, 0, 1, 0, 0}, dy[] = {0, 1, 0, -1, 0};void turn(int x,int y)
{for(int i=0;i<5;i++)//如果当前位置x,y需要改变灯，则，上下左右也会发生变换。{int newX=x+dx[i],newY=y+dy[i];if(newX<5&&newY<5&&newX>=0&&newY>=0)//如果满足边界条件g[newX][newY]^=1;//通过异或方式来改变灯的变换}
}void solve()
{int res=INT_MAX;//枚举第一行的灯的所有情况for(int k=0;k<1<<5;k++){int curRes=0;char tmp[N][N];//保存当前的结果memcpy(tmp,g,sizeof g);for(int i=0;i<5;i++){if(k>>i&1) {curRes++;turn(0,i);}}//第一行的状态已确定如果存在0的情况下，那么只能从第二行开始for(int i=0;i<4;i++)for(int j=0;j<5;j++)if(g[i][j]=='0'){curRes++;turn(i+1,j);}bool dark=false;//通过判断最后一行的灯情况如果没有出现0则说明变换成功for(int i=0;i<5;i++)if(g[4][i]=='0'){dark=true;break;}if(!dark) res=min(res,curRes);memcpy(g,tmp,sizeof g);}if(res>6) cout<<"-1"<>T;while(T--){for(int i=0;i<5;i++) cin>>g[i];solve();}return 0;
}

5.奇怪的汉诺塔

#include 
#include 
#include using namespace std;const int N=15;int d[N],f[N];int main()
{d[1]=1;for(int i=2;i<=12;i++)d[i]=1+d[i-1]*2;//首先考虑三个汉诺塔问题，可以推出该递推公式memset(f,0x3f,sizeof f);f[0]=0;for(int i=1;i<=12;i++){for(int j=0;j

#include 
#include 
#include using namespace std;const int mod=9901;int qmi(int a,int b)
{a%=mod;int res=1%mod;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}
//(1+pk2)∗sum(p,k2)
int sum(int p,int k)
{if(k==0) return 1;if (k % 2 == 0) return (p % mod * sum(p, k - 1) % mod + 1) % mod;return sum(p, k / 2) % mod * (1 + qmi(p, k / 2 + 1)) % mod;
}int main()
{int A,B;cin>>A>>B;int res=1;for(int i=2;i<=A;i++){int s=0;while(A%i==0){s++;A/=i;}if(s) res=res*sum(i,s*B)%mod;}if(!A) puts("0");else cout<