T1 如何优雅的送分
考虑式子的实际意义。\(2^{f_n}\)实际上就是枚举\(n\)质因子的子集。令\(k\)为这个子集中数的乘积，就可以将式子转化为枚举\(k\)，计算\(k\)的贡献。
不难得出\(k\)一定没有平方因子，那么枚举\(k\)就可以写为枚举\(\left \{ \mu^2(d)|d\in N^* \right \}\)，即:
\[2^{f_i}=\sum_{k=1}^n\mu^2(k)
\]
发现有\(\mu^2(d)=\sum_{k^2|d}\mu(k)\)，证明时考虑\(d\)有几个平方因子。当没有时，\(k\)只能取\(1\)。否则令\(x\)为它的平方因子个数，有：
\[\sum_{k^2|d}\mu(k) =\sum_{d=0}^x(-1)^d\binom{x}{d}
\]
发现它就是个二项式定理，即\((-1+1)^x=0\)。于是等式成立。
于是接下来一波合适变换整成整除分块的形式，求答案即可。
\[\begin{aligned}
\sum_{i=1}^n2^{f_i} &=\sum_{i=1}^n\sum_{d|i}\mu^2(d)
\\ &=\sum_{i=1}^n\sum_{d|i}\sum_{k^2|d}\mu(k)
\\ &=\sum_{k=1}^n\sum_{k^2|d}\left\lfloor \frac{n}{d} \right\rfloor
\\ &=\sum_{k=1}^n\mu(k)\sum_{i=1}^{\left\lfloor\frac{n}{k^2}\right\rfloor}\left\lfloor\frac{n}{k^2i}\right\rfloor
\\ &=\sum_{k=1}^n\mu(k)S(\left\lfloor\frac{n}{k^2}\right\rfloor)
\end{aligned}
\]
其中\(S(n)=\sum_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor\)，枚举\(k\)，整除分块求\(S\)即可。时间复杂度\(\Theta(\sqrt n \ln n)\)。
数学题题解写着真累
\(code:\)
T1
#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace IO{
typedef long long LL;
auto read=[]()->int{
char ch=getchar(); int x=0,f=1;
while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
return x*f;
};
auto write=[](LL x,int sp)->void{
char ch[20]; int len=0;
if(x<0){ x=~x+1; putchar('-'); }
do{ ch[len++]=(1<<4)+(1<<5)+x%10; x/=10; }while(x);
for(int i=len-1;~i;--i) putchar(ch[i]); putchar(sp);
};
auto ckmax=[](int& x,int y)->void{ x=x<y?y:x; };
auto ckmin=[](int& x,int y)->void{ x=x<y?x:y; };
} using namespace IO;
const int p=1e9+7;
int n,ext,ans,cnt,pri[1000010],mu[1000010];
bool vis[1000010];
void get(){
mu[1]=1;
for(int i=2;i<=ext;i++){
if(!vis[i]) pri[++cnt]=i, mu[i]=-1;
for(int j=1;j<=cnt&&pri[j]*i<=ext;j++){
vis[pri[j]*i]=1;
if(!(i%pri[j])) break;
mu[pri[j]*i]=-mu[i];
}
}
}
int calc(int N){
int l=1,r,res=0;
while(l<=N){
r=N/(N/l);
(res+=(N/l)*(r-l+1))%=p;
l=r+1;
}
return res;
}
signed main(){
freopen("elegant.in","r",stdin);
freopen("elegant.out","w",stdout);
n=read(); ext=sqrt(n); get();
for(int i=1;i<=ext;i++)
(ans+=p+mu[i]*calc(n/(i*i)))%=p;
return write(ans,'\n'),0;
}
T2 阴阳
\(set\)大暴力，记黑点。显然被卡了，正解太神仙，暴力没啥意思，不放代码了。
T3 你猜是不是找规律
令\(f_{i,j}\)为长度为\(i\)的排列，最少交换\(j\)次合法的方案数。转移时考虑新一个数是否放在最后，有
\[f_{i,j}=f_{i-1,j}+(i-1)\times f_{i-1,j-1}
\]
非常感性地发现\(f_{n,k}\)为关于\(n\)的\(2k-1\)次多项式，答案，即\(\sum_{i=0}^k f_{n,i}\)，为关于\(n\)的\(2k\)次多项式。拉格朗日插值即可。
\(code:\)
T3
#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace IO{
typedef long long LL;
auto read=[]()->int{
char ch=getchar(); int x=0,f=1;
while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
return x*f;
};
auto write=[](LL x,int sp)->void{
char ch[20]; int len=0;
if(x<0){ x=~x+1; putchar('-'); }
do{ ch[len++]=(1<<4)+(1<<5)+x%10; x/=10; }while(x);
for(int i=len-1;~i;--i) putchar(ch[i]); putchar(sp);
};
auto ckmax=[](int& x,int y)->void{ x=x<y?y:x; };
auto ckmin=[](int& x,int y)->void{ x=x<y?x:y; };
} using namespace IO;
const int NN=3010,p=1e9+7;
int n,k,ans,f[NN];
int x[NN<<1],y[NN<<1];
int qpow(int a,int b){
int res=1;
while(b){
if(b&1) res=res*a%p;
a=a*a%p;
b>>=1;
}
return res;
}
inline int langrange(int num,int xx){
int res=0; xx%=p;
for(int i=1;i<=num;i++){
int s1=y[i]%p,s2=1;
for(int j=1;j<=num;j++)
if(i!=j) s1=s1*(xx-x[j]+p)%p, s2=s2*(x[i]-x[j]+p)%p;
(res+=s1*qpow(s2,p-2)%p)%=p;
}
return res;
}
signed main(){
freopen("guess.in","r",stdin);
freopen("guess.out","w",stdout);
n=read(); k=read();
x[1]=1; y[1]=1; f[0]=1;
for(int i=2;i<=2*k+1;i++){
x[i]=i;
for(int j=k;j;j--) (f[j]+=(i-1)*f[j-1])%=p;
for(int j=0;j<=k;j++) (y[i]+=f[j])%=p;
}
return write(langrange(2*k+1,n),'\n'),0;
}
T4 小说
题解说得很清楚。
\(01\)退背包：记\(f\)为原\(01\)背包方案数，\(g\)为强制第\(i\)件物品不选的方案数。有
\[g_k=\begin{cases} f_k & k<v_i \\ f_k-g_{k-v_i} &k\geq v_i \end{cases}
\]
\(code:\)
T4
#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace IO{
typedef long long LL;
auto read=[]()->int{
char ch=getchar(); int x=0,f=1;
while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
return x*f;
};
auto write=[](LL x,int sp)->void{
char ch[20]; int len=0;
if(x<0){ x=~x+1; putchar('-'); }
do{ ch[len++]=(1<<4)+(1<<5)+x%10; x/=10; }while(x);
for(int i=len-1;~i;--i) putchar(ch[i]); putchar(sp);
};
auto ckmax=[](int& x,int y)->void{ x=x<y?y:x; };
auto ckmin=[](int& x,int y)->void{ x=x<y?x:y; };
} using namespace IO;
const int NN=110,WW=1401000,p=998244353;
int n,mx,pos,ans,sum,tot,v[NN];
int f[WW],g[WW];
void work(int I){
int res=0;
memset(g,0,sizeof(g)); g[0]=1;
for(int i=1;i<=sum;i++)
if(i<v[I]) g[i]=f[i];
else g[i]=(f[i]-g[i-v[I]]+p)%p;
for(int i=1;i<=sum;i++)
res+=(bool)g[i];
if(res>mx) mx=res,pos=I;
}
signed main(){
freopen("novel.in","r",stdin);
freopen("novel.out","w",stdout);
n=read(); f[0]=1;
for(int i=1;i<=n;i++)
sum+=(v[i]=read());
sort(v+1,v+n+1);
for(int i=1;i<=n;i++)
for(int j=sum;j>=v[i];j--)
(f[j]+=f[j-v[i]])%=p;
for(int i=1;i<=n;i++) work(i);
tot=sum-v[pos]; write(v[pos],' ');
memset(f,0,sizeof(f)); f[tot]=1;
for(int i=1;i<=n;i++) if(i!=pos){
for(int j=tot+tot;j>=v[i];j--)
f[j]|=f[j-v[i]];
for(int j=0;j<=tot+tot-v[i];j++)
f[j]|=f[j+v[i]];
}
for(int i=1;i<=tot;i++)
if(!f[i+tot]) return write(i,'\n'),0;
return write(tot+1,'\n'),0;
}
![[考试反思]0801NOIP模拟测试11](https://www.kunjuke.com/file/css/thumb/6.jpg/280-180.jpg)
![[NOI.AC省选模拟赛3.23] 集合 [数学]](https://www.kunjuke.com/file/css/thumb/10.jpg/280-180.jpg)
![[NOI.AC省选模拟赛3.30] Mas的童年 [二进制乱搞]](https://www.kunjuke.com/file/css/thumb/7.jpg/280-180.jpg)
