noip模拟9 达哥随单题

T1.随

　　看题第一眼，就瞄到最下面孙金宁教你学数学？？？？？原根？目测神题，果断跳过。

　最后打了个快速幂，愉快的收到了达哥送来的10分。

　　实际上这题暴力不难想，看到一个非常小的mod应该就能想到复杂度与mod有关，然后dp式子也挺显然的。

　　比较神的是最后的优化，我们用 f[i][j]表示经过i次操作，最终%mod后与原根的j次方同余的方案数，然后，之前的转移

　　f[i][j*k%mod]=f[i-1][j]*sum[k](sum[k]为k在n个数中出现的次数) 就变成了f[ i ] [ ( j + k ) % ( mod-1 ) ]=f[i-1][j]*sum[k];

　　那么这有什么卵用呢，原来的转移矩阵变成了循环矩阵，于是乎就可以mod^2乘一次。

　　另外，对于这道题，原根没有必要O（mod^1/4）求，mod^2暴力就行。。。

　　总复杂度O（mod^2logm）.

　　数据差评，没有80分算法

 #include<bits/stdc++.h>

 #define p 1000000007

 using namespace std;

 int n,m,mod,a,sum[],yuan,ys[],yx[];

 long long b[][],aa[],c[],d[];

 bool v[];

 inline void cheng()

 {

     for(int i=;i<mod;i++)

     {

         d[i]=;

         for(int j=;j<mod;j++)

             d[i]=(d[i]+aa[j]*b[j][i])%p;

     }

     for(int i=;i<mod;i++)

         aa[i]=d[i];

 }

 inline void z()

 {

     for(int i=;i<mod;i++)

     {

         c[i]=;

         for(int j=;j<mod;j++)

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

     }

     for(int i=;i<mod;i++)

         b[][i]=c[i];

     for(int i=;i<mod;i++)

         for(int j=;j<mod;j++)

             b[i][j]=b[i-][(j==)?mod-:j-];

 }

 inline long long qpow(long long x,long long y)

 {

     long long ans=;

     while(y)

     {

         if(y&)ans=ans*x%p;

         x=x*x%p;

         y>>=;

     }

     return ans;

 }

 int main()

 {

     scanf("%d%d%d",&n,&m,&mod);

     for(int i=;i<mod;i++)

     {

         memset(v,,sizeof(v));

         long long k=;

         bool kkk=;

         for(int j=;j<mod;j++)

         {

             if(v[(k*i)%mod])

             {

                 kkk=;

                 break;

             }

             k=(k*i)%mod,v[k]=true;

         }

         if(!kkk)

         {

             yuan=i;

             break;

         }

     }

     for(int i=,j=yuan;i<mod;i++,j=j*yuan%mod)

         ys[j]=i,yx[i]=j;

     for(int i=;i<=n;i++)

         scanf("%d",&a),sum[ys[a]]++;

     for(int i=;i<mod;i++)

         for(int j=;j<mod;j++)

             b[i][(i+j-)%(mod-)+]+=sum[j];

     aa[mod-]=;

     long long bb=qpow(n,m),aaa=;

     while(m)

     {

         if(m&) cheng();

         z();

         m>>=;

     }

     for(int i=;i<mod;i++)

         (aaa+=yx[i]*aa[i])%=p;

     cout<<aaa*qpow(bb,p-)%p;

     return ;

 }

T2.单

　　这也是一道很帅的题，首先对于t=0的操作，令sum为所有节点的权值之和，我们首先进行暴力求出b[1]的值，然后对于其他节点，我们可以进行换根：

　　b[x]=b[fa]-siz[x]+(sum-siz[x]);这个式子比较显然。于是30分到手。

　　对于t=1的操作，我们把上面那个式子变一下就可以得到2*siz[x]=b[fa]-b[x]+sum。也就是说，我们只要求出sum的值，就可以求出所有的a。

　　考试的时候就死在了这里，发现不会求sum，不同与其他人的高斯消元，我采取了一种更为sha diao的做法：枚举sum值，代进去看能不能成立。。。。。由于题中有a[i]<=100的限制，所以sum不会很大，理论上有60分，但是不知道为啥死掉了。

　　实际上，有一个隐藏的条件：d[1]=∑siz[i] (2<=i<=n)，然后我们将上面那个式子x=2到x=n的情况全都写下来相加，将前面这个式子×2，再将这两部分相减，我们就会惊喜的发现：

　　sum=(∑d[fa]-d[x]-d[1]*2)/(n-1);

