NOIP模拟测试9

时间:2021-12-20 09:11:20

又考崩了咕咕咕。。。

T1:随    好题标记

前置芝士:

原根:质数P的原根g满足1<=rt<P,且rt的1次方,2次方…(P-1)次方在模P意义下可以取遍1到(P-1)的所有整数。
    欧拉定理:对于质数P,1<=x<P的任意x的P-1次方在模P意义下都为1。
    显然,原根的1次方,2次方…(P-2)次方在模P意义下都不为1,只有(P-1)次方在模P意义下为1.这也是一个数成为原根的充分必要条件。
    x^b≡x^(b%φ(p))  (%p)



考虑到这道题的m很大,但状态具有传递性,用倍增算法。

设状态f[i][j]表示选了i波后为原根的j次方的方案总数,另求一个辅助数组g[i][j]表示选择2^i次后为原根的j次方的方案总数,那么dp转移显然:

f[i][(j+k)%(p-1)]=Σf[i-1][j]*g[now][k]  (0<=k,j<mod-1)(可以滚动)

注意这里是p-1!由前置芝士可得(因为表示的是次方嘛)。

求g数组同理:

g[i][(j+k)%(mod-1)]=g[i-1][k]*g[i-1][j](0<=k,j<mod-1)

NOIP模拟测试9NOIP模拟测试9
 1 #include<bits/stdc++.h>
 2 #define int long long
 3 #define ts puts("----------");
 4 using namespace std;  5 const int MOD=1000000007;  6 int g[1005][50],f[2][1005],num[1005],Map[1005],bin[50],To[1005];  7 bitset<1001>s;  8 int qpower(int a,int b){  9     int ans=1; 10     while(b){if(b&1)ans=ans*a%MOD;a=a*a%MOD;b>>=1;} 11     return ans%MOD; 12 } 13 signed main() 14 { 15     int n,m,mod; 16     scanf("%lld%lld%lld",&n,&m,&mod); 17     int t=log(m)/log(2)+1; 18     bin[0]=1; 19     for(int i=1;i<=31;i++)bin[i]=bin[i-1]<<1; 20     for(int i=1;i<mod;i++){ 21  s.reset(); 22         int base=1; 23         for(int j=1;j<mod;j++){ 24             (base*=i)%=mod; 25             s[base]=1; 26  } 27         if(s.count()==mod-1){ 28 // cout<<i<<endl;
29             int base=1; 30             for(int j=1;j<mod;j++) 31                 (base*=i)%=mod,Map[base]=j,To[j]=base; 32             Map[1]=0;To[0]=1; 33             break; 34  } 35  } 36     for(int i=1;i<=n;i++) 37  { 38         int a; 39         scanf("%lld",&a); 40         num[a]++; 41         g[Map[a]][0]++; 42  } 43     for(int i=1;i<=t;i++) 44         for(int j=0;j<mod;j++) 45             for(int k=0;k<mod;k++) 46                 (g[(j+k)%(mod-1)][i]+=g[k][i-1]*g[j][i-1])%=MOD; 47 // for(int i=0;i<=t;i++) 48 // for(int j=0;j<mod;j++) 49 // cout<<j<<' '<<i<<' '<<g[j][i]<<endl;
50     f[1][Map[1]]=1; 51     int now=0; 52     int cur=0; 53     for(int i=t;i>=0;i--){ 54         if(now+bin[i]>m)continue; 55         for(int j=0;j<mod;j++)f[cur][j]=0; 56 // cout<<i<<endl;
57         now+=bin[i]; 58         for(int j=0;j<mod;j++) 59             for(int k=0;k<mod;k++) 60         // cout<<k<<' '<<f[cur^1][k]<<" "<<j<<' '<<i<<' '<<g[j][i]<<endl,
61                 (f[cur][(j+k)%(mod-1)]+=(f[cur^1][k]*g[j][i]))%=MOD;//,cout<<(j+k)%(mod-1)<<' '<<f[cur][(j+k)%(mod-1)]<<endl;
62         if(now==m)break; 63         cur^=1; 64  } 65     int a=0; 66     for(int i=0;i<mod;i++) 67 // cout<<i<<' '<<f[cur][i]<<endl,
68         (a+=To[i]*f[cur][i])%=MOD; 69     int b=qpower(qpower(n,m),MOD-2); 70     cout<<(a*b)%MOD<<endl; 71     return 0; 72 }
n^2的原根


T2:单   好题标记

咕咕咕

这题嘛高斯消元就溜啦,然后获得了10的好成绩,但高斯消元没骗到分。

直接贴代码

注意的点吧:

1.高斯消元不管是不是整数解,一定要开double!

2.整数解向上取整!

3.fabs必须有!

4.sb错误!

总而言之,不要被题里说的保证有整数解蒙蔽了双眼=_=

上正解:

先看一条链的情况:

已知a[i]求b[i]:

考虑每条边的贡献,辣么,b[i]=pr[1]+pr[2]+pr[3]+......+pr[i-1]+ls[i+1]+ls[i+2]+........+ls[n]。

这是因为第一条边对于i来说只有a[1]的贡献,而第二条边有a[1]+a[2]的贡献,然后处理前缀的前缀和后缀的后缀就好啦!

已知b[i]求a[i]:

先把柿子列出来:

b[1]=ls[2]+.....+ls[n]。

b[2]=pr[1]+ls[3]+.....+ls[n]。

作差发现b[1]-b[2]=ls[2]-pr[1],设sum=a[1]+......+a[n]。

