11.9贺题大赛

· · 个人记录

四道题三道原题，牛的。

T1

同NOIP2018 旅行。

暴力枚举每条边即可。

T2

同NOIP2017 天天爱跑步。

树上差分，考试的时候真，没时间写。

T3

同NOIP2016 愤怒的小鸟

考虑一个只有两个未知量的二次函数能被两个点确定，我们暴力枚举每个点，特判x_i=x_j或a\geq0的情况。

然后就变成了一个显然的区间DP.

#include <bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
inline void file(){
    freopen("terrorist.in","r",stdin);
    freopen("terrorist.out","w",stdout);
}
#define N 18
#define M (1<<N)
const double eps=1e-6;
int f[M];
int g[N][N];
int lb[M];
struct node{
    double x,y;
}q[N];
inline int cmp(double a,double b){
    if(fabs(a-b)<=eps)return 0;
    return a<b?-1:1;
}
inline void work(){
    int n=read(),m=read();
    for(int i=0;i<n;i++){
        scanf("%lf %lf",&q[i].x,&q[i].y); 
    }
    for(int i=0;i<(1<<n)-1;i++){
        for(int j=0;j<n;j++){
            if(!(i>>j&1)){lb[i]=j;break;}
        }
    }
    memset(g,0,sizeof(g));
    for(int i=0;i<n;i++){
        g[i][i]=(1<<i);
        for(int j=0;j<n;j++){
            if(!cmp(q[i].x,q[j].x))continue;
            double xx1=q[i].x,yy1=q[i].y,xx2=q[j].x,yy2=q[j].y;
            double b=(yy1*xx2*xx2-yy2*xx1*xx1)/(xx2*xx2*xx1-xx2*xx1*xx1);
            double a=(yy1-b*xx1)/(xx1*xx1);
            //cout<<i<<' '<<j<<' '<<a<<' '<<b<<endl;
            if(a>=0)continue;
            int fl=0;
            for(int k=0;k<n;k++){
                double dx=q[k].x,dy=q[k].y;
                if(!cmp(dy,a*dx*dx+b*dx))fl+=(1<<k);
            }
            g[i][j]=fl;
        }
    }
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=0;i<(1<<n)-1;i++){
        for(int j=0;j<n;j++)
        f[i|g[lb[i]][j]]=min(f[i|g[lb[i]][j]],f[i]+1);
    }
    printf("%d\n",f[(1<<n)-1]);
}
int main(void){
    file();
    int T=read();
    while(T--)work();

}
/*
1
5 0
2.72 2.72
2.72 3.14
3.14 2.72
3.14 3.14
5.00 5.00
*/

T4

求

\prod_{i_1=1}^n\prod_{i_2=1}^n...\prod_{i_k=1}^n\frac{i_1i_2i_3...i_k}{\gcd(i_1,i_2,...,i_k)} $n\leq 3\times 10^5,k\leq 10^{18},T\leq 2\times 10^3

sol

考虑把分子分母拆开来求（反正我不会合起来QAQ）

对于分子。

\prod_{i_1=1}^n\prod_{i_2=1}^n...\prod_{i_k=1}^ni_1i_2...i_k=(n!)^{kn^{k-1}}

主要是考虑分母

\prod_{i_1=1}^n\prod_{i_2=1}^n...\prod_{i_k=1}^n\gcd(i_1,i_2,...i_k)=\prod_{d=1}^nd^{\sum_{i_1=1}^n \sum_{i_2=1}^{n}...\sum_{i_k=1}^n[\gcd(i_1,i_2...i_k)=d]}

我们单独考虑指数，这就是一个很naive的莫反，最后得到

\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)(\lfloor \frac{n}{dp}\rfloor)^k

如果直接求上式，考虑在整除分块下整除分块，最终复杂度为O(n^{\frac{3}{4}}logk)会被卡，所以考虑预处理(\lfloor \frac{n}{dp}\rfloor)^k，有一个性质，即(\lfloor \frac{n}{a}\rfloor)^k在只会有\sqrt n个取值。我们通过一次整除分块预处理出(\lfloor \frac{n}{dp}\rfloor)^k的值，把它丢进一个哈希表，每次询问时O(1)取出即可。最终的logn与\sqrt n做加法，总复杂度为O(Tn^{\frac{3}{4}})

#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
inline void file(){
    freopen("lcm.in","r",stdin);
    freopen("lcm.out","w",stdout);
}
const int mod=998244353;
inline int ksm(int a,int b,int mod){
    int res=1ll;
    while(b){
        if(b&1)res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res%mod;
}
#define N 1000005
#define S 1005
int s,n,k;
int mu[N+5],fac[N+5],invfac[N+5];
bool vis[N+5];
int p[N],num;
int idiv[S],adiv[S],cnt;
int hsh[(S<<1)+5];
inline int &id(int x){
    return x<=s?idiv[x]:adiv[n/x];
}
inline void pre(){
    mu[1]=fac[0]=fac[1]=1;
    for(int i=2;i<=N;i++){
        fac[i]=fac[i-1]*i%mod;
        if(!vis[i]){
            p[++num]=i;
            mu[i]=mod-2;
        }
        for(int j=1;j<=num&&p[j]*i<=N;j++){
            vis[i*p[j]]=1;
            if(i%p[j]==0)break;
            mu[i*p[j]]=(mod-1-mu[i])%(mod-1);
        }
        mu[i]=(mu[i]+mu[i-1])%(mod-1);
    }
    invfac[N]=ksm(fac[N],mod-2,mod);
    for(int i=N;i;i--){
        invfac[i-1]=invfac[i]*i%mod;
    }
}
inline void work(){
    n=read(),k=read();
    int fz=ksm(fac[n],(k%(mod-1))*ksm(n,k-1,mod-1)%(mod-1),mod);
     //cout<<fz<<endl;
    s=sqrt(n);
    int fm=1ll;
    cnt=0;
    for(int l=1,r;l<=n;l=r+1){
        r=n/(n/l);
        hsh[id(n/l)=++cnt]=ksm(n/l,k,mod-1);
    }

    for(int l=1,r;l<=n;l=r+1){
        r=n/(n/l);
        int lsw=0,at=n/l;
        for(int L=1,R;L<=at;L=R+1){
            R=at/(at/L);
            lsw=(lsw+hsh[id(at/L)]*(mu[R]-mu[L-1]+mod-1))%(mod-1);  
        }
        fm=fm*ksm(fac[r]*invfac[l-1]%mod,lsw,mod)%mod;
    }
    printf("%lld\n",fz*ksm(fm,mod-2,mod)%mod);
}
signed main(void){
    file();
    pre();
    int T=read();
    while(T--)work();
    return 0;
}