「UR #8」宿命多项式

十月 04, 2020 · OI 题解

给定 $n$ 和 $c_{0\ldots n}$，表示限制形如对于 $0 \leq i \leq n$ 都满足 $1 \leq f(i) \leq c_i$。

其中 $f(x) = \sum_{i=0}^{n} a_i x^i$，其中 $a_{0 \ldots n}$ 都是整数，即 $f(x)$ 是一个不超过 $n$ 次的整系数多项式。

问满足限制的 $f(x)$ 有多少个，答案对 $998244353$ 取模。

题解

考虑把 $1 \leq f(i) \leq c_i$ 的限制转换为 $0 \leq f(i) < c_i$，且将 $f(x)$ 转化为下降幂多项式。注意到这些转化不会影响到答案。

我们令 $a_i = x_i (n-i)! + y_i$，考虑枚举 $y_i$ 后怎么计算答案。

我们提出其中一项式子：

$0 \leq a_0 + k a_1 + k^{\underline 2}a_2 + k^{\underline 3} a_3 + \cdots + k! a_k < c_k$

把前半部分设为 $d_k$，则有：

$0 \leq d_k + k!a_k < c_k$

代入 $a_k = x_k (n-k)! + y_k$ 得：

$0 \leq d_k + k!(x_k (n-k)! + y_k) < c_k$

其中 $y_k$ 是我们已经枚举的整数，故只需要考虑对 $x_k$ 计数即可。

$-d_k - k! y_k \leq k!(n-k)! x_k < c_k - d_k - k! y_k$

答案显然是在 $\frac {c_k} {k!(n-k)!}$ 的级别，但是会有 $\pm 1$ 的偏差，取决于不等式两边在模意义下的大小，具体地（令 $C=d_k+ k!y_k ,\ M = k!(n-k)!$）：

$\operatorname{count}(x_k)= \begin{cases} \lfloor \frac {c_k} {M} \rfloor & (C \bmod M \leq c_k + C \bmod M) \\ \lfloor \frac {c_k} {M} \rfloor +1 & (C \bmod M > c_k + C \bmod M) \\ \end{cases}$

我们现在考察 $C\bmod M$ 的关系，$k!y_k$ 的贡献是已知常数，考虑：

$d_k = \sum_{i=0}^{k-1} a_i k^{\underline i} = \sum_{i=0}^{k-1} (x_i(n-i)! + y_i) k^{\underline i}$

注意到 $(n-i)!k^{\underline i}$ 是 $M$ 的倍数，故 $C \bmod M$ 只和 $y_{0 \ldots k}$ 有关。

可以通过枚举 $y_{0 \ldots n}$ 后计算，时间复杂度 $O(n \times n! \times (n-1)! \times \cdots \times 1!)$。

虽然理论上来说是不能过的但是可以通过巨大多常数优化草过去，实际表现还是跑的挺快的。（竟然比以小常数著名的 zx2003 学长快！）

代码

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma,tune=native") 
#include<bits/stdc++.h>

namespace mem{ //v1.8.5 => size: 13.21KiB
  #define MEM_IO
  #define MEM_STR
  #define MEM_MATH
  #define MEM_UTILS
  #define MEM_MODINT
  #define MEM_RANDOM
  #define MEM_STDVAL
  #define MEM_CONTAINER
  #ifdef memset0
  #else
    #define MEM_FASTIO
  #endif

  #ifdef __SIZEOF_INT128__
    #define MEM_INT128
  #endif

  #define __integer_mapper(func)     \
      func(int)                      \
      func(unsigned int)             \
      func(long long)                \
      func(unsigned long long)
  #define __float_mapper(func)       \
      func(float)                    \
      func(double)
  #define __string_mapper(func) \
      func(char *)              \
      func(string &)            \
      func(std::string &)
  #define __string_join_mapper(func)                                              \
      func(vector<string>,string)                                                 \
      func(std::vector<string>,string)                                            \
      template<class T> func(vector<T>,to_string)                                 \
      template<class T> func(std::vector<T>,to_string)