　　于是我们就可以愉快的ac了。

 #include<bits/stdc++.h>

 #define int long long

 using namespace std;

 int t,n,fi[],ne[],to[],tot,a[],b[],sum,siz[],de[];

 bool o;

 inline void add(int x,int y)

 {

     ne[++tot]=fi[x];

     to[tot]=y;

     fi[x]=tot;

 }

 void dfs1(int x,int fa)

 {

     siz[x]=a[x];b[]+=(de[x]-)*a[x];

     for(int i=fi[x];i;i=ne[i])

     {

         int y=to[i];

         if(y!=fa)

         {

             de[y]=de[x]+;

             dfs1(y,x);

             siz[x]+=siz[y];

         }

     }

 }

 void dfs2(int x,int fa)

 {

     b[x]=b[fa]-siz[x]+sum-siz[x];

     for(int i=fi[x];i;i=ne[i])

     {

         int y=to[i];

         if(y!=fa)

         {

             dfs2(y,x);

         }

     }

 }

 void dfs3(int x,int fa)

 {

     siz[x]=(b[fa]-b[x]+sum)>>;a[x]=siz[x];

     for(int i=fi[x];i;i=ne[i])

     {

         int y=to[i];

         if(y!=fa)

         {

             dfs3(y,x);

             a[x]-=siz[y];

         }

     }

 }

 void gsm(int x,int fa)

 {

     for(int i=fi[x];i;i=ne[i])

     {

         int y=to[i];

         if(y!=fa)

         {

             sum+=b[x]-b[y];

             gsm(y,x);

         }

     }

 }

 main()

 {

     scanf("%lld",&t);

     while(t--)

     {

         tot=sum=;

         memset(fi,,sizeof(fi));

         memset(b,,sizeof(b));

         memset(a,,sizeof(a));

         memset(siz,,sizeof(siz));

         memset(de,,sizeof(de));

         scanf("%lld",&n);

         for(int i=,x,y;i<n;i++)

         {

             scanf("%lld%lld",&x,&y);

             add(x,y),add(y,x);

         }

         cin>>o;

         if(o)

         {

             for(int i=;i<=n;i++)

                 scanf("%lld",&b[i]);

             gsm(,);

             sum=(b[]*-sum)/(n-);

             siz[]=sum;

             for(int i=fi[];i;i=ne[i])

             {

                 dfs3(to[i],);

                 siz[]-=siz[to[i]];

             }

             a[]=siz[];

             for(int i=;i<=n;i++)

                 printf("%lld ",a[i]);

             puts("");

         }

         else

         {

             for(int i=;i<=n;i++)

                 scanf("%lld",&a[i]),sum+=a[i];

             de[]=;

             dfs1(,);

             for(int i=fi[];i;i=ne[i])

             {

                 int y=to[i];

                 dfs2(y,);

             }

             for(int i=;i<=n;i++)

                 printf("%lld ",b[i]);

             puts("");

         }

     }

     return ;

 }

T3.题

　　送分题，但我没有全部接到。。

　　对于opt=0，ans=C(n,n/2)^2;

　　对于opt=1，ans=catalan(n);

　　对于opt=2，dp即可

　　对于opt=3，枚举一个方向走的步数，ans=∑catalan(i)*catalan((n-i-i)/2)*C(n,i+i);

　　另外，求大神解释我曾经的visit题解（那两个组合数怎么解释啊）

 #include<bits/stdc++.h>

 #define mod 1000000007

 using namespace std;

 int n,k;

 long long js[],ni[],f[][][];

 inline long long qpow(long long x,long long y)

 {

     long long ans=;

     while(y)

     {

         if(y&)ans=ans*x%mod;

         x=x*x%mod;

         y>>=;

     }

     return ans;

 }

 inline long long c(long long x,long long y)

 {

     return js[x]*ni[x-y]%mod*ni[y]%mod;

 }

 int main()

 {

     scanf("%d%d",&n,&k);

     js[]=ni[]=;

     for(int i=;i<=n+n;i++)

         js[i]=js[i-]*i%mod,ni[i]=qpow(js[i],mod-);

     if(k==)

     {

         printf("%lld\n",c(n,n/)*c(n,n/)%mod);

         return ;

     }

     if(k==)

     {

         printf("%lld\n",c(n,n/)*qpow(n/+,mod-)%mod);

         return ;

     }

     if(k==)

     {

         f[][][]=;

         for(int i=;i<=n;i++)

         {

             f[i&][][]=(f[(i-)&][][]+f[(i-)&][][]+f[(i-)&][][]+f[(i-)&][][])%mod;

             for(int j=-n;j<=+n;j++)

                 if(j!=)

                     f[i&][][j]=(f[(i-)&][][j-]+f[(i-)&][][j+])%mod;

             for(int j=-n;j<=+n;j++)

                 if(j!=)

                     f[i&][j][]=(f[(i-)&][j-][]+f[(i-)&][j+][])%mod;

         }

         cout<<f[n&][][]<<endl;

         return ;

     }

     if(k==)

     {

         long long ans=;

         for(int i=;i<=n/;i++)

             ans=(ans+c(n,i+i)*c(i+i,i)%mod*qpow(i+,mod-)%mod*c(n-i-i,(n-i-i)/)%mod*qpow((n-i-i)/+,mod-))%mod;

         cout<<ans;

     }

     return ;

 }

巴特西

noip模拟9 达哥随单题

最新文章

热门文章