uoj#120. 【UR #8】宿命多项式 | miaom's Blog
miaom's Blog

lych真的0

miaom's avatar miaom

uoj#120. 【UR #8】宿命多项式

题目大意

$q$组数据,求有多少最高次不高于$n$的整系数多项式,对于任意$0\leq i \leq n$均满足$1\leq f(i) \leq c_i$。

$1\leq n \leq 6,0\leq c_i \leq 10^9,q\leq 10$

题解

感觉这个东西很厉害的样子,不知道能不能出毒瘤题。。

原问题等价于:

求有多少最高次不高于$n$的整系数多项式,对于任意$0\leq i \leq n$均满足$0\leq f(i) < c_i$。

定义一个叫下降幂的东西$x^{\underline{k}}=x(x-1)(x-2)\cdots (x-k+1) \,\,(k\ge 0)$,发现$x^{\underline{k}}=\frac{x!}{(x-k)!}$。

对于满足条件多项式$f(x)=\sum_{i=0}^nc_ix^i$使用下降幂表示为$f(x)=\sum_{i=0}^nq_ix^{\underline{i}}$。

$c_i$均为整数等价于$q_i$均为整数。

我们并不需要求出具体的$x^{\underline{i}}$。

考虑$0\leq f(i)<c_i$,有$f(i)=q_ii^{\underline{i}}+q_{i-1}i^{\underline{i-1}}+\cdots+q_0i^{\underline{0}}$。对答案的贡献与$q_{i-1}i^{\underline{i-1}}+\cdots+q_0i^{\underline{0}}\, mod\, \, i^{\underline{i}}$有关。直接枚举$q_i$没有希望,观察发现对于$k<i$,有$(n-i)!\cdot i^{\underline{i}} | (n-k)!\cdot i^{\underline{k}}$。用$(n-i)!\cdot t_i+r_i$表示$q_i$,dfs枚举$r_i$,对于$i$,对答案的贡献即$t_i$的方案数为

等价于

可以做到$O(n!\cdot (n-1)!\cdots1!\cdot n)$的复杂度。

考虑进一步优化,对于枚举$r_0$的部分,发现存在大量冗余,考虑对于答案相同的一起统计。对于$t_i$,有$2\binom{n}{i}$个$r_0$的关键点,共$2^{n+1}$个,使用计数排序的技巧,可以优化到$O((n-1)!\cdots 1! \cdot 2^{n+1})$。

实现

#include<bits/stdc++.h>
#define ll long long
#define P 998244353
using namespace std;
int n,fac[10],c[10],r[10],u[10][10],val[10],cnt,e[512],s[500005],ly;
struct T
{
    int x,y,z;    
}q[500005];
int v[800],w[500005];
void calc()
{
    memset(v,0,sizeof v);
    for (int i=1;i<=cnt;i++) v[q[i].y]++;
    for (int i=1;i<720;i++) v[i]+=v[i-1];
    for (int i=1;i<=cnt;i++) w[v[q[i].y]--]=i;
    for (int i=1,t;i<=cnt;i++)
    {
        t=w[i];
        e[s[q[t].x]]+=q[t].y;
        s[q[t].x]^=1<<q[t].z;
        e[s[q[t].x]]-=q[t].y;
    }
    for (int i=1;i<=ly;i++)
        e[s[i]]+=fac[n];
    ly=cnt=0;
}
void dfs(int x)
{
    if (!x)
    {
        ly++;s[ly]=0;
        for (int i=0;i<=n;i++)
        {
            int p0=fac[i]*fac[n-i],K=val[i]%p0;
            if (c[i]%p0>K) s[ly]|=1<<i;
            for (int j=0,tmp;j<=fac[n];j+=p0)
            {
                tmp=j-K;
                if (tmp>0&&tmp<fac[n]) q[++cnt]=(T){ly,tmp,i};
                tmp=j-K+c[i]%p0;
                if (tmp>0&&tmp<fac[n]) q[++cnt]=(T){ly,tmp,i};
            }
        }
        if (cnt>400000) calc();
        return;
    }
    int hz[10];
    memcpy(hz,val,sizeof hz);
    for (r[x]=0;r[x]<fac[n-x];r[x]++)
    {
        dfs(x-1);
        for (int i=x;i<=n;i++)
            val[i]+=u[i][x];
    }
    memcpy(val,hz,sizeof val);
}
void work()
{
    scanf("%d",&n);
    for (int i=0;i<=n;i++)
        scanf("%d",&c[i]);
    dfs(n);
    calc();
    int Ans=0;
    for (int i=0;i<(1<<n+1);i++)
    {
        int tmp=1;
        for (int j=0;j<=n;j++)
            tmp=(ll)tmp*(c[j]/(fac[j]*fac[n-j])+(i>>j&1))%P;
        Ans=(Ans+(ll)e[i]*tmp)%P;
        e[i]=0;
    }
    printf("%d\n",(Ans+P)%P);
}
int main()
{
    fac[0]=1;
    for (int i=1;i<=6;i++)
        fac[i]=fac[i-1]*i;
    for (int i=0;i<=6;i++)
    {
        u[i][0]=1;
        for (int j=1;j<=i;j++)
            u[i][j]=u[i][j-1]*(i-j+1);
    }
    int T;
    scanf("%d",&T);
    while(T--) work();
}