  #ifdef MEM_STDVAL
    namespace stdval{
      using i32=int;
      using i64=long long;
      using u32=unsigned int;
      using u64=unsigned long long;
      using f32=float;
      using f64=double;
  #ifdef MEM_INT128
      using i128=__int128_t;
      using u128=__uint128_t;
  #endif
    }
  #endif

  #ifdef MEM_UTILS
    namespace utils{
      using std::cin;
      using std::tie;
      using std::cout;
      using std::cerr;
      using std::endl;
      using std::swap;
      using std::sort;
      using std::unique;
      using std::reverse;
      using std::shuffle;
      using std::function;
      using std::make_pair;
      using std::make_tuple;
      using std::lower_bound;
      using std::upper_bound;
      using std::max_element;
      using std::min_element;
    }
  #endif

  #ifdef MEM_IO
    namespace io{
  #ifdef MEM_FASTIO
      namespace fastio{
        const int BUFFER=1<<21;
        char ibuf[BUFFER],*iS,*iT;
        inline int getc(){
          if(iS==iT){
            iT=(iS=ibuf)+fread(ibuf,1,BUFFER,stdin);
            return iS==iT?EOF:*iS++;
          }else{
            return *iS++;
          }
        }
        char obuf[BUFFER],*oS=obuf,*oT=oS+BUFFER-1;
        inline void flush(){
          fwrite(obuf,1,oS-obuf,stdout);
          oS=obuf;
        }
        inline void putc(int x){
          *oS++=x;
          if(oS==oT)flush();
        }
        struct Flusher{~Flusher(){flush();}}flusher;
      }
      using fastio::getc;
      using fastio::putc;
  #else
      inline int getc(){return getchar();}
      inline void putc(int c){putchar(c);}
  #endif
      
      template<class T> inline void readDigit(T &x){
        x=getc();
        while(!isdigit(x))x=getc();
      }
      inline int readDigit(){
        int x;
        readDigit(x);
        return x;
      }
      template<class T> inline void readAlpha(T &x){
        x=getc();
        while(!isalpha(x))x=getc();
      }
      inline int readAlpha(){
        int x;
        readAlpha(x);
        return x;
      }
      template<class T> inline void readInt(T &x){
        x=0;
        bool f=0;
        char c=getc();
        while(!isdigit(c))f^=c=='-',c=getc();
        while(isdigit(c))x=x*10+c-'0',c=getc();
        if(f)x=-x;
      }

  #define __read(T)                             \
      inline void read(T &x) {                  \
        x=0; bool f=0; char c=getc();           \
        while(!isdigit(c))f^=c=='-',c=getc();   \
        while(isdigit(c))x=x*10+c-'0',c=getc(); \
        if(f)x=-x;                              \
      }
      __integer_mapper(__read)
  #undef __read
      
      inline void read(char &x){x=getc();}
      template<class T=int> inline T read(){
        T x;
        read(x);
        return x;
      }
      template<class T,class... Args> inline void read(T &x,Args &... args){
        read(x),read(args...);
      }

  #define __print(T)           \
      inline void print(T x){  \
        if(x<0)putc('-'),x=-x; \
        if(x>9)print(x/10);    \
        putc('0'+x%10);        \
      }
      __integer_mapper(__print)
  #undef __print
      
      inline void print(char x){putc(x);}
      inline void print(const char *s){
        int len=strlen(s);
        for(int i=0;i<len;i++)putc(s[i]);
      }
      inline void print(const std::string &s){
        for(int i=0;i<s.length();i++)putc(s[i]);
      }
      
      template<class T,class... Args> inline void print(const T &x,Args... args){
        print(x),print(args...);
      }
      template<class... Args> inline void println(Args... args){
        print(args...),putc('\n');
      }
    }
  #endif

  #ifdef MEM_RANDOM
    namespace random{
      const int LuckyNumber=20040725;
      std::mt19937 rng(LuckyNumber^std::chrono::steady_clock::now().time_since_epoch().count());
      std::mt19937_64 rng64(LuckyNumber^std::chrono::steady_clock::now().time_since_epoch().count());
      
      template<class T> inline T rand(T l,T r){return std::uniform_int_distribution<T>(l,r)(rng);}
      template<class T> inline T rand64(T l,T r){return std::uniform_int_distribution<T>(l,r)(rng);}
    }
  #endif

