自动搬运

查看原文

来自洛谷，原作者为

	隔壁泞2的如心 AFO|以某种事物作为代价，以某种代价作为契机……？

搬运于2025-08-24 23:04:42，当前版本为作者最后更新于2024-10-24 22:50:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑 $n=3$ 的情况，那么问题可以被转化为从长方体的一个顶点移动到对面的顶点，并且有两条不能在非顶点处触碰的直线。钦定走到的不合法点集合，相邻两个不合法点之间的走法一共只有 $O(m)$ 种。$n$ 更大时实际上也没有区别。把这些方案数算出来需要 $O(nm)$ 的时间复杂度，然后再用多项式求逆合并就可以。

要注意本题其实并没有所有 $a_i$ 均相等从而答案为 $0$ 的数据，所以不用讨论这个（

代码写得很难看……

//省略多项式板子
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",l+i);
    sort(l+1,l+1+n);m=l[1];
    assert(l[1]==l[n]);
    default_shrink=m+1;
    poly p_upper,p_lower,p,ans;
    for(int i=1;i<=m;i++){
        int siz=0;mi cur=1;
        for(int j=1;j<=n;j++){
            siz+=i;cur=cur*rfac[i];
        }
        p[i]=-cur*fac[siz];
    }
    for(int i=0;i<=m;i++){
        int siz=0;mi cur=1;
        for(int j=1;j<=n;j++){
            siz+=l[j]-m+i;cur=cur*rfac[l[j]-m+i];
        }
        p_upper[i]=-cur*fac[siz];
    }
    for(int i=0;i<=m;i++){
        int siz=0;mi cur=1;
        for(int j=n;j>=1;j--){
            if(i-l[j]+m<0){cur=0;break;}
            siz+=i-l[j]+m;cur=cur*rfac[i-l[j]+m];
        }
        p_lower[i]=-cur*fac[siz];
    }
    poly p1;p1[0]=1;
    p_upper=p_upper*ginv(p1-p);
    p_lower=p_lower*ginv(p1-p);
    poly p_conclusion=p_upper*p_lower;
    ans=ginv(p1-p)*p_upper*ginv(p1-p_conclusion);
    printf("%d",(-(ans[m])).w);
}