[NOI2007]生成树计数环形版

时间：2023-03-10 04:37:43
[NOI2007]生成树计数环形版

NOI2007这道题人类进化更完全之后出现了新的做法

毕姥爷题解：

[NOI2007]生成树计数环形版

于是毕姥爷出了一道环形版的这题（test0814），让我们写这个做法

环形的情况下，k=5的时候是162阶递推。

求这个递推可以用BM算法

一个很好的介绍BM算法的博客

 //Achen

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<vector>

 #include<cstdio>

 #include<queue>

 #include<cmath>

 #include<set>

 #include<map>

 #define Formylove return 0

 #define For(i,a,b) for(int i=(a);i<=(b);i++)

 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)

 const int p=;

 typedef long long LL;

 typedef double db;

 using namespace std;

 int k;

 template<typename T>void read(T &x)  {

     char ch=getchar(); x=; T f=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 LL a[][];

 LL solve(int n) {

     LL rs=,f=;

     For(i,,n) For(j,,n) a[i][j]=(a[i][j]+p)%p;

     For(i,,n) {

         For(j,i+,n) {

             LL A=a[i][i],B=a[j][i],t;

             while(B) {

                 t=A/B;

                 For(k,i,n) a[i][k]=(a[i][k]-t*a[j][k]%p+p)%p;

                 For(k,i,n) swap(a[i][k],a[j][k]);

                 A%=B; swap(A,B); f=-f;

             }

         }

         rs=rs*a[i][i]%p;

     }

     if(f==-) rs=p-rs;

     return rs;

 }

 #define ANS

 int main() {

 #ifdef ANS

     //freopen("shanghai.in","r",stdin);

     freopen("biao.out","w",stdout);

 #endif

     read(k);

     //printf("%d\n",500-2*k);

     int tot=;

     For(n,*k+,) {

         tot++;

         For(i,,n) For(j,i+,n) if(min(abs(i-j),n-abs(i-j))<=k) {

             a[i][i]++;

             a[j][j]++;

             a[i][j]--;

             a[j][i]--;

         }

         LL rs=solve(n-);

         printf("%lld,",rs);

         For(i,,n) For(j,,n) a[i][j]=;

         if(tot==) break;

     }

     Formylove;

 }

暴力程序(矩阵树定理)

对于每个k用上面这个暴力打表，再用下面这个模板得出递推（ps,BM算法n越大越精确，当k=5,n只取到200时会得出90多阶的递推而不是162阶）

 //Achen

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<vector>

 #include<cstdio>

 #include<queue>

 #include<cmath>

 #include<set>

 #include<map>

 #define Formylove return 0

 #define For(i,a,b) for(int i=(a);i<=(b);i++)

 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)

 const int N=,p=;

 typedef long long LL;

 typedef double db;

 using namespace std;

 int n,cnt,fail[N];

 vector<LL>f[N];

 LL a[N],delta[N];

 template<typename T>void read(T &x)  {

     char ch=getchar(); x=; T f=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 LL ksm(LL a,LL b) {

     LL rs=,bs=a%p;

     while(b) {

         if(b&) rs=rs*bs%p;

         bs=bs*bs%p;

         b>>=;

     }

     return rs;

 }

 #define ANS

 int main() {

 #ifdef ANS

     freopen("biao.out","r",stdin);

     freopen("k4.out","w",stdout);

 #endif

     read(n);

     For(i,,n) read(a[i]);

     For(i,,n) {

         LL tp=;

         int up=f[cnt].size();

         For(j,,up-)

             tp=(tp+f[cnt][j]*a[i-j-]%p)%p;

         if(tp==a[i]) continue;

         delta[i]=(a[i]-tp+p)%p;

         fail[cnt]=i;

         ++cnt;

         if(cnt==) {

             f[cnt].resize(i);

             continue;

         }

         LL mul=delta[i]*ksm(delta[fail[cnt-]],p-)%p,fmul=(p-mul)%p;

         f[cnt].resize(i-fail[cnt-]-);

         f[cnt].push_back(mul);

         up=f[cnt-].size();

         For(j,,up-)

             f[cnt].push_back(fmul*f[cnt-][j]%p);

         up=f[cnt-].size();

         if(f[cnt].size()<f[cnt-].size()) f[cnt].resize(up);

         For(j,,up-) f[cnt][j]=(f[cnt][j]+f[cnt-][j])%p;

     }

     int up=f[cnt].size();

     printf("%d\n",up);

     For(i,,up-) printf("%lld,",f[cnt][i]);

     Formylove;

 }

模意义下BM模板

把打出来的表直接放程序里，暴力递推就有80了。

 //Achen

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<vector>

 #include<cstdio>

 #include<queue>

 #include<cmath>

 #include<set>

 #include<map>

 #define Formylove return 0

 #define For(i,a,b) for(int i=(a);i<=(b);i++)

 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)

 const int p=;

 typedef long long LL;

 typedef double db;

 using namespace std;

 int len[]={,,,,,};

 LL f[][]={{},{,,},{,,,,,,},{,,,,,,,,,,,,,,,,,,},{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,},{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,}};

 LL a[][]={{},{,,},{,,,,,,},{,,,,,,,,,,,,,,,,,,},{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,},{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,}};

 LL b[],n,k;

 template<typename T>void read(T &x)  {

     char ch=getchar(); x=; T f=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 #define ANS

 int main() {

 #ifdef ANS

     freopen("shanghai.in","r",stdin);

     freopen("shanghai.out","w",stdout);

 #endif

     read(k); read(n);

     For(i,,len[k]) b[i+*k]=a[k][i];

     For(i,len[k]+*k+,n) {

         For(j,,len[k]) b[i]=(b[i]+f[k][j]*b[i-j]%p)%p;

     }

     printf("%lld\n",b[n]);

     Formylove;

 }

 /*

 */

80pt

矩乘优化好像跑不过，得多项式取模优化才行。。。

多项式取模优化k阶常系数线性递推

时间复杂度k^2logn

 //Achen

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<vector>

 #include<cstdio>

 #include<queue>

 #include<cmath>

 #include<set>

 #include<map>

 #define Formylove return 0

 #define For(i,a,b) for(int i=(a);i<=(b);i++)

 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)

 const int p=;

 typedef long long LL;

 typedef double db;

 using namespace std;

 int len[]={,,,,,};

 LL f[][]={{},{,,},{,,,,,,},{,,,,,,,,,,,,,,,,,,},{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,},{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,}};

 LL a[][]={{},{,,},{,,,,,,},{,,,,,,,,,,,,,,,,,,},{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,},{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,}};

 LL b[],n,k;

 template<typename T>void read(T &x)  {

     char ch=getchar(); x=; T f=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 LL rs[],bs[];

 void mul(LL a[],LL b[],LL c[]) {

     static LL tp[];

     int up=(len[k]<<);

     For(i,,up) tp[i]=;

     For(i,,len[k]-) For(j,,len[k]-)

         (tp[i+j]+=a[i]*b[j]%p)%=p;

     Rep(i,up,len[k]) For(j,,len[k])

         (tp[i-j]+=f[k][j]*tp[i]%p)%=p;

     For(i,,up) c[i]=tp[i];

 }

 void ksm(LL b) {

     while(b) {

         if(b&) mul(rs,bs,rs);

         mul(bs,bs,bs);

         b>>=;

     }

 }

 #define ANS

 int main() {

 #ifdef ANS

     freopen("shanghai.in","r",stdin);

     freopen("shanghai.out","w",stdout);

 #endif

     read(k); read(n);

     n-=*k;

     For(i,,len[k]) b[i]=a[k][i];

     if(n<=len[k]) printf("%lld\n",b[n]);

     else {

         rs[]=; bs[]=;

         ksm(n-);

         LL ans=;

         For(i,,len[k]-) (ans+=b[i+]*rs[i]%p)%=p;

         printf("%lld\n",ans);

     }

     Formylove;

 }

100pt

相关文章