今天又是自闭的一天,不过今天终于有了签到题,体验比前两天好了不少,并从数论题上学到了一些东西。
顺便每个题把老师的一句话题解贴上了
A 二十四点*
搜+打表,370个无解集合。
unsolved
B 集合
分类讨论,反射,二分求出入射角等于反射角的值,O(Tlogn)
C 小游戏
DP,O(nlogn)
unsolved
D 精简改良
状压 DP,O(3nn2)
unsolved
E 最大独立集
贪心, O(n)
unsolved
F 小清新数论*
搞完签到题后一直在搞这一道题,但是可惜,最后还是没能做出来,但是做了一下午没做出来反而是我今天最大的收获,下面就写写我下午做这道题的经过吧。
这道题乍一看莫比乌斯函数就被吓了一跳,但是为了克服对数论的恐惧,只能硬着头皮上,头铁了一下午,总算是对莫比乌斯函数有了些了解。
先说说我的思路,一开始我是认为这道题跟莫比乌斯反演有很大关系,虽然现在看看确实如此,但是我最终做出来的时候,并没有用到莫比乌斯反演。一开始去看了很多莫比乌斯反演的博客,尝试性得将公式化简了一下,但是没有成功。不过,这为我后来的化简提供了一些思路。
首先,由枚举 i , j 改为枚举 d 。
后面的公式又可以写成
其实到这里我就不会做了,因为我只找到了求 **μ(n)** 的板子,后面的完全无法下手,所以我晚上要来了庄学姐的代码,发现他用了下面这个公式就可以 **O(n)** 求出结果(我总觉得他是感性认知出来的,因为我就是靠感性证明的)。
为什么会这样呢,我用了一个感性认知的方法来证明 我们以 **n=5** 的 **gcd(i,j)** 为例子
显然它是关于从 到 的直线对称的,如果只考虑半边,第 行中 的值为 1 的个数为 ,特殊的,令 ,则 就是其中一个半边中的为 1 的数的个数,乘上二再加对称轴上的一个 1 ,就是 式。
最后,靠着学长网上找的线性筛的板子,总算是做出了这道题。
怎么说呢,这道题还是没有真正明白,不管是杜教筛还是莫比乌斯反演都没有学会,之后我会再更新关于他们的博客,并把链接贴到这里。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e7+10,M=998244353;
ll phi[N+10];
bool vis[N+10];
ll prime[N+10];
ll miu[N+10];
ll tot;
void init(){
miu[1]=1;
tot = 0;
for(ll i = 2; i <=N; i ++)
{
if(!vis[i])
{
prime[tot ++] = i;
phi[i] = i - 1;
miu[i]=-1;
}
for(ll j = 0; j < tot; j ++)
{
if(i * prime[j] >= N) break;
vis[i * prime[j]] = 1;
if(i % prime[j] == 0)
{
miu[i*prime[j]]=0;
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
else
{
phi[i * prime[j]] = phi[i] * phi[prime[j]];
miu[i*prime[j]]=-1*miu[i];
}
}
}
}
int main()
{
int n;
ios::sync_with_stdio(false);
cin>>n;
init();
ll ans=0;
for(int i=1;i<=N;i++){
phi[i]=(phi[i]+phi[i-1])%M;
}
for(int i=1;i<=n;i++)
{
int h=n/i;
ans+=(ll)(10*M+miu[i]*(2*phi[h]+1)%M);//因为miu有负数,所以要加10*M
ans%=M;
}
cout<<ans%M<<endl;
}
G 排列
签到题,能读懂题意就能做出来。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=100005;
int a[N]={0};
int pa[N];
int ans[N];
int main()
{
ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
{
pa[a[i]]=i;
}
int minn=1e9;
for(int i=1;i<=n;i++)
{
if(minn>pa[i]){
minn=pa[i];
}
else if(pa[i]>=minn)pa[i]=minn;
}
int pre=pa[n];
int h=1;
for(int i=n;i>=1;i--)
{
if(pa[i]!=pre){
h++;
pre=pa[i];
}
pa[i]=h;
}
int p=pa[1];
ans[1]=p;
int p1=p+1;
for(int i=2;i<=n;i++)
{
if(pa[i]<p){
ans[i]=pa[i];
p=pa[i];
continue;
}
ans[i]=p1;
p1++;
}
cout<<ans[1];
for(int i=2;i<=n;i++)
cout<<' '<<ans[i];
cout<<endl;
}
H 涂鸦*
贪心, O(n)
unsolved
I 石头剪刀布
并查集, O(na(n))
unsolved
J 子序列
矩阵乘法, O(m^3n), m是字符集大小
unsolved