P5023

Aryper · 2021-10-17 13:42:03 · 个人记录

[NOIP2018 提高组] 填数游戏

打表找规律题？？？

先弃了。

二进制数存路径，分别存从某个点出发得到的最大值和最小值，如果向下走的最大值大于向右走的最小值就说明不合法。

优化过后每枚举完一行就判断一下剪枝。

这样暴力打出打表，大眼观察规律。

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

1. 若 n=1 则 f(n,m)=2^m。

2. 若 n=m 则可以表内查找。

3. 若 n\le m+1 则 f(n,m)=f(n,n+1)\times 3^{m-n-1}。

代码：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll mo=1e9+7;

ll n,m;

ll a[10][10];

ll pow(ll x,ll p) {
    ll ans=1;
    while(p>0) {
        if(p&1) ans=(ans*x)%mo;
        x=(x*x)%mo;p>>=1;
    }
    return ans;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

void init() {
    a[1][1]=2;a[1][2]=4;
    a[2][2]=12;a[2][3]=36;
    a[3][3]=112;a[3][4]=336;
    a[4][4]=912;a[4][5]=2688;
    a[5][5]=7136;a[5][6]=21312;
    a[6][6]=56768;a[6][7]=170112;
    a[7][7]=453504;a[7][8]=1360128;
    a[8][8]=3626752;a[8][9]=10879488;
}

int main() {

    n=read();m=read();

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

    init();

    if(n==1) write(pow(2,m));
    else
    if(n==m) write(a[n][m]);
    else write(a[n][n+1]*pow(3,m-n-1)%mo);

    return 0;
}