zcmimi's blog

查看原题

点击跳转

这题考场上可能打表稳一点

n/m 1 2 3 4 5 6 7 8
1 2 4 8 16 32 64 128 256
2 4 12 36 108 324 972 2916 8748
3 8 36 112 336 1008 3024 9072 27216
4 16 108 336 912 2688 8064 24192 72576
5 32 324 1008 2688 7136 21312 63936 191808
6 64 972 3024 8064 21312 56768 170112 510336
7 128 2916 9072 24192 63936 170112 453504 1360128
8 256 8748 27216 72576 191808 510336 1360128 3626752

不妨设n<m(不难发现表格是对称的)

不难发现:

  1. n=1时,ans(n,m)=2^m
  2. n>1,m>n+1时,ans(n,m)=ans(n,m-1)\times 3

打表+快速幂就完事了

#include<bits/stdc++.h>
const int P=1000000007;
int n,m,
    a[10]={0,2,12,112,912,7136,56768,453504,3626752},
    b[10]={0,4,36,336,2688,21312,170112,1360128,10879488};
int pw(int x,int b){
    int res=1;
    for(;b;b>>=1,x=1ll*x*x%P)
        if(b&1)res=1ll*res*x%P;
    return res;
}
int main(){
    scanf("%d%d",&n,&m);
    if(n>m)std::swap(n,m);
    if(n==1)printf("%d\n",pw(2,m));
    else if(n==m)printf("%d\n",a[n]);
    else printf("%d\n",1ll*b[n]*pw(3,m-n-1)%P);
}
LG 5023 填数游戏
comment评论
Search
search