Atcoder 230
Atcoder 230
\(G.\)GCD Permutation
题意
给定一个\(1\)到\(N\)的排列\(P=(P_1,P_2,...,P_N)\)，问有多少不同的数对\((i,j)\)满足\(1\le i\le j\le N\)，\(GCD(i,j)\neq1\) 并且\(GCD(P_i,P_j)\neq 1\)
\(1\le N\le 2\times 10^5\)
Sol
定义\(\tilde{\mu}(n)=-\mu(n)\)
令\(f(a,b;i,j)=a|i\ \ \ \&\ \ a|j\ \ \ \&\ \ b|P_i\ \ \ \&\ \ \ b|P_j\)
那么\(ans=\sum_{1\le i\le j\le N}\sum_{a=1}^N\sum_{b=1}^N\tilde{\mu}(a)\tilde{\mu}(b)f(a,b;i,j)\)
令\(g=GCD(i,j),g^{' }=GCD(P_i,P_j)\)
那么\(\sum_{a=1}^N\sum_{b=1}^N\tilde{\mu}(a)\tilde{\mu}(b)f(a,b;i,j)=\sum_{a|g}\sum_{b|g^{' }}\tilde{\mu}(a)\tilde{\mu}(b)\)
同时令\(num(a,b)\)表示有多少个\(i\)满足\(i|a\)并且\(P_i|b\)，则\(\sum_{1\le i\le j\le N}f(a,b;i,j)=\frac{num(a,b)(num(a,b)+1)}{2}\)
可以这样理解，假设\(num(a,b)=3\)，说明有\(4\)个下标\(i_1,i_2,i_3\)满足条件，不妨设他们就是从小到大排序，那么
\(f(a,b,i_1,i_1),f(a,b,i_1,i_2),f(a,b,i_1,i_3),f(a,b,i_2,i_2),f(a,b,i_2,i_3),f(a,b,i_3,i_3)\)均符合条件,也就是
\(\sum_{i=1}^{num(a,b)}i\)
\(ans=\sum_{1\le i\le j\le N}\sum_{a=1}^N\sum_{b=1}^N\tilde{\mu}(a)\tilde{\mu}(b)\frac{num(a,b)(num(a,b)+1)}{2}\)
这样计算的时候可以先枚举\(a\)，再枚举\(i\)，然后枚举\(b\)计算\(num(a,b)\)，最后再累计和
#include
#define ll long long
#define inf 0x7f7f7f7fll
#define fi first
#define se second
#define Mod 998244353
#define pb push_back
using namespace std;
template void rd (T &x)
{
x=0;int f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-') f=-1;s=getchar();}
while(s>='0'&&s<='9') x=x*10+(s^48),s=getchar();
x*=f;
}
template void chkMax(T &x, T y) { if (y > x) x = y; }
template void chkMin(T &x, T y) { if (y < x) x = y; }
const int N=2e5+10;
int p[N];
int primes[N],mu[N],st[N],cnt;
void get_primes()
{
mu[1]=0;
for(int i=2;im,d[N],B;
//m存mu不为0的数，d[i]存i的所有因子.
ll num[N];
int main()
{
get_primes();
int n;rd(n);
for(int i=1;i<=n;i++) rd(p[i]);
for(int i=1;i<=n;i++)
if(mu[i])
{
m.pb(i);
for(int j=i;j<=n;j+=i)
d[j].pb(i);
}
ll ans=0;
for(auto a:m) //枚举a
{
for(int i=a;i<=n;i+=a) //枚举下标i,i为a的倍数
{
for(auto j:d[p[i]]) //枚举p[i]的因子b
{
num[j]++; //num(a,b)个数+1
B.pb(j);
}
}
for(auto b:B) ans+=mu[a]*mu[b]*(num[b]*(num[b]+1)/2),num[b]=0;
B.clear();
}
cout< \(F.\)Predilection
给定一个长度为\(N\)的序列，你可以对这个序列进行这样的操作：将相邻的两个数相加后，把这个相加后的数放回它们原来的位置，然后删掉原来的两个数，你可进行若干次操作，每次操作都可能获得一个新的序列，直到只剩下一个数，问可能生成的新的序列的个数。
\(1\le N\le 2\times 10^5\)
\(|A_i|\le10^9\)
\(Sol\)
令\(dp[i]\)表示添加一个数后可以生成的新的序列的个数，显然\(dp[i+1]=2*dp[i]\)，因为假设\(i+1\)前面的序列为\(Sa_i\)，\(S\)表示\(a_i\)前面的全部数字，\(a_i\)也不一定是原来的\(a_i\)，只是表示第\(i+1\)个数前面的那个数字，于是第\(i+1\)个数要么直接加在\(a_i\)后面，要么和\(a_i\)相加后组成新的序列。但可能会重复计算，为什么？因为假设有这样的序列\(S_10S_2\)，那么在转移时\((S_1+0)S_2\)和\(S_1(0+S_2)\)这其实是一个系列，假设产生\(0\)的区间为\([l,r]\)，那么答案还要减去\(dp[l]\)
#include
#define ll long long
#define inf 1e18
#define fi first
#define se second
#define mod 998244353
#define pb push_back
using namespace std;
template void rd (T &x)
{
x=0;int f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-') f=-1;s=getchar();}
while(s>='0'&&s<='9') x=x*10+(s^48),s=getchar();
x*=f;
}
template void chkMax(T &x, T y) { if (y > x) x = y; }
template void chkMin(T &x, T y) { if (y < x) x = y; }
const int N=2e5+10;
int a[N];
int dp[N];
mapmp;
int main()
{
int n;
rd(n);
for(int i=1;i<=n;i++) rd(a[i]);
dp[1]=1;
ll sum=0;
//sum[r]-sum[l]=0
//sum[r]=sum[l]
//mp[sum[r]]=l
for(int i=1;i \(H.\)Bullion
神仙生成函数数和多项式题（不会）