辣么显然pr[i]+ls[i+1]=sum

=>b[1]-b[2]=sum-2*pr[1]。

以此类推 b[i]-b[i+1]=sum-2*pr[i]。

累加发现b[1]-b[n]=(n-1)*sum-2*Σpr[i](1<=i<n)

又发现后面那个sigma可以变成b[n]。

所以b[1]+b[n]=(n-1)*sum => sum=(b[1]+b[n])/(n-1)

知道sum就可以利用前面的柿子愉快的推出来了!

树上的以此类推就好啦,不过把前缀后缀换成了子树a[i]的和

AC代码:

NOIP模拟测试9NOIP模拟测试9
 1 #include<bits/stdc++.h>
 2 #define mem(a) memset(a,0,sizeof(a))
 3 #define MAXN 100050
 4 #define int long long
 5 using namespace std;  6 int n,a[MAXN],b[MAXN],tot,head[MAXN],nxt[MAXN*3],to[MAXN*3],cnt,rt,sz[MAXN];  7 int mmp;  8 void add(int u,int v)  9 {  10     to[++cnt]=v;  11     nxt[cnt]=head[u];  12     head[u]=cnt;  13 }  14 void clear()  15 {  16     mem(a);mem(b);tot=0;cnt=0;mem(head);mem(sz);mmp=0;  17 }  18 void dfs(int x,int fa,int depth)  19 {  20     b[rt]+=a[x]*depth;  21     sz[x]=a[x];  22     for(int i=head[x];i;i=nxt[i])  23  {  24         int y=to[i];  25         if(y==fa)continue;  26         dfs(y,x,depth+1);  27         sz[x]+=sz[y];  28  }  29     return ;  30 }  31 void dfs1(int x,int fa)  32 {  33     if(x!=rt)b[x]=b[fa]+tot-2*sz[x];  34     for(int i=head[x];i;i=nxt[i])  35  {  36         int y=to[i];  37         if(y==fa)continue;  38  dfs1(y,x);  39  }  40 }  41 void dfs2(int x,int fa)  42 {  43     if(x!=rt)tot+=b[x]-b[fa];  44     for(int i=head[x];i;i=nxt[i])  45  {  46         int y=to[i];  47         if(y==fa)continue;  48  dfs2(y,x);  49  }  50 }  51 void dfs3(int x,int fa)  52 {  53     if(x!=rt)a[x]=sz[x]=(tot+b[fa]-b[x])/2;  54     for(int i=head[x];i;i=nxt[i])  55  {  56         int y=to[i];  57         if(y==fa)continue;  58  dfs3(y,x);  59         if(x!=rt)a[x]-=sz[y];  60  }  61     if(x!=rt)mmp+=a[x];  62     return ;  63 }  64 signed main()  65 {  66     int t;rt=1;  67     scanf("%lld",&t);  68     while(t--)  69  {  70  clear();  71         scanf("%lld",&n);  72         for(int i=1;i<n;i++)  73  {  74             int a,b;  75             scanf("%lld%lld",&a,&b);  76  add(a,b);add(b,a);  77  }  78         int mt;  79         scanf("%lld",&mt);  80         if(!mt)  81  {  82             for(int i=1;i<=n;i++)scanf("%lld",&a[i]),tot+=a[i];  83             dfs(1,0,0);  84             dfs1(1,0);  85             for(int i=1;i<=n;i++)printf("%lld ",b[i]);  86             puts("");  87  }  88         else
 89  {  90             for(int i=1;i<=n;i++)scanf("%lld",&b[i]);  91             tot=b[1]*2;  92             dfs2(1,0);  93             tot/=(n-1);  94             dfs3(1,0);  95             a[rt]=tot-mmp;  96             for(int i=1;i<=n;i++)printf("%lld ",a[i]);  97             puts("");  98  }  99  } 100     return 0; 101 }
View Code

 



T3是个打表找规律题,不说啦

 

考试反思:

第一次写考试反思,以前只写了题解(甚至有的题解都没写)。
连续爆炸后是波澜不惊,还是任其东西,在你自己,wd大佬一次rk15把自己说的什么都不是,而你次次落后还不知悔改。
你可以笨,但不能自甘堕落,也许努力没有结果,但不努力一定没有结果!
人生百态,世事沉浮,你,只能靠自己啊。
以前的你虽然菜,但基本上不挂分,现在又菜又挂分,是能力问题吗?
为什么以前能做到的现在反而做不到了?   
暴力变难了吗?   你变傻了吗? 还是你的态度有问题?
你怎么做的你自己清楚,你想干什么你自然也清楚,而你能不能做到,在你心里也早有定数。
模板不会,知识点理解不透彻,思维不够,你还剩什么呀!
只有暴力,难道你就要用一直挂分的暴力苟且?  就算你能苟过联赛,下面的路呢? 就不走了吗?
一个题的分数是有限的,但算法的优化是无限的,你还在为T3 95分沾沾自喜吗?
一个显然的规律,被你打了两个小时的表,那么多人AC,你就不能找找规律吗?
还是,你就认为自己找不出来?

这不是什么考试技巧,这是你对自己的定位,你凭什么认为就那么难,你就推不出来?
在不该浪费时间的题上浪费时间,该得的分却拿不到。
你的考试策略出现了很大的问题
不管什么题,先试着推一下,骗分是迫不得已的行为。
某学长曾说过:或许这,或许那,都是经历,愿OI,成为你无悔的历练。