P11152 七彩序列 题解

隔壁泞2的如心 · 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);
}