间幕 \(1\)
从今天开始记小记。
七点到校了，先小摆一会，然后整理博客。
听 MITiS 的电音，开始写题。
\(\color{blueviolet}{P1829\ [国家集训队]\ Crash的数字表格\ /\ JZPTAB}\)
莫反练习题，式子并不难推，两个整除分块解决。
八点整打完，开始调。
忘记初始化了。
筛质数 pri[++pcnt]=true;，不知道自己在写什么。
没给 \(\mu(1)\) 赋值，忘写 ==0，等差数列求和忘除以 \(2\)，不知道自己在些什么。
不小心又炸 int 了，讨厌取模。
总计浪费 \(20min\) 调弱智错误。
\(\text{code:}\)
#include<bits/stdc++.h>
#define LL long long
#define UN unsigned
using namespace std;
//--------------------//
//IO
inline int rd()
{
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
//--------------------//
const int N=1e7+5;
LL n,m;
//--------------------//
//Mob
const int Mod=20101009;
LL mob[N],ms[N];
int pcnt,pri[N];
bool v[N];
void init()
{
mob[1]=1;
for(int i=2;i<=min(n,m);i++)
{
if(!v[i])
mob[i]=-1,pri[++pcnt]=i;
for(int j=1;j<=pcnt&&i*pri[j]<=min(n,m);j++)
{
v[i*pri[j]]=true;
if(i%pri[j]==0)
{
mob[i*pri[j]]=0;
break;
}
mob[i*pri[j]]=-mob[i];
}
}
for(int i=1;i<=min(n,m);i++)
ms[i]=((ms[i-1]+(mob[i]+Mod)*(1LL*i*i%Mod))%Mod)%Mod;//printf("%lld\n",ms[i]);
return;
}
LL f1(LL x,LL y){return (x*(x+1)/2%Mod)*(y*(y+1)/2%Mod)%Mod;}
LL f2(LL x,LL y)
{
LL ans=0;
for(int ed,st=1;st<=min(x,y);st=ed+1)
{
ed=min(x/(x/st),y/(y/st));
ans=(ans+(ms[ed]-ms[st-1]+Mod)*f1(x/st,y/st)%Mod+Mod)%Mod;
}
return ans;
}
//--------------------//
int main()
{
scanf("%lld%lld",&n,&m);
init();
LL ans=0;
for(int ed,st=1;st<=min(n,m);st=ed+1)
{
ed=min(n/(n/st),m/(m/st));
ans=(ans+1LL*(st+ed)*(ed-st+1)/2%Mod*f2(n/st,m/st)%Mod+Mod)%Mod;
}
printf("%lld",ans);
return 0;
}
间幕 \(2\)
开始学杜教筛，没学完，开始听课。
图论会不了一点。
学长请我们喝水。
复习了点双边双，点完外卖开始做题。
外卖到了，正好敲完一遍割点板子，发现以前写的板子有冗余部分。
打完一道题调不出来，开摆，学习打块。
午休结束，开调。
\(\color{blueviolet}{P1829\ [国家集训队]\ Crash的数字表格\ /\ JZPTAB}\)
考虑分类讨论：
- 若节点 \(i\) 不是割点，则 \(ans_i=2(n-1)\)。
- 若节点 \(i\) 是割点，则用组合数计算贡献即可。
具体地，因为点对有向，所以对于每一联通块计算以其为起点的点对。
代码里计算割点答案时把所有子节点全算上了，错误的，应该记录子节点 \(low\) 比当前节点 \(dfn\) 大的贡献。
细微重构，开 long long，A 掉。
#include<bits/stdc++.h>
#define LL long long
#define UN unsigned
using namespace std;
//--------------------//
//IO
inline int rd()
{
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
//--------------------//
const int N=1e5+5;
int n,m;
//--------------------//
const int M=1e6+5;
struct Edge
{
int to,nex;
}edge[M];
int tot,head[N];
void add(int from,int to)
{
edge[++tot]={to,head[from]};
head[from]=tot;
return;
}
int dcnt,dfn[N],low[N];
bool v[N],ansv[N];
LL siz[N],ans[N];
void Tarjan(int now,int fa)
{
v[now]=true,dfn[now]=low[now]=++dcnt,siz[now]=1;
LL scnt=0;
LL sum=0;
for(int to,i=head[now];i;i=edge[i].nex)
{
to=edge[i].to;
if(!v[to])
{
Tarjan(to,now);
siz[now]+=siz[to];
scnt++;
low[now]=min(low[now],low[to]);
if(now==fa||low[to]>=dfn[now])
{
ansv[now]=true;
ans[now]+=siz[to]*(n-siz[to]);
sum+=siz[to];
}
}
else
low[now]=min(low[now],dfn[to]);
}
if(now==fa&&scnt>1)
ansv[now]=true;
if(ansv[now])
ans[now]+=n-1+(sum+1)*(n-sum-1);
else
ans[now]=2*(n-1);
return;
}
//--------------------//
int main()
{
scanf("%d%d",&n,&m);
for(int from,to,i=1;i<=m;i++)
{
scanf("%d%d",&from,&to);
if(from!=to)
add(from,to),add(to,from);
}
Tarjan(1,1);
for(int i=1;i<=n;i++)
printf("%lld\n",ans[i]);
return 0;
}