  #ifdef MEM_MODINT
    namespace modint{
      template<const int mod> struct Z{
        int x;
        inline Z(){x=0;}
        inline Z(int t){x=t;}
        
        inline void operator-=(Z a){(x-=a.x)<0&&(x+=mod);}
        inline void operator+=(Z a){(x+=a.x)>=mod&&(x-=mod);}
        inline void operator*=(Z a){x=(long long)x*a.x%mod;}
        
        friend inline Z operator*(Z a,Z b){return (long long)a.x*b.x%mod;}
        friend inline Z operator-(Z a,Z b){return ((a.x-=b.x)<0&&(a.x+=mod)),a;}
        friend inline Z operator+(Z a,Z b){return ((a.x+=b.x)>=mod&&(a.x-=mod)),a;}
      };
      
      template<const int mod> inline Z<mod> finv(Z<mod> x){
        if(x.x<2)return x;
        return (mod-mod/x.x)*finv(mod%x.x);
      }
      template<const int mod> inline Z<mod> fpow(Z<mod> a,int b){
        Z <mod> s=1;
        for(;b;b>>=1,a=a*a)
          if(b&1)s=s*a;
        return s;
      }
      
      template<const int mod> inline void init_inverse(int n,Z<mod> *inv){
        inv[0]=inv[1]=1;
        for(int i=2;i<n;i++)inv[i]=(mod-mod/i)*inv[mod%i];
      }
      template<const int mod> inline void init_factorial(int n,Z<mod> *fac,Z<mod> *ifac){
        fac[0]=1,init_inverse(n,ifac);
        for(int i=1;i<n;i++)fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*ifac[i];
      }
    }
  #endif

  #ifdef MEM_MATH
    namespace math{
      using std::max;
      using std::min;
      template<class T> inline T abs(T x){return x<0?-x:x;}
      template<class T> inline T gcd(T n,T m){return m?gcd(m,n%m):n;}
      template<class T> inline T lcm(T n,T m){return n/gcd(n,m)*m;}
      
      template<const stdval::u64 p> struct FastDiv{
        stdval::u64 t,i;
        inline FastDiv():t(stdval::u64(-1)/p),i(mul_inv(p)){}
        
        inline bool divide(stdval::u64 n){return n*i<=t;}
        inline bool divide(stdval::i64 n){return stdval::u64(n<0?-n:n)*i<=t;}
        inline stdval::u64 mul_inv(stdval::u64 n){
          stdval::u64 x=n;
          for(int i=0;i<5;++i)x*=2-n*x;
          return x;
        }
      };

  #ifdef MEM_INT128
      template<const stdval::u64 b> struct FastMod{
        stdval::u64 m;
        inline FastMod():m(stdval::u64((stdval::u128(1)<<64)/b)){}
        
        inline stdval::u64 reduce(stdval::u64 a){
          stdval::u64 q=(stdval::u64)((stdval::u128(m)*a)>>64);
          stdval::u64 r=a-q*b;
          return r>=b?r-b:r;
        }
      };
  #endif
    }
  #endif

  #ifdef MEM_CONTAINER
    namespace container{
      using std::pair;
      using std::tuple;
      using std::set;
      using std::unordered_set;
      using std::map;
      using std::unordered_map;

      using std::tie;
      using std::make_pair;
      using std::make_tuple;

