WA了第2二点求调,悬2关
查看原帖
WA了第2二点求调,悬2关
507374
sqrtqwq楼主2024/6/8 19:46
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int P = 299987;
int n,m;
int ex,ey,now,lst;
__int128 ans;
int a[105][105];
int head[300000],nxt[300005],cnt[2];
__int128 que[2][300005],val[2][300005],inc[15];
void insert(__int128 bit,__int128 num)
{
    int u = bit % P + 1;
    for(int i = head[u];i;i = nxt[i])
    {
        if(que[now][i] == bit)
        {
            val[now][i] += num;
            return;
        }
    }
    nxt[++cnt[now]] = head[u];
    head[u] = cnt[now];
    que[now][cnt[now]] = bit;
    val[now][cnt[now]] = num;
}

void write(__int128 x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9)
	{
		write(x/10);
	}
	putchar(x%10+'0');
}


signed main()
{
    cin >> m >> n;
    if(n == 1 && m == 1)
    {
        cout << 1;
        return 0;
    }
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            a[i][j] = 1;
			ex = i;
			ey = j;
        }
    }
    inc[0] = 1;
	for(int i = 1;i <= 13;i++)
	{
       inc[i] = inc[i - 1] << 2;
	}
    cnt[now] = 1;
    val[now][1] = 1;
    que[now][1] = 0;
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= cnt[now];j++)
        {
            que[now][j] <<= 2;
        }
        for(int j = 1;j <= m;j++)
        {
            memset(head,0,sizeof(head));
        	lst = now;
            now ^= 1;
           	cnt[now] = 0;
            for(int k = 1;k <= cnt[lst];k++)
            {
                __int128 bit = que[lst][k],num = val[lst][k];
                __int128 b1 = (bit >> ((j - 1) << 1)) % 4;
                __int128 b2 = (bit >> (j << 1)) % 4;
                if(!a[i][j])
			   	{
                   if(!b1 && !b2) insert(bit,num);
               	}
                else if(!b1 && !b2)
                {
                    if(a[i + 1][j] && a[i][j + 1])insert(bit + inc[j - 1] + inc[j] * 2,num);
                }
                else if(!b1 && b2)
                {
                    if(a[i][j + 1])insert(bit,num);
                   	if(a[i + 1][j])insert(bit - inc[j] * b2 + inc[j - 1] * b2,num);
                }
                else if(b1 && !b2)
                {
                    if(a[i + 1][j])insert(bit,num);
                   	if(a[i][j + 1])insert(bit - inc[j - 1] * b1 + inc[j] * b1,num);
                }
                else if(b1 == 1 && b2 == 1)
                {
                    int flag = 1;
                   	for(int l = j + 1;l <= m;l++)
					{
                       	if((bit >> (l << 1)) % 4 == 1)flag++;
                       	if((bit >> (l << 1)) % 4 == 2)flag--;
                       	if(!flag)
						{
                           	insert(bit - inc[j] - inc[j - 1] - inc[l],num);
                           	break;
                       	}
                   	}
                }
                else if(b1 == 2 && b2 == 2)
                {
                    int flag = 1;
                   	for(int l = j - 2;l > 0;l--)
					{
                       	if((bit >> (l << 1)) % 4 == 1)flag--;
                       	if((bit >> (l << 1)) % 4 == 2)flag++;
                       	if(!flag)
						{
                           	insert(bit - inc[j] * 2 - inc[j - 1] * 2 + inc[l],num);
                           	break;
                       	}
                   	}
                }
                else if(b1 == 2 && b2 == 1) insert(bit - inc[j - 1] * 2 - inc[j],num);
				else if(i == ex && j == ey) ans += num;
            }
        }
    }
    write(ans);
    return 0;
}

2024/6/8 19:46
加载中...