首页 > 代码库 > 特征多项式优化线性递推

特征多项式优化线性递推

#include <cstdio>
#define EXint __uint128_t
 
  EXint n,k,p,tmp[3001],ans;
 
  inline EXint READ(){
    char ch=getchar();EXint ret=0;
    while (ch<0||ch>9) ch=getchar();
    while (ch>=0&&ch<=9){ret*=10;ret+=ch-0;ch=getchar();}
    return(ret);
  }
    
  inline void WRITE(EXint a){
    int cnt=0,typ[101];
    while (a) typ[++cnt]=a%10,a/=10;
    for (int i=cnt;i>=1;i--) putchar(typ[i]+0);
  }
 
  struct poly{
    EXint a[3001];
     
    void mul(poly&b){
      for (int i=0;i<=2*k-2;i++) tmp[i]=0;
      for (int i=0;i<=k-1;i++)
        for (int j=0;j<=k-1;j++)
          tmp[i+j]+=a[i]*b.a[j];

    //对特征多项式取模
for (int i=2*k-2;i>=k;i--){ tmp[i-k]+=tmp[i];tmp[i-k+1]+=tmp[i]; } for (int i=k-1;i>=0;i--) a[i]=tmp[i]; } }bas,res; int main(){ n=READ();k=READ();p=READ(); bas.a[1]=1;res.a[0]=1; while (n){ if (n&(EXint)1) res.mul(bas); bas.mul(bas); n=n>>1; } for (int i=0;i<k;i++) ans=ans+res.a[i];//若0-k-1的初始值不为1则乘权值 if (p!=128) ans&=((((EXint)1)<<p)-1); WRITE(ans); }

 

特征多项式优化线性递推