      template<class T> struct vector:std::vector<T>{
        using std::vector<T>::vector;
        vector():std::vector<T>(){}
        vector(const std::vector<T> &plain):std::vector<T>(plain){}
        
        inline void read(int s=-1){
          if(~s)this->resize(s);
          for(size_t i=0;i<this->size();i++){
            io::read(this->operator[](i));
          }
        }
        inline void print(char pt0=' ',char pt1='\n'){
          for(size_t i=0;i<this->size();i++){
            io::print(this->operator[](i));
            if(i+1<this->size())io::putc(pt0);
          }
          io::putc(pt1);
        }
        
        inline void sort(){std::sort(this->begin(),this->end());}
        inline void concat(const vector &rhs){this->insert(this->end(),rhs.begin(),rhs.end());}
        inline bool includes(const T &x) const{return std::find(this->begin(),this->end(),x)!=this->end();}
        
        inline vector slice(int l,int r) const{
          if(l>r)return {};
          if(r<this->size())return vector(this->begin()+l,this->begin()+r);
          vector<int> rsp=(this->begin()+l,this->end());
          return rsp.resize(r-l),rsp;
        }
        
        inline void from(const std::set<T> &src){
          this->resize(src.size());
          auto it=this->begin();
          for(const T e:src)*it++=e;
        }
        
        template<class Function> inline void forEach(Function func){for(const auto &it:*this)func(it);}
        
        template<class R,class Function> inline vector<R> _map(Function func) const{
          vector <R> res(this->size());
          for(size_t i=0;i<this->size();i++)
            res[i]=func(this->operator[](i));
          return res;
        }
        template<class R> inline vector<R> map(R func(T)) const{return this->_map<R>(func);}
        template<class R> inline vector<R> map(const std::function<R(T)> &func) const{return this->_map<R>(func);}
      };
    }
  #endif

  #ifdef MEM_STR
    namespace str {
      using namespace mem::container;

      struct string:std::string{
        using std::string::string;
        string():std::string(""){}
        string(const std::string &plain):std::string(plain){}

  #define __join_declaration(Vector,_)            \
        inline string join(const Vector &) const;
        __string_join_mapper(__join_declaration)
  #undef __join_declaration
        
        vector<string> split(const string &delim)const{
          if(this->empty())return {};
          char *src=new char[this->length()+1];
          strcpy(src,this->c_str());
          char *tar=new char[delim.length()+1];
          strcpy(tar,delim.c_str());
          vector<string> rsp;
          for(char *pos=strtok(src,tar);pos;pos=strtok(nullptr,tar))
            rsp.push_back(string(pos));
          delete[] src;
          delete[] tar;
          return rsp;
        }
        
        template<class... Args> static inline string format(const char *fm,Args... args){
          int len=snprintf(nullptr,0,fm,args...);
          char *buf=new char[len+1];
          snprintf(buf,len+1,fm,args...);
          string str(buf);
          delete[] buf;
          return str;
        }
        template<class... Args> static inline string format(const string &fm,Args... args){
          return format(fm.c_str(),args...);
        }
      };

  #define __to_string(T)                   \
      inline string to_string(const T &x){ \
        return std::to_string(x);          \
      }
      __float_mapper(__to_string)
      __integer_mapper(__to_string)
  #undef __to_string
      template<class T> inline string to_string(const vector<T> &vet){return "{"+string(",").join(vet)+"}";}
      template<class T> inline string to_string(const std::vector<T> &vet){return to_string(vector<T>(vet.begin(),vet.end()));}
      template<const int mod> inline string to_string(const mem::modint::Z<mod> &zval){return std::to_string(zval.x);}

  #define __join_instantiation(Vector,to_string)          \
      inline string string::join(const Vector &vet)const{ \
        if(!vet.size())return "";                         \
        string res=to_string(vet[0]);                     \
        for(size_t i=1;i<vet.size();i++){                 \
          res+=*this;                                     \
          res+=to_string(vet[i]);                         \
        }                                                 \
        return res;                                       \
      }
      __string_join_mapper(__join_instantiation)
  #undef __join_instantiation
      
      inline void print(const str::string &s){
        for(size_t i=0;i<s.length();i++)mem::io::putc(s[i]);
      }

  #define __printfm(T)                                                      \
      template<class... Args> inline void printfm(const T fm,Args... args){ \
        print(str::string().format(fm,args...));                            \
      }
      __string_mapper(__printfm)
  #undef __printfm
    }
  #endif

  #undef __integer_mapper
  #undef __float_mapper
  #undef __string_mapper
  #undef __string_join_mapper

