T^T Saffah大神照样刷我这样诚心诚意想做一套NOIP模拟题的蒟蒻.
第一题 九九归一
好diao的名字...
题意就是给定一队$n,q$,求在模$n$意义下一个数$x$自乘的循环节长度.
当$x=0$时候输出$0$是吧...
.................................................实在是太弱了....................................................
连个思路都没有.....
再看一遍题目
萌蛋在练习模n意义下的乘法时发现，总有一些数，在自乘若干次以后，会变成1。例如n=7，那么5×5 mod 7=4,4×5 mod 7=6,6×5 mod 7=2,2×5 mod 7=3,3×5 mod 7=1。如果继续乘下去，就会陷入循环当中。萌蛋还发现，这个循环的长度经常会是φ(n)，即小于n且与n互质的正整数的个数。例如，φ(7)=6，而上述循环的长度也是6，因为5,4,6,2,3,1共有6个数。再如n=6，那么5×5 mod 6=1。这个循环的长度很短，只有2，而恰好φ(6)=2。然而，对于某些情况，虽然循环的长度可以是φ(n)，但存在比φ(n)更小的长度：例如n=7，而2×2 mod 7=4,4×2 mod 7=1，循环的长度只有3。当然，6也可以是一个循环的长度。假设已知了n，我们称数a神奇的，当且仅当关于数a的循环长度可以是φ(n)，而且不存在比φ(n)更小长度的循环。例如对于n=7，5是神奇的，而2不是神奇的。现在给出n和q次询问，每次询问给出a，问a是否是神奇的。
这个循环长度为φ(n)的条件...既然$x^{φleft( n ight)}equiv 1 pmod{n}$,看起来很像欧拉定理...大声告诉我是不是!!!
光知道这个有个P用...真是书到用时方恨少...
还是等Saffah大神的官方题解吧
第二题
似乎有种会做了的感觉...
对于每个节点,将它的每子树节点的w值的和一乘完事...
好吧没时间了.
#include <cstdio>
#define MOD 1000000007
long long fat[200000],w[200000],f[200000],sub[200000],totw[200000],n,p,i,sum;
long long q[200000],qh,qt;
int main(){
scanf("%lld %lld",&n,w+1);
for(i=2;i<=n;++i){
scanf("%lld %lld",fat+i,w+i);
++sub[fat[i]];
}
for(i=1;i<=n;++i){
f[i]=0;
if(!sub[i]){
q[qt++]=i;
totw[i]=0;
f[i]=0;
}
}
while(qh!=qt){
i=q[qh++];
f[i]+=(((w[i]*w[i])%MOD)*(w[i]+totw[i]*2))%MOD;
totw[i]+=w[i];
sum=(sum+f[i])%MOD;
f[fat[i]]+=totw[i]*totw[fat[i]]*w[fat[i]]*2;
totw[fat[i]]+=totw[i];
f[fat[i]]%=MOD;
--sub[fat[i]];
if(!sub[fat[i]]) q[qt++]=fat[i];
}
printf("%lld
", sum);
return 0;
}
-----UPDATE: 似乎没有Mod到位...改一下-----
#include <cstdio>
#include <cstring>
#define MOD 1000000007
long long fat[200000],w[200000],f[200000],sub[200000],totw[200000],n,p,i,sum;
long long q[200000],qh,qt;
int main(int argc,char const *argv[]){
scanf("%lld %lld",&n,w+1);
for(i=2;i<=n;++i){
scanf("%lld %lld",fat+i,w+i);
++sub[fat[i]];
}
for(i=1;i<=n;++i){
f[i]=0;
if(!sub[i]){
q[qt++]=i;
totw[i]=0;
f[i]=0;
}
}
while(qh!=qt){
i=q[qh++];
f[i]+=(((w[i]*w[i])%MOD)*((w[i]+totw[i]*2)%MOD))%MOD;
totw[i]+=w[i];
totw[i]%=MOD;
sum=(sum+f[i])%MOD;
f[fat[i]]+=(totw[i]*totw[fat[i]])%MOD*w[fat[i]]*2;
totw[fat[i]]+=totw[i];
totw[fat[i]]%=MOD;
f[fat[i]]%=MOD;
--sub[fat[i]];
if(!sub[fat[i]]) q[qt++]=fat[i];
}
printf("%lld
", sum);
return 0;
}
这个程序是AC的.