「Log」2023.8.11 小记

间幕 \(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{royalblue}{P3469\ [POI2008]\ BLO-Blockade}\)

考虑分类讨论：

• 若节点 \(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;
}