zcmimi's blog

arrow_back打表共1篇文章

avatar
zc
2020-10-21 10:05:27

查看原题

点击跳转

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

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

打表+快速幂就完事了

1/1
Search
search