【Atcoder】 [ABC284G] Only Once

题目链接

Atcoder方向
Luogu方向

题目解法

首先一个显然的转化是从 $i$ 向 $a_i$ 连边，那么这样会形成一棵内向基环树，那么 $S_i$ 即为 $i$ 到环的距离
下面有一个妙妙的思路是：对于每一行来说价值和是等价的，所以不妨只计算 $1$ 号点在所有情况下的价值和，然后将答案 $\times n$ 即可
考虑枚举 $1$ 号点走到的第一个重复的点，即为 $1$ 号点到环的距离与环的大小之和，记其为 $i$
那么 $$\begin{gathered} Ans=(n-1{)}^{\underline{i-1}}\times n^{n-i}\times \sum _{j=1}^{i-1}j \\ =(n-1{)}^{\underline{i-1}}\times n^{n-i}\times \frac{i\times (i-1)}{2} \end{gathered}$$
直接计算即可，时间复杂度 $O(n)$

#include <bits/stdc++.h>
using namespace std;
const int N=200100;
int n,P,mi[N];
inline int read(){
	int FF=0,RR=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
	for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
	return FF*RR;
}
int main(){
	n=read(),P=read();
	mi[0]=1;
	for(int i=1;i<=n;i++) mi[i]=1ll*mi[i-1]*n%P;
    int ans=0;
	for(int i=1,res=1;i<=n;res=1ll*res*(n-i)%P,i++){//枚举点1到环的距离与环大小之和
		int t=(1ll*i*(i-1)/2)%P;
		ans=(ans+1ll*res*mi[n-i]%P*t)%P;
	}
	printf("%d\n",1ll*ans*n%P);
	fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25