Noip模拟75 2021.10.12
2024-09-02 06:33:08
T1 如何优雅的送分
他说是送分题，我就刚，没刚出来，想到莫比乌斯容斥后就都没推出来
好吧还是不能被恶心的题目，挑衅的语言打乱做题节奏
于是这一场也就没了。。。。
$F(i)$表示$i$的不同质因子集合大小
$2$的这么多次方显然是在枚举子集
那么改变一下枚举顺序，问题答案可以理解为：
几个不同的质数连乘组成的数在$n$的范围内有多少倍数
考虑枚举这个乘积，可以得到式子
$ans=\sum\limits_{k=1}^{n} \mu ^2(k) \left \lfloor \frac{n}{k} \right \rfloor$
关于使用$\mu ^2$考虑$\mu$的定义式
$\begin{cases}
1 & n= 1\\
(-1)^k & n= p_1^{c_1}p_2^{c_2}..,k=\sum c\\
0 & n \textit{含有平方因子}
\end{cases}$
那么$\mu^2$只会有$0,1$两种取值，$\mu^2(k)=0$当且仅当$k$含有平方因子
所以上式等价于$\sum\limits_{i=0}^{n}2^{F(i)}$
考虑让上式变得可做，不妨重新搞一下
$2^{F(i)}=\sum\limits_{d|n}\mu^2(d)=\sum\limits_{d|n}\sum\limits_{k^2|d}\mu(k)$
证明一下正确性，当$d$没有平方因子时显然正确，$k$只能等于$1$
当$d$有平方因子时，考虑为什么$\sum\limits_{k^2|d}\mu(k)=0$
$k$一定可以质因数分解，而当$k$也含有平方因子的情况不考虑，因为他不会对答案造成贡献
那么我们可以把$k$看成多个$1$次质数乘积，考虑从$d$中的含平方因子项中选择
那么$\sum\limits_{k^2|d}\mu(k)=\sum\limits_{i=0}^{n}(-1)^{i}C_{n}^{i}1^{n-i}=(1-1)^n=[n=0]$其中$n$表示$d$的平方因子个数
显然$n!=0$，则当$d$含有平方因子时，$\sum\limits_{k^2|d}\mu(k)=0$
那么
$\sum\limits_{i=0}^n2^{F(i)}=\sum\limits_{i=0}^n\sum\limits_{d|i}\sum\limits_{k^2|d}\mu(k)=\sum\limits_{k=0}^n\mu(k)\sum\limits_{k^2|d}\lfloor\frac{n}{d}\rfloor$
然后改变枚举$k$的几倍
$\sum\limits_{k=0}^n\mu(k)\sum\limits_{k^2|d}\lfloor\frac{n}{d}\rfloor=\sum\limits_{k=0}\mu(k)\sum\limits_{i=1}^{\lfloor\frac{n}{k^2}\rfloor}\lfloor\frac{n}{ik^2}\rfloor$
然后就可以数论分块简单过掉了，（我觉得这题可以单独写一篇题解了，然后美其名曰送分。。）
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 namespace AE86{
5 inline int read(){
6 int x=0,f=1;char ch=getchar();
7 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
8 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
9 }inline void write(int x,char opt='\n'){
10 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
11 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
12 for(register int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
13 }using namespace AE86;
14 const int NN=1e6+5,mod=1e9+7;
15 int prime[NN],cnt,n,ans,mu[NN],Smu[NN],sum[NN];
16 bool vis[NN];
17 inline void getprime(){
18 mu[1]=1; Smu[1]=1;
19 for(int i=2;i<NN;i++){
20 if(!vis[i]) prime[++cnt]=i,mu[i]=-1;
21 for(int j=1;j<=cnt&&i*prime[j]<NN;j++){
22 vis[i*prime[j]]=1;
23 if(i%prime[j]==0) break;
24 mu[i*prime[j]]=-mu[i];
25 }
26 }
27 for(int i=2;i<NN;i++) Smu[i]=Smu[i-1]+mu[i];
28
29 }
30 inline int calc(int n){
31 int l=1,r,ans=0;
32 while(l<=n){
33 r=min(n,n/(n/l));
34 (ans+=(n/l)*(r-l+1)%mod)%=mod;
35 l=r+1;
36 }
37 return ans;
38 }
39 namespace WSN{
40 inline short main(){
41 freopen("elegant.in","r",stdin);
42 freopen("elegant.out","w",stdout);
43 getprime();n=read();
44 int l=1,r,ans=0,B=sqrt(n);
45 while(l<=B){
46 r=min(n,n/(n/l));
47 (ans+=calc(n/(l*l))*((Smu[r]-Smu[l-1]+mod)%mod)%mod)%=mod;
48 l=r+1;
49 } write(ans);
50 return 0;
51 }
52 }
53 signed main(){return WSN::main();}
T2 阴阳
数据水直接用$set$水过，后来被卡了，所以现在只有$91$分
1 #include<bits/stdc++.h>
2 using namespace std;
3 namespace AE86{
4 inline int read(){
5 int x=0,f=1;char ch=getchar();
6 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
7 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
8 }inline void write(int x,char opt='\n'){
9 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
10 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
11 for(register int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
12 }using namespace AE86;
13 const int NN=1e5+5;
14 int t,n,opt,x,m,ban,c;
15 set<int> S[NN];
16 struct SNOW{int to,next;}e[NN<<1]; int head[NN],rp;
17 inline void add(int x,int y){
18 e[++rp]=(SNOW){y,head[x]};head[x]=rp;
19 e[++rp]=(SNOW){x,head[y]};head[y]=rp;
20 }
21 namespace tree_division{
22 int dfn[NN],rk[NN],son[NN],fa[NN],top[NN],dep[NN],siz[NN],cnt;
23 inline void dfs1(int f,int x){
24 dep[x]=dep[f]+1; siz[x]=1; fa[x]=f;
25 for(int i=head[x];i;i=e[i].next){
26 int y=e[i].to;if(y==f) continue;
27 dfs1(x,y); siz[x]+=siz[y];
28 if(siz[son[x]]<siz[y]) son[x]=y;
29 }
30 }
31 inline void dfs2(int x,int t){
32 top[x]=t; dfn[x]=++cnt; rk[cnt]=x;
33 if(son[x]) dfs2(son[x],t);
34 for(int i=head[x];i;i=e[i].next){
35 int y=e[i].to;
36 if(y!=fa[x]&&y!=son[x]) dfs2(y,y);
37 }
38 }
39 inline int LCA(int x,int y){
40 while(top[x]!=top[y]){
41 if(dep[top[x]]<dep[top[y]]) swap(x,y);
42 x=fa[top[x]];
43 }if(dfn[x]>dfn[y]) swap(x,y);
44 return x;
45 }
46 }using namespace tree_division;
47 namespace WSN{
48 inline short main(){
49 freopen("yygq.in","r",stdin);
50 freopen("yygq.out","w",stdout);
51 t=read(); n=read();
52 for(int i=1,u,v;i<n;i++) u=read(),v=read(),add(u,v);
53 dfs1(0,1); dfs2(1,1);
54 m=read();int lastans=0;
55 while(m--){
56 opt=read(),x=(read()^(lastans*t));
57 if(opt==1){
58 ++ban; S[ban]=S[c];
59 if(x>n){lastans=1000000000,puts("1000000000");continue;}
60 if(S[ban].find(x)==S[ban].end()) S[ban].insert(x);
61 else S[ban].erase(S[ban].find(x));
62 c=ban;
63 }
64 if(opt==2){
65 if(x>n){lastans=1000000000,puts("1000000000");continue;}
66 int ans=1000000000;
67 for(set<int>::iterator it=S[c].begin();it!=S[c].end();it++){
68 int lca=LCA(*it,x);
69 ans=min(ans,dep[x]+dep[*it]-dep[lca]*2);
70 } write(ans); lastans=ans;
71 }
72 if(opt==3){
73 if(x>ban)continue;
74 c=x;
75 }
76 }
77 return 0;
78 }
79 }
80 signed main(){return WSN::main();}
T3 你猜是不是找规律
显然不是找规律
$dp$非常好写，重要是优化，他可以用拉格朗日插值（？）
确实一片大雾，真就啥都能优化$dp$
关于多项式的证明现在大佬们貌似还在问，总之题解说啥我干啥就过了
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 namespace AE86{
5 inline int read(){
6 int x=0,f=1;char ch=getchar();
7 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
8 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
9 }inline void write(int x,char opt='\n'){
10 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
11 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
12 for(register int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
13 }using namespace AE86;
14 const int NN=3005,mod=1e9+7;
15 int n,k,ans,f[NN];
16 struct node{int x,y;}p[NN<<1];
17 inline int qmo(int a,int b,int ans=1){int c=mod;
18 for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;
19 return ans;
20 }
21 inline int inv(int x){return qmo(x,mod-2);}
22 inline int lagrange(int k,int n,int ans=0){
23 for(int i=1;i<=n;i++){
24 int s1=p[i].y%mod,s2=1;
25 for(int j=1;j<=n;j++)
26 if(i!=j) s1=s1*((k-p[j].x+mod)%mod)%mod,s2=s2*((p[i].x-p[j].x+mod)%mod)%mod;
27 ans=(ans+s1*inv(s2)%mod)%mod;
28 }
29 return ans;
30 }
31 namespace WSN{
32 inline short main(){
33 freopen("guess.in","r",stdin);
34 freopen("guess.out","w",stdout);
35 n=read();k=read();f[0]=1;
36 if(!k) return puts("1"),0;
37 p[1].x=1;for(int i=0;i<=k;i++) p[1].y+=f[i];
38 for(int i=2;i<=2*k+1;i++){
39 for(int j=k;j;j--) f[j]=(f[j]+f[j-1]*(i-1)%mod)%mod;
40 for(int j=0;j<=k;j++) (p[i].y+=f[j])%=mod;
41 p[i].x=i;
42 }
43 write(lagrange(n,2*k+1));
44 return 0;
45 }
46 }
47 signed main(){return WSN::main();}
T4 小说
唯一一道联赛难度题目
然后用到了倒背包，就是开两个$dp$一个是放进去的，一个是倒出来的，好理解不好写（bushi）
然后就完了
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 namespace AE86{
5 inline int read(){
6 int x=0,f=1;char ch=getchar();
7 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
8 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
9 }inline void write(int x,char opt='\n'){
10 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
11 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
12 for(register int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
13 }using namespace AE86;
14 const int NN=1005,MM=7e5+5,mod=998244353;
15 int n,v[NN],a,b,sum,dp[MM<<1],pd[MM];
16 namespace WSN{
17 inline short main(){
18 freopen("novel.in","r",stdin);
19 freopen("novel.out","w",stdout);
20 n=read(); dp[0]=1;
21 for(int i=1;i<=n;i++) v[i]=read();
22 for(int i=1;i<=n;i++){
23 sum+=v[i];
24 for(int j=sum;j>=v[i];j--) dp[j]=(dp[j]+dp[j-v[i]])%mod;
25 }
26 sort(v+1,v+n+1);
27 int mx=0;
28 for(int j=1;j<=n;j++){
29 int tmp=0;memset(pd,0,sizeof(pd));pd[0]=1;
30 for(int i=1;i<=sum;i++){
31 if(i<v[j]) pd[i]=dp[i];
32 else pd[i]=(dp[i]-pd[i-v[j]]+mod)%mod;
33 }
34 for(int i=1;i<=sum;i++) tmp+=(pd[i]>0);
35 if(tmp>mx) mx=tmp,a=j;
36 // cout<<tmp<<endl;
37 }
38 // cout<<mx<<endl;
39 write(v[a],' '); sum-=v[a];
40 memset(dp,0,sizeof(dp)); dp[sum]=1;
41 for(int i=1;i<=n;i++) if(i!=a){
42 for(int j=sum*2;j>=v[i];j--)
43 if(dp[j-v[i]]) dp[j]=1;
44 for(int j=0;j<=sum*2-v[i];j++)
45 if(dp[j+v[i]]) dp[j]=1;
46 }
47 for(int i=1;i<=sum;i++)
48 if(!dp[i+sum]) return write(i),0;
49 write(sum+1);
50 return 0;
51 }
52 }
53 signed main(){return WSN::main();}
最新文章
- Nancy之Forms authentication的简单使用
- Linux命令之reset - 终端屏幕混乱的终结者
- 25款顶级的jQuery表格插件
- python基础——迭代
- 《day09---继承-抽象类-接口》
- C预处理，条件编译
- BIND9配置文件详解模板[转载]
- mysql的数据类型int、bigint、smallint 和 tinyint取值范围 及varchar
- 网络流（最大流）：CodeForces 499E Array and Operations
- poj 1328 Radar Installation（贪心）
- hdu_1348_Wall（凸包）
- 设置MyEclipse黑色主题背景
- mybatis错误——java.io.IOException: Could not find resource com/xxx/xxxMapper.xml
- Win10家庭版WindowsUpdate属性为灰色
- eclipse添加缺失的包/src/main/resource
- 深入浅出zeptojs中tap事件
- Keepalived配置与使用--转载
- Jquery 对比 Javascript
- linux python 安装 nose lapack atlas numpy scipy
- 6.9-JDBC