题目：

可以用分治FFT。但自己只写了多项式求逆。

和COGS2259几乎很像。设A(x)，指数是长度，系数是方案。 \( A(x)^{k} \) 的 m 次项系数表示 k 个连续段组成长度为 m 的序列的方案数。

\( B(x)=1+F(x)+F^{2}(x)+F^{3}(x)+... \)

\( B(x) = \frac{1}{1-F(x)} \)（通过计算B(x)的逆来看出这个式子）

然后多项式求逆就行了。

注意模数 \( 313=2^{3}*3*13 \) ，原根是10，但那个 2³ 太小了！如果 len 大于3的话就会除出小数，所以不能直接用NTT！

那么就用FFT。FFT不能中途取模，所以最大的值是 312×312×10000=9734400000，会让FFT的精度变得很低。所以用拆系数FFT。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define db double#define ll long longusing namespace std;const int N=1e5+5,M=(1<<18)+5,mod=313;const db pi=acos(-1);int n,a[M],b[M],tp[M],len,r[M],base;struct cpl{db x,y;}A[M],B[M],Ta[M],Tb[M],Tc[M],Td[M],Ini,I;cpl operator+ (cpl a,cpl b){
   return (cpl){a.x+b.x,a.y+b.y};}cpl operator- (cpl a,cpl b){
   return (cpl){a.x-b.x,a.y-b.y};}cpl operator* (cpl a,cpl b){
   return (cpl){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}cpl cnj(cpl a){
    return (cpl){a.x,-a.y};}int rdn(){  int ret=0;bool fx=1;char ch=getchar();  while(ch>'9'||ch<'0'){
   if(ch=='-')fx=0;ch=getchar();}  while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();  return fx?ret:-ret;}void upd(int &x){x>=mod?x-=mod:0;}int pw(int x,int k){
    int ret=1;while(k){
   if(k&1)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=1;}return ret;}void fft(cpl *a,bool fx){  for(int i=1;i
          
           >1; cpl wn=(cpl){ cos(pi/m),fx?-sin(pi/m):sin(pi/m) }; for(int i=0;i
           
            >1]>>1)+((i&1)?len>>1:0); for(int i=0;i
            
             >1,a,b); mtt(n,a,b,tp); mtt(n,tp,b,tp); for(int i=0;i
             
              <<1)-tp[i])%mod+mod,upd(b[i]);}int main(){ base=sqrt(mod); I.x=1; while(1) { memset(a,0,sizeof a);memset(b,0,sizeof b); n=rdn(); if(!n)return 0; for(int i=1;i<=n;i++)a[i]=rdn(); for(int i=1;i<=n;i++)a[i]=mod-a[i]%mod,upd(a[i]); a[0]++; getinv(n+1,a,b); printf("%d\n",b[n]); } return 0;}