NOIP提高组模拟赛1
A 平凡的函数
做法：魔改欧拉筛
\(f[1]=1\)
\(f[p^c] =p\) \(xor\) \(c\) (p为素数)
\(f[ab]=f[a]f[b]\)(a,b互质)
可以发现\(p^c\)容易处理，而\(f[p]=p\;xor\;1\)
考虑其他数，根据唯一分解定理\(x=p1^{c1}*p2^{c2}*...pn^{cn}\)
两数互质，分解后没有公共质因子
那么我们把该数的某个质因子拆下来，一定与剩下的互质，即\(f[x]=f[p1^{p1}...pn^{cn}]=f[pi^{ci}]f[x/pi^{ci}]\)
怎么处理？先筛质数，观察欧拉筛可以发现奇妙的性质
质数直接求值，非质数一定被筛去，筛去他的是一个质数和另一个数相乘，可以在筛去时求值，当\(i%prime[j]==0\)时，让i不停的除以prime[j]，直到没有这个因子，如果没有剩余，用第二条性质，有剩余，用第一条性质，（小于i的值在计算i之前一定都已经得出，直接用即可）
大约\(O(n)\)解决？
#include
#include
using namespace std;
const int maxn=50000007;
int prime[maxn],cnt;
int v[maxn];
bool flag[maxn];
unsigned long long ans;
int main()
{
freopen("func.in","r",stdin);
freopen("func.out","w",stdout);
int n;cin>>n;
v[1]=1;ans=1;
for(int i=2;i<=n;++i){
if(!flag[i]){
prime[++cnt]=i;
v[i]=i^1;
}
for(int j=1;j<=cnt&&prime[j]*i<=n;++j){
int s=prime[j]*i;
flag[prime[j]*i]=1;
v[prime[j]*i]=v[prime[j]]*v[i];
if(i%prime[j]==0){
int s=i*prime[j];
int p=s,k=0,q=1;
while(p%prime[j]==0){p/=prime[j];k++;q*=prime[j];}
if(p!=1)v[s]=v[p]*v[q];
else v[s]=prime[j]^k;
break;
}
}
ans+=v[i];
// printf("%d %d\n",i,v[i]);
}
cout< B. 那一天她离我而去
暴力一点的想法是删掉与1相连的边，然后在与1相邻的点两两之间跑最短路，复杂度\(O(数据水能过)\)
正解分组最短路，我们没有必要两两跑最短路，将与1相邻的点和边单独存一下，与1相邻的点的编号对应的二进制一定至少有一位不相同，于是我们枚举每个二进制位，每次将该位为1的点x与1连一条1->x的边，为0的向虚拟点n+1连边，边权为原来1-x的边权，这样跑1-n+1的最短路即可，任意两个点一定分别出于两端至少一次，他们构成的环一定能跑出来。枚举二进制时，每次回复一下head数组和tot，再连该次所需边即可
注意数组开大点，尤其是边
#include
#include
#include
using namespace std;
int min(int x,int y){return xq;
void spfa(){
memset(vis,0,sizeof(vis));
for(int i=2;i<=n+1;++i)dis[i]=inf;
dis[1]=0;q.push(1);
while(!q.empty()){
int x=q.front();q.pop();vis[x]=0;
for(int i=head[x];i;i=a[i].net){
int v=a[i].to;
if(dis[x]+a[i].val C. 熟练剖分
乍一看以为是道水题，仔细一看我是菜鸡
期望写成分数取模，不如用总长度除以总方案数，都是整数，求逆元
总方案数就是所有节点子节点个数之积
读入时候顺便求一下就行（别问我为啥说这个）
设\(dp[i][j]\)表示i为根的子树最坏复杂度小于等于j的方案数
考虑每个节点是重儿子情况
a 子树贡献了j ，其他结点子树贡献小于等于j-1
b 其他节点子树贡献j-1，该子树贡献小于等于j
如果不是重儿子的情况，由其他节点计算
然后我们把两者合并，去掉重复，贡献为该子树小于等于j的方案数乘以其他子树小于等于j-1的方案数
即\(s\)子树对当前子树\(i\)的贡献为\(f[s][j]*\prod f[k][j-1](k是i的子树，k\not= s)\)
边界条件，i是叶结点，\(f[i][j]=1\;j\epsilon[1,n]\)
只有一棵子树的点额外有\(f[i][0]=f[k][0]\),这样保证只有连续到叶都是只有一棵子树才是1
正常的转移j从1到该点到最远叶结点的距离即可,DFS时求出距离high[i]，但是由于后面可能会用到大于high[i]的，所以需要将大于high[i]的都赋成f[i][high[i]]
..........
直接转移每次都是\(O(high[i]*size^2)\)
求总积再除可能因为取模比较麻烦（容易挂）
\(lyin\)大佬有\(O(k*size)\)预处理\(O(1)\)求贡献的奇妙方法，可以去掉一个size
维护\(qz[s]\;hz[s]\)分别记录1-s子树\(f[son][k-1]\)的积和s-n的积，即前缀和后缀积，然后转移就可以\(f[i][j]=f[k][j]*qz[k-1]*hz[k+1]\)避免了除法运算
#include
#include
using namespace std;
const int maxn=3005;
const int mod=1e9+7;
int max(int x,int y){return x>y?x:y;}
long long qpow(long long x,long long y){
long long ans=1;
while(y){
if(y&1)ans=(ans*x)%mod;
x=(x*x)%mod;
y=y>>1;
}
return ans;
}
int head[maxn],tot;
struct edge{
int to,net;
}a[maxn*2+1];
void add(int u,int v){
++tot;
a[tot].net=head[u];
head[u]=tot;
a[tot].to=v;
}
long long dp[maxn][maxn],n;
long long hi[maxn],fa[maxn],qz[maxn],hz[maxn],l[maxn];
void db(){
for(int i=1;i<=n;++i){
for(int j=0;j<=n;++j)
printf("%d ",dp[i][j]);
puts("");
}
}
void dfs(int root,int fx){
for(int i=head[root];i;i=a[i].net){
if(a[i].to==fx)continue;
dfs(a[i].to,root);
hi[root]=max(hi[a[i].to]+1,hi[root]);
}
int cnt=0;
for(int i=head[root];i;i=a[i].net){
if(a[i].to==fx)continue;
l[++cnt]=a[i].to;
}
if(!cnt){for(int i=0;i<=n;++i)dp[root][i]=1;return;}
if(cnt==1)dp[root][0]=dp[l[1]][0];
qz[0]=1;hz[cnt+1]=1;
for(int k=1;k<=hi[root];++k){
for(int i=1;i<=cnt;++i)qz[i]=qz[i-1]*dp[l[i]][k-1]%mod;
for(int i=cnt;i>=1;--i)hz[i]=hz[i+1]*dp[l[i]][k-1]%mod;
for(int i=1;i<=cnt;++i)dp[root][k]=(dp[root][k]+((dp[l[i]][k]*qz[i-1])%mod*hz[i+1])%mod)%mod;
}
for(int i=hi[root]+1;i<=n;++i)dp[root][i]=dp[root][i-1];
}
int main()
{
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
scanf("%d",&n);
long long fm=1;
for(int i=1;i<=n;++i){
int k;scanf("%d",&k);
if(k)fm=fm*k%mod;
for(int j=1;j<=k;++j){
int u;scanf("%d",&u);
add(i,u);fa[u]=i;
}
}
int root;for(int i=1;i<=n;++i)if(!fa[i]){root=i;break;}
dfs(root,0);
long long la=0;
for(int i=1;i<=n;++i)la=(la+(((dp[root][i]-dp[root][i-1])%mod+mod)%mod)*i)%mod;
printf("%lld\n",(qpow(fm,mod-2)*la)%mod);
return 0;
}