NC20700. 好的序列
描述
输入描述
两个整数N，k，含义见题面
输出描述
一个整数，含义见题面
示例1
输入:
4 2
输出:
22
说明:
示例2
输入:
95723 91427
输出:
236956841
C++14(g++5.4) 解法, 执行用时: 965ms, 内存消耗: 249696K, 提交时间: 2018-10-21 18:12:03
#include<bits/stdc++.h>
#define gc getchar()
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define Rep(i,v) rep(i,0,(int)v.size()-1)
#define lint long long
#define mod 998244353
#define db double
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define N 10000010
#define K 100020
#define debug(x) cerr<<#x<<"="<<x
#define sp <<" "
#define ln <<endl
using namespace std;
typedef pair<int,int> pii;
typedef set<int>::iterator sit;
typedef unordered_map<int,int> mpii;
typedef unordered_map<int,lint> mpil;
mpil savg;lint sg[N];int fac[K],facinv[K];
mpii savh;int sh[N],k,mu[N],ik[N],sk[N];
bool np[N];int p[N],pre[K],suf[K],y[K];
inline int inn()
{
int x,ch;while((ch=gc)<'0'||ch>'9');
x=ch^'0';while((ch=gc)>='0'&&ch<='9')
x=(x<<1)+(x<<3)+(ch^'0');return x;
}
inline int fast_pow(int x,int k,int ans=1) { for(;k;k>>=1,x=(lint)x*x%mod) (k&1)?ans=(lint)ans*x%mod:0;return ans; }
inline int prelude(int n)
{
mu[1]=1,sg[1]=mu[1]*1,sh[1]=mu[1],ik[1]=1,sk[1]=1;
for(int i=2,c=0;i<=n;i++)
{
if(!np[i]) p[++c]=i,mu[i]=-1,ik[i]=fast_pow(i,k);
sg[i]=sg[i-1]+mu[i]*i,sh[i]=sh[i-1]+mu[i],
sk[i]=sk[i-1]+ik[i],(sk[i]>=mod?sk[i]-=mod:0);
for(int j=1,u=n/i;j<=c&&p[j]<=u;j++)
{
int x=p[j]*i;np[x]=1,ik[x]=(lint)ik[i]*ik[p[j]]%mod;
if(i%p[j]==0) { mu[x]=0;break; } else mu[x]=-mu[i];
}
}
return 0;
}
inline int prelude2(int n)
{
rep(i,1,n) y[i]=y[i-1]+fast_pow(i,k),(y[i]>=mod?y[i]-=mod:0);
rep(i,fac[0]=1,n) fac[i]=(lint)fac[i-1]*i%mod;
facinv[n]=fast_pow(fac[n],mod-2);
for(int i=n-1;i>=0;i--) facinv[i]=(i+1ll)*facinv[i+1]%mod;
return 0;
}
inline lint g(int n)//mu(i)*i
{
if(n<N) return sg[n];lint ans=0;
if(savg.count(n)) return savg[n];
for(int s=2,t;s<=n;s=t+1) t=n/(n/s),ans+=(s+t)*(t-s+1ll)/2*g(n/s);
return savg[n]=1-ans;
}
inline int h(int n)//mu(i)
{
if(n<N) return sh[n];int ans=0;
if(savh.count(n)) return savh[n];
for(int s=2,t;s<=n;s=t+1) t=n/(n/s),ans+=h(n/s)*(t-s+1);
return savh[n]=1-ans;
}
inline int g(int l,int r) { return ((g(r)-g(l-1))%mod+mod)%mod; }
inline int h(int l,int r) { return (h(r)-h(l-1)+mod)%mod; }
inline int S(int x)
{
if(x<N) return sk[x];int n=k+3;static lint xs[3],ans;
pre[0]=suf[n+1]=1,xs[0]=1,xs[1]=-1,ans=0;
for(int i=1;i<=n;i++) pre[i]=(lint)pre[i-1]*(x-i)%mod;
for(int i=n;i>=1;i--) suf[i]=(lint)suf[i+1]*(x-i)%mod;
for(int i=1;i<=n;i++)
ans+=xs[(n-i)&1]*y[i]*pre[i-1]%mod*suf[i+1]%mod*facinv[i-1]%mod*facinv[n-i]%mod;
return int((ans%mod+mod)%mod);
}
inline int IK(int i) { if(i<N) return ik[i];return fast_pow(i,k); }
inline int qs(int n,int kk=k) { int ans=0;rep(i,1,n) (ans+=fast_pow(i,kk))%=mod;return ans; }
int main()
{
int n=inn();k=inn();
lint ans=0;prelude(N-1),prelude2(K-1);
for(int l=1,r,t;l<=n;l=r+1) r=n/(n/l),t=n/l,
ans+=(g(l,r)*(S(t-1)-(lint)IK(t)*t%mod)+h(l,r)*(n+1ll)%mod*IK(t)%mod)%mod;
return !printf("%lld\n",(ans%mod+mod)%mod);
}
C++11(clang++ 3.9) 解法, 执行用时: 1726ms, 内存消耗: 170884K, 提交时间: 2020-04-08 17:09:02
#include<cstdio>
#include<cstring>
#include<unordered_map>
typedef long long LL;
const int md=998244353,N=1e5+7;
int n,k,X[10000008],fac[N],iv[N],ans,pre[N],suf[N];
int P[10000008],pri[10000001/10],tot,mu[10000008],imu[10000008];
bool vis[10000008];
std::unordered_map<int,int>Mu,IMu;
inline void upd(int&a){a+=a>>31&md;}
inline int pow(int a,int b){
int ret=1;
for(;b;b>>=1,a=(LL)a*a%md)if(b&1)ret=(LL)ret*a%md;
return ret;
}
inline void init(const int n){
P[1]=mu[1]=1;
for(int i=2;i<=n;++i){
if(!vis[i])pri[++tot]=i,P[i]=pow(i,k),mu[i]=-1;
for(int j=1;j<=tot&&i*pri[j]<=n;++j){
vis[i*pri[j]]=1,P[i*pri[j]]=(LL)P[i]*P[pri[j]]%md;
if(i%pri[j]==0)break;
mu[i*pri[j]]=-mu[i];
}
}
for(int i=1;i<=n;++i)upd(X[i]=P[i]+X[i-1]-md);
}
inline int query(int x){
if(x<=10000000)return X[x];
int ret=0;
for(int i=1;i<=k+3;++i)
pre[i]=pre[i-1]*(LL)(x-i+md)%md;
for(int i=k+3;i;--i)
suf[i]=suf[i+1]*(LL)(x-i+md)%md;
for(int i=1;i<=k+3;++i){
int y=X[i]*(LL)pre[i-1]%md*suf[i+1]%md*iv[i-1]%md*iv[k+3-i]%md;
if((k+3-i)&1)upd(y=-y);
upd(ret+=y-md);
}
return ret;
}
inline int sumd(int x){return(x+1LL)*x/2%md;}
int getmu(int n){
if(n<=10000000)return mu[n];
if(Mu.count(n))return Mu[n];
int&S=Mu[n];S=0;
for(unsigned l=2,r;l<=n;l=r+1){
r=n/(n/l);
S=(S+(r-l+1LL)*getmu(n/l))%md;
}
upd(S=1-S);
return S;
}
int getimu(int n){
if(n<=10000000)return imu[n];
if(IMu.count(n))return IMu[n];
int&S=IMu[n];S=0;
for(int l=2,r;l<=n;l=r+1){
r=n/(n/l);
S=(S+((LL)sumd(r)-sumd(l-1)+md)*getimu(n/l))%md;
}
upd(S=1-S);
return S;
}
inline int solve(int t){
return(t*(LL)query((n+1)/t-1)+(LL)((n+1)%t)*pow((n+1)/t,k))%md;
}
int main(){
scanf("%d%d",&n,&k);
init(10000000);
pre[0]=suf[k+4]=1;
for(int i=*fac=1;i<=k+3;++i)fac[i]=(LL)i*fac[i-1]%md;
iv[k+3]=pow(fac[k+3],md-2);
for(int i=k+2;~i;--i)iv[i]=(i+1LL)*iv[i+1]%md;
if(n<=5000000){
for(int i=1;i<=n;++i)
ans=(ans+(LL)(mu[i]+md)*solve(i))%md;
printf("%d\n",ans);
}else{
for(int i=1;i<=5000000;++i)
ans=(ans+(LL)(mu[i]+md)*solve(i))%md;
++n;
for(int i=1;i<=10000000;++i)
imu[i]=(imu[i-1]+(LL)i*mu[i]+md)%md,mu[i]=(mu[i]+mu[i-1]+md)%md;
for(int l=5000001,r;l<n;l=r+1){
r=n/(n/l);
if(r==n)--r;
int sum_mu=getmu(r)-getmu(l-1);upd(sum_mu);
int sum_imu=getimu(r)-getimu(l-1);upd(sum_imu);
ans=(ans+(LL)sum_imu*query(n/l-1)%md)%md;
int t=pow(n/l,k),x=0;
x=(x+(LL)n*t%md*sum_mu)%md;
x=(x-(LL)(n/l)*t%md*sum_imu%md+md)%md;
upd(ans+=x-md);
}
printf("%d\n",ans);
}
return 0;
}