uva 10795 新汉诺塔问题【思维】

证明过程书上给的很详细了

说几个易错点

1、求2^(k-1) 时，可以使用快速幂，可以直接暴力，可以用 （1<<(k-1)） 但要注意，会超出int 范围，所以这里要用 1LL
2、在我们分解只要找到最大的不在位置上的数。然后往下递归就可以了。递归的过程中就可以将其中的算好

#include <bits/stdc++.h>
#define cl(a) memset(a,0,sizeof(a))
#define sc(x) scanf("%d",&x)
#define pf(x) printf("%d\n",x)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define fi first
#define se second
using namespace std;
const int mod=1e9+7;
typedef long long ll;
const int maxn=1e5+50;
const int inf=0x3f3f3f3f;
typedef pair <int,int> PII;
ll fpow(ll n,ll k,ll p =mod){ll r=1;for(;k;k>>=1){if(k&1)r=r*n%p;n=n*n%p;}return r;}
ll inv(ll n, ll p=mod) {return fpow(n,p-2,p);}
ll fact[maxn];
void init(){fact[0]=1;for(int i=1;i<maxn;i++)fact[i]=fact[i-1]*i%mod;}
ll C(ll n,ll m,ll p){ll r = fact[n]; r = r * inv(fact[m])%p; r = r*inv(fact[n-m])%p;return r;}
int n;
int st[105],ed[105];
ll ans=0;
ll dfs(int a[],int k,int p)
{
    ll re=0;
    if(k==0) return 0;
    if(a[k]==p) return re=dfs(a,k-1,p);
    else
    {
        re=dfs(a,k-1,6-p-a[k])+(1ll<<(k-1));
        return re;
    }
}
int main()
{
    int kase =0;
    while(cin>>n&&n)
    {
        ans=0;
        rep(i,1,n) cin>>st[i];
        rep(i,1,n) cin>>ed[i];
        per(i,n,1) {if(st[i]!=ed[i]) {
            ans=dfs(st,i-1,6-st[i]-ed[i])+dfs(ed,i-1,6-st[i]-ed[i])+1;
            break;
        }}
        cout<<"Case "<<++kase<<": "<<ans<<endl;
    }
    return 0;
}