问题标题: 今年提高组D2T2

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const long long Ans[9][2]={{0,0},{0,0},{12,36},{112,336},{912,2688},{7136,21312},{56768,170112},{453504,1360128},{3626752,10879488}}; 

const long long M=1000000007;

long long n,m,ans=1;

int main()
{
    int i;

    cin>>n>>m;

    if (n>m)
    {
        swap(n,m);
    }

    if (n==1)
    {
        for (i=30;i>=0;--i)
        {
            ans=ans*ans%M;
            if (m&(1<<i))
            {
                ans=ans*2%M;
            }
        }
        cout<<ans;
    }

    else
    {
        if (m==n)
        {
            cout<<Ans[n][0];
            return 0;
        }
        else if (m==n+1)
        {
            cout<<Ans[n][1];
        }
        else
        {
            for (i=30;i>=0;--i)
            {
                ans=ans*ans%M;
                if ((m-n-1)&(1<<i))
                {
                    ans=ans*3%M;
                }
            }
            cout<<ans*Ans[n][1]%M;
        }
    }

    return 0;
}

求采纳，谢谢！

毛润宇在2018-11-29 20:01:31追加了内容

应该可以，看一下，就算不对，也会给你一些帮助吧

毛润宇在2018-11-29 20:07:38追加了内容

是这个？

#include <cstdio>
#include <cstring>
typedef long long ll;
const int mod = 1e9+7;
inline ll qpow(ll a, int n){
    ll ret(1);
    for(; n; n >>= 1, (a*=a)%=mod){
        if(n&1) (ret*=a)%=mod;
    }
    return ret;
}
int n, m, ans;
inline void solve1(){
    printf("%lld\n", qpow(2ll, m));
}//n=1
inline void solve2(){
    printf("%lld\n", 4ll*qpow(3ll, m-1)%mod);
}//n=2
bool mp[10][10]; int dp[10][10][10][10][2];
bool check(int X1, int Y1, int X2, int Y2, bool same){
    if(dp[X1][Y1][X2][Y2][same] != -1) return dp[X1][Y1][X2][Y2][same];
    int &x = dp[X1][Y1][X2][Y2][same];
    if(X1 > n || Y1 > m || X2 > n || Y2 > m) return x=true;
    if(X1 == n && Y1 == m) return true;
    if(!same && mp[X1][Y1] > mp[X2][Y2]) return x=true;
    if(!same && mp[X1][Y1] < mp[X2][Y2]) return x=false;
    if(same){
        return x=check(X1+1,Y1,X2,Y2+1,0) &&
               check(X1+1,Y1,X2+1,Y2,1) &&
               check(X1,Y1+1,X2,Y2+1,1);
    }
    else{
        return x=check(X1+1,Y1,X2+1,Y2,0) &&
               check(X1+1,Y1,X2,Y2+1,0) &&
               check(X1,Y1+1,X2,Y2+1,0) &&
               check(X1,Y1+1,X2+1,Y2,0);
    }
}
void dfs(int x, int y){
    if(y > m){ dfs(x + 1, 1); return;   }
    if(x > n){ memset(dp, -1, sizeof(dp)); ans += check(1, 1, 1, 1, 1); return; }
    if(x >= 2 && y < m){
        if(!mp[x-1][y+1]){
            mp[x][y] = 0; dfs(x, y + 1);
        }
        mp[x][y] = 1; dfs(x, y + 1);
    }
    else{
        mp[x][y] = 0; dfs(x, y + 1);
        mp[x][y] = 1; dfs(x, y + 1);
    }
}
inline void solve3(){
    dfs(1, 1);
    printf("%d\n", ans);
}
inline void solve4(){
    printf("%lld\n", 112ll*qpow(3,m-3)%mod);
}//n==3
inline void solve5(){
    if(m == 4){
        printf("%lld\n", 912ll);
    }
    else{
        printf("%lld\n", 2688ll*qpow(3,m-5)%mod);
    }
}//n==4
inline void solve6(){
    if(m == 5){
        printf("%lld\n", 7136ll);
    }
    else{
        printf("%lld\n", 21312ll*qpow(3,m-6)%mod);
    }
}//n=5
ll t[10], t1[10];
inline void init(){
    t[4] = 912; ll tmp = 160;
    for(int i(5); i <= 8; ++i, (tmp*=2)%=mod){
        t[i] = t[i-1]*8 - tmp;
        t[i] %= mod;
    }
    tmp = 48;
    for(int i(4); i <= 8; ++i, (tmp*=2)%=mod){
        t1[i] = t[i]*3 - tmp;
        t1[i] %= mod;
    }
}
inline void solve10(){
    if(n == m){
        printf("%lld\n", t[n]);
    }
    else{
        printf("%lld\n", t1[n] * qpow(3, m-n-1) % mod);
    }
}
int main(){
//  freopen("game.in", "r", stdin);
//  freopen("game.out", "w", stdout);
    init();
    scanf("%d%d", &n, &m);
    if(n > m) n ^= m ^= n ^= m;
    if(n == 1){
        solve1();
    }
    else if(n == 2){
        solve2();
    }
    else if(n == 3){
        solve4();
    }
    else{
        solve10();
    }
    return 0;
}