  #ifdef MEM_IO
    using namespace io;
  #endif
  #ifdef MEM_STR
    using namespace str;
  #endif
  #ifdef MEM_MATH
    using namespace math;
  #endif
  #ifdef MEM_UTILS
    using namespace utils;
  #endif
  #ifdef MEM_MODINT
    using namespace modint;
  #endif
  #ifdef MEM_RANDOM
    using namespace random;
  #endif
  #ifdef MEM_STDVAL
    using namespace stdval;
  #endif
  #ifdef MEM_CONTAINER
    using namespace container;
  #endif
} // namespace mem

const int N=10,F=10000,mod=998244353;
const int fac[N]={1,1,2,6,24,120,720,5040,40320,362880};
const int ifac[N]={1,1,499122177,166374059,291154603,856826403,641926577,376916469,421456191,712324701};
const int down[N][N]={
  {1,0,0,0,0,0,0,0,0,0},
  {1,1,0,0,0,0,0,0,0,0},
  {1,2,2,0,0,0,0,0,0,0},
  {1,3,6,6,0,0,0,0,0,0},
  {1,4,12,24,24,0,0,0,0,0},
  {1,5,20,60,120,120,0,0,0,0},
  {1,6,30,120,360,720,720,0,0,0},
  {1,7,42,210,840,2520,5040,5040,0,0},
  {1,8,56,336,1680,6720,20160,40320,40320,0},
  {1,9,72,504,3024,15120,60480,181440,362880,362880}
};
using z=mem::Z<mod>;
using namespace mem::io;
using namespace mem::modint;

int n,q,c[N],d[N],y[N],fit[N][F];
z ans,cur[1<<7];

void dfs(int u){
  if(u>n){
    int x=0;
    for(int i=0;i<=n;i++){
      x|=fit[i][d[i]]<<i;
    }
    ans+=cur[x];
    return;
  }
  for(int i=0;i<fac[n-u];i++){
    y[u]=i;
    for(int i=u;i<=n;i++)d[i]+=y[u]*down[i][u];
    dfs(u+1);
    for(int i=u;i<=n;i++)d[i]-=y[u]*down[i][u];
  }
}

void mainVI(){
  y[5]=y[6]=0;
  for(y[0]=0;y[0]<fac[6];y[0]++){
    for(int i=0;i<=6;i++)d[i]+=y[0];
    for(y[1]=0;y[1]<fac[5];y[1]++){
      for(int i=1;i<=6;i++)d[i]+=y[1]*down[i][1];
      for(y[2]=0;y[2]<fac[4];y[2]++){
        for(int i=2;i<=6;i++)d[i]+=y[2]*down[i][2];
        for(y[3]=0;y[3]<fac[3];y[3]++){
          for(int i=3;i<=6;i++)d[i]+=y[3]*down[i][3];
          for(y[4]=0;y[4]<fac[2];y[4]++){
            for(int i=4;i<=6;i++)d[i]+=y[4]*down[i][4];
            int x=0;
            for(int i=0;i<=6;i++)x|=fit[i][d[i]]<<i;
            ans+=cur[x];
            for(int i=4;i<=6;i++)d[i]-=y[4]*down[i][4];
          }
          for(int i=3;i<=6;i++)d[i]-=y[3]*down[i][3];
        }
        for(int i=2;i<=6;i++)d[i]-=y[2]*down[i][2];
      }
      for(int i=1;i<=6;i++)d[i]-=y[1]*down[i][1];
    }
    for(int i=0;i<=6;i++)d[i]-=y[0];
  }
}

int main(){
#ifdef memset0
  freopen("1.in","r",stdin);
#endif
  for(read(q);q-->0;ans=0){
    read(n);
    for(int i=0;i<=n;i++)read(c[i]);
    for(int i=0;i<=n;i++)
      for(int d=0;d<F;d++){
        fit[i][d]=(c[i]+d)%(fac[i]*fac[n-i])<d%(fac[i]*fac[n-i]);
      }
    for(int x=0;x<(1<<(n+1));x++){
      cur[x]=1;
      for(int i=0;i<=n;i++)
        if((x>>i)&1){
          cur[x]*=c[i]/(fac[i]*fac[n-i])+1;
        }else{
          cur[x]*=c[i]/(fac[i]*fac[n-i]);
        }
    }
    if(n==6)mainVI();
    else dfs(0);
    print((int&)ans,'\n');
  }
}