【洛谷5456】[THUPC2018] 蛋糕（搜索）

点此看题面

大致题意： 把一个\(a\times b\times c\times d\)的\(4\)维图形划分成\(a\times b\times c\times d\)个小块，求有\(0\sim8\)个面暴露在表层的块数各为多少。

搜索

这道题乍一看无比神仙，对于我这种数学差、想象力匮乏的蒟蒻真是连样例都理解不了。

不过，其实只要好好去钻研一下\(3\)维图形，就可以推出\(4\)维图形的答案。

考虑在一般情况下，对于\(4\)维图形的每一维，当且仅当选择了这一维的第一行或者最后一行，才会多一个面暴露在表层。

但是，如果出现了某种特殊情况，即某一维总共只有一行，我们就可以发现，这会导致暴露在表层的面数加\(2\)。

因此，我们只要写个搜索，然后特判行数为\(1\)的情况，即可过此题了。

最后，吐槽一下诡异的模数。

代码

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define X 2148473648
#define LL long long
#define Inc(x,y) ((x+=(y))>=X&&(x-=X))
using namespace std;
int a[5];LL v[9];
I void dfs(CI x,Con LL& p,CI t)//搜索
{
    if(x==5) return (void)Inc(v[t],p);if(a[x]==1) return dfs(x+1,p,t+2);//统计答案；特判行数为1
    dfs(x+1,(a[x]-2)*p%X,t),dfs(x+1,2*p%X,t+1);//分两种情况继续搜索
}
int main()
{
    RI Tt;scanf("%d",&Tt);W(Tt--) scanf("%d%d%d%d",a+1,a+2,a+3,a+4),dfs(1,1,0),
        printf("%lld %lld %lld %lld %lld %lld %lld %lld %lld\n",v[0],v[1],v[2],v[3],v[4],v[5],v[6],v[7],v[8]),
        v[0]=v[1]=v[2]=v[3]=v[4]=v[5]=v[6]=v[7]=v[8]=0;return 0;//注意清空
}