2020杭电多校联合训练(第六场)
in 杭电多校多校训练 with 0 comment

2020杭电多校联合训练(第六场)

in 杭电多校多校训练 with 0 comment

摘要

/ABCDEFGHIJK
场上
zyj
wrf
lmj

题目

A.Road To The 3rd Building

lmj (00:49:22) +1

题意

在长度为n的序列中任意选一段区间,贡献为区间的点权和的平均值,求贡献的期望

题解

考虑每个点对答案的贡献,可以发现第i个点的贡献为$s[i]*$
$(\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+……+\frac{1}{n-i+1}+$
$\frac{1}{2}+\frac{1}{3}+……+\frac{1}{(n-i+2)}+$
$……$
$+\frac{1}{i}+\frac{1}{(i+1)}+……+\frac{1}{n})$
然后可以发现在遍历i时,后面这个求和的变化可以预处理然后O(1)获得,即可得到所有情况下的总答案,除以情况数即为期望

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
ll s[N];
ll pre[N];
ll inv[N];
void work()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&s[i]);
    }
    ll tmp=0;
    ll ans=0;
    for(int i=1;i<=n;i++){
        tmp=(tmp+pre[n]-pre[i-1]-pre[n]+pre[n-i+1])%p;
        tmp=(tmp+p)%p;
        ans=(ans+s[i]*tmp%p)%p;
        //printf("%lld\n",ans);
    }
    ans=ans*qpow((1ll*n*(n+1)/2)%p,p-2)%p;
    printf("%lld\n",ans);
}
int main()
{
    inv[0]=inv[1]=1;
    for(int i=2;i<N;i++){
        inv[i]=((p-p/i)*inv[p%i])%p;
    }
    pre[0]=0;
    for(int i=1;i<N;i++){
        pre[i]=(pre[i-1]+inv[i])%p;
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

B.Little Rabbit's Equation

wrf (00:59:55) +3

题意

题解

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int inf=0x3f3f3f3f;
const ll mint=0x7fffffff;
const ll linf=1000000000000000000LL;
const ll mod=998244353LL;
const double eps=1e-3;

const int N=20;

inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char ch[N],c1[N],c2[N],c3[N];

int solve()
{
    int p1=0,p2=0,p3=0,pos=1;
    char op;
    int mx=0;
    
    for(int i=0;ch[i]!='\0';i++)
    {
        if(ch[i]=='+' || ch[i]=='-' || ch[i]=='*' || ch[i]=='/')
        {
            c1[p1]='\0';
            op=ch[i];
            pos=2;
        }
        else if(ch[i]=='=')
        {
            c2[p2]='\0';
            pos=3;
        }
        else
        {
            if(pos==1)
            {
                c1[p1]=ch[i];
                p1++;
            }
            if(pos==2)
            {
                c2[p2]=ch[i];
                p2++;
            }
            if(pos==3)
            {
                c3[p3]=ch[i];
                p3++;
            }

            if(ch[i]>='0' && ch[i]<='9') mx=max(mx,ch[i]-'0');
            else mx=max(mx,ch[i]-'A'+10);
        }
    }
    c3[p3]='\0';

    for(int r=max(2,mx+1);r<=16;r++)
    {
        ll i1=0,i2=0,i3=0;

        for(int i=0;c1[i]!='\0';i++)
        {
            int now=0;
            if(c1[i]>='0' && c1[i]<='9') now=c1[i]-'0';
            else now=c1[i]-'A'+10;
            i1*=r;
            i1+=now;
        }
        for(int i=0;c2[i]!='\0';i++)
        {
            int now=0;
            if(c2[i]>='0' && c2[i]<='9') now=c2[i]-'0';
            else now=c2[i]-'A'+10;
            i2*=r;
            i2+=now;
        }
        for(int i=0;c3[i]!='\0';i++)
        {
            int now=0;
            if(c3[i]>='0' && c3[i]<='9') now=c3[i]-'0';
            else now=c3[i]-'A'+10;
            i3*=r;
            i3+=now;
        }
        if(op=='+' && i1+i2==i3) return r;
        if(op=='-' && i1-i2==i3) return r;
        if(op=='*' && i1*i2==i3) return r;
        if(op=='/' && i1==i2*i3) return r;
    }
    return -1;
}

int main(void)
{
    //ios::sync_with_stdio(false);
    
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    
    while(~scanf("%s",ch))
    {
        printf("%d\n",solve());
    }
    
    return 0;
}

C.Borrow

lmj (赛后)

题意

给定x,y,z,每次操作可以选最大的数中的一个,将一个1转移到另外2个数中,求使得三个数相同的期望操作数

题解

假设$x<=y<=z$,如果$y>=average$那么考虑最小值,每次操作有$1/2$的概率变大1,有$1/2$的概率不变,可以得到期望为$2*(average-x)$。
如果$y<average$,那么考虑将其变成上面这种情况,分别考虑$x$和$y$,在第$i$步到达$average$的概率,为$\frac{C_{i-1}^{average-y-1}}{2^i}$,次数为$i$次,此时转移到第一种情况,求一下另一个值多大即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=1e6+5;
const int p=998244353;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int a[4];
ll pre[N];
ll inv[N];
ll C(int n,int m)
{
    if(n<m)return 0;
    return pre[n]*inv[m]%p*inv[n-m]%p;
}
void work()
{
    scanf("%d%d%d",&a[1],&a[2],&a[3]);
    sort(a+1,a+4);
    if((a[1]+a[2]+a[3])%3){
        printf("-1\n");return;
    }
    int tmp=(a[1]+a[2]+a[3])/3;
    if(a[2]>=tmp){
        printf("%d\n",(tmp-a[1])*2%p);
    }else{
        ll ans=0;
        for(int i=tmp-a[2];i<tmp*2-a[1]-a[2];i++){
            ans=(ans+C(i-1,tmp-a[2]-1)*qpow(qpow(2,i),p-2)%p*(i+(tmp*2-a[1]-a[2]-i)*2)%p)%p;
        }
        for(int i=tmp-a[1];i<tmp*2-a[1]-a[2];i++){
            ans=(ans+C(i-1,tmp-a[1]-1)*qpow(qpow(2,i),p-2)%p*(i+(tmp*2-a[1]-a[2]-i)*2)%p)%p;
        }
        printf("%lld\n",ans);
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    pre[0]=1;
    for(int i=1;i<N;i++){
        pre[i]=pre[i-1]*i%p;
    }
    inv[N-1]=qpow(pre[N-1],p-2);
    for(int i=N-2;i>=0;i--){
        inv[i]=inv[i+1]*(i+1)%p;
    }
    //cin>>T;
    while(T--){
        work();
    }
}

D.Asteroid in Lov

zyj (赛后) +1

题意

给出三种颜色的点若干个,问你从每种颜色中选出一个构成的三角形面积最大值。$(n \leq 3000)$

题解

这题是个假题,正确写法会TLE,就先介绍以下假做法吧。
做法就是$n^2$枚举两种颜色的直线,然后去找距离这条直线最远的点。
那么有一个发现:

确定一条直线后,剩下那个点一定只能在该颜色的凸包上。

于是我们随便找一个颜色构造凸包,然后枚举剩下两种颜色的直线,可以发现凸包上的点到直线的距离是两个单峰函数,于是考虑三分凸包上的点(至于为什么这个三分是正确的,我只能说数据随机)。

其实不三分而是直接枚举凸包上的点也能卡过去的

再来说说正确的做法。
之前的做法会出现错误主要是因为那是个双峰函数,于是考虑变成两个独立的单峰。
首先将剩下两种颜色的点极角排序,不难发现此时枚举直线时凸包上变化的点是一段连续区间。于是考虑用线段树维护这个区间直接求最大值。但是此算法由于常数太大不能通过出题人的数据。

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
#define ld long double
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
const ld eps=1e-8;
const int maxP=1100;
inline ld sqr(ld d){return d*d;}
inline int dcmp(ld d){return d<-eps?-1:d>eps;}
struct Point{
    ld x,y;
    Point(){}
    Point(const ld &_x,const ld &_y):x(_x),y(_y){}
    bool operator <(const Point &p)const{return y+eps<p.y||(y<p.y+eps&&x+eps<p.x);}
    Point operator -(const Point &p)const{return Point(x-p.x,y-p.y);}
    Point operator *(const ld &k)const{return Point(x*k,y*k);}
    ld operator *(const Point &p)const{return x*p.y-y*p.x;}
    ld Distance(Point p){return sqrt(sqr(p.x-x)+sqr(p.y-y));}
};
struct Line{
    Point a,b;
    Line(){}
    Line(const Point &_a,const Point &_b):a(_a),b(_b){}
    ld operator*(const Point &p)const{return(b-a)*(p-a);}
    ld len(){return a.Distance(b);}
    ld DisPointToLine(const Point &p){return fabs((*this)*p)/a.Distance(b);}
};
struct Polygon{
    int n;
    Point p[maxP];
    Polygon(){n=0;}
    void push(const Point &pp){p[n++]=pp;}
    void getConvex(Polygon &c){
        sort(p,p+n);c.n=n;
        if(n==0)return;c.p[0]=p[0];
        if(n==1)return;c.p[1]=p[1];
        if(n==2)return;
        int &top=c.n;top=1;
        for(int i=2;i<n;i++){
            while(top&&dcmp((c.p[top]-p[i])*(c.p[top-1]-p[i]))>=0) top--;
            c.p[++top]=p[i];
        }
        int temp=top;
        c.p[++top]=p[n-2];
        for(int i=n-3;i>=0;i--){
            while(top!=temp&&dcmp((c.p[top]-p[i])*(c.p[top-1]-p[i]))>=0) top--;
            c.p[++top]=p[i];
        }
    }
};
int n;
vector<Point> p[3];
Polygon tb;
ld calc(int x,Line &l){return l.DisPointToLine(tb.p[x]);}
ld check(Point &x,Point &y){
    int n=tb.n;ld h=0;
    Line L=Line(x,y);
    int l=0,r=n-1;
    while(l<r){
        int lmid=l+(r-l)/3,rmid=r-(r-l)/3;
        if(calc(lmid,L)<=calc(rmid,L)) l=lmid+1;
        else r=rmid-1;
    }h=max({h,calc(l,L),calc(r,L)});
    return h;
}
void solve(){
    scanf("%d",&n);
    rep(i,0,2) p[i].clear();
    rep(i,1,n){
        int x,y,c;scanf("%d%d%d",&x,&y,&c);
        p[c].pb(Point(x,y));
    }int a=1,b=2,c,mx=0;
    rep(i,0,2) if(p[i].size()>mx) mx=p[i].size(),c=i;
    if(c==1) a=0;if(c==2) a=0,b=1;
    Polygon col;tb.n=0;
    for(auto u:p[c]) col.push(u);
    col.getConvex(tb);
    ld ans=0;
    for(Point x:p[a]) for(Point y:p[b]){
        ld len=x.Distance(y);
        ld h=check(x,y);
        ans=max(ans,len*h);
    }
    ll res=(ll)ans;
    printf(res&1?"%lld.5\n":"%lld.0\n",res/2);
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}

E.Fragrant numbers

lmj 赛后

题意

给定一个无限长的循环1145141919,可以在其中插入括号、加号、乘号,求最短多少长度可以表示出n

题解

通过比较粗略的打表可以得到所有的答案小于15,对前15进行区间dp打表即可。

代码

打表程序删了,不写了


F.A Very Easy Graph Problem

zyj+lmj (01:19:06) +1

题意

给定m条边,第i条边的边权为$2^i$,然后每个点有颜色0或者1,求$\sum_{i=1}^n\sum_{j=1}^n dis(i,j)*(a[i] \oplus a[j])$

题解

可以发现,在加入第$i$条边的的时候,已经连通的部分的最短路并不会受到这条边的影响,因为前$i-1$条的和也是小于第$i$条边的。那么在加入边的时候,考虑该边的两个点是否已经连通,如果已经连通则这条边没用,最后就可以建成一棵生成树,在生成树上dfs枚举每条边求解即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
const ll INF=(ll)1e18;
int n,m;
struct Edge{
    int v,id;ll w;int nxt;
}g[maxn<<1];
int head[maxn],edge_tot;
void init(){rep(i,0,n) head[i]=0;edge_tot=1;}
void addedge(int u,int v,ll w,int id){g[edge_tot]={v,id,w,head[u]};head[u]=edge_tot++;}
vector<int> v,v0;
ll qpow(ll x,int n){
    ll res=1;
    while(n){
        if(n&1) res=(res*x)%mod;
        x=(x*x)%mod;n>>=1;
    } return res;
}
int fa[maxn];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
struct node{int u,v,id;ll w;}e[maxn];
int n0,n1,x[maxn];
int sum[maxn][2];
ll ans=0;
void dfs(int u,int fa){
    sum[u][0]=sum[u][1]=0;
    for(int i=head[u];i;i=g[i].nxt){
        if(g[i].v!=fa){
            dfs(g[i].v,u);
            ans=(ans+1ll*sum[g[i].v][0]*(n1-sum[g[i].v][1])%mod*g[i].w%mod)%mod;
            ans=(ans+1ll*sum[g[i].v][1]*(n0-sum[g[i].v][0])%mod*g[i].w%mod)%mod;
            sum[u][0]+=sum[g[i].v][0];
            sum[u][1]+=sum[g[i].v][1];
        }
    }
    if(x[u]==1){
        sum[u][1]++;
    }else{
        sum[u][0]++;
    }
}
void solve(){
    scanf("%d%d",&n,&m);init();n0=n1=0;
    ans=0;
    rep(i,1,n){
        scanf("%d",&x[i]);
        if(x[i]) n1++;
        else n0++;
    }
    rep(i,1,m){
        int u,v;scanf("%d%d",&u,&v);
        ll w=qpow(2,i);e[i]={u,v,i,w};
    }
    rep(i,1,n) fa[i]=i;
    rep(i,1,m){
        int u=find(e[i].u),v=find(e[i].v);
        if(u!=v){
            fa[u]=v;
            addedge(e[i].u,e[i].v,e[i].w,e[i].id);
            addedge(e[i].v,e[i].u,e[i].w,e[i].id);
        }
    }dfs(1,0);
    printf("%lld\n",ans);
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}

G.A Very Easy Math Problem

lmj (04:03:21) +3

题意


$$\sum_{a_1=1}^n\sum_{a_2=1}^n……\sum_{a_x=1}^n \prod_{j=1}^n a_j^k f(gcd(a_1,a_2,……,a_x))*gcd(a_1,a_2,\cdot,a_x)$$
如果存在某个质数$k$使得$x mod k^2==0$那么$f(x)=0$,否则$f(x)=1$

题解

$\sum\limits_{a_1=1}^n\sum\limits_{a_2=1}^n……\sum\limits_{a_x=1}^n \prod\limits_{j=1}^x a_j^k*f(gcd(a_1,a_2,……,a_x))*gcd(a_1,a_2,……,a_x)$
$=\sum\limits_{a_1=1}^n\sum\limits_{a_2=1}^n……\sum\limits_{a_x=1}^n \prod\limits_{j=1}^x a_j^k*μ(gcd(a_1,a_2,……,a_x))^2*gcd(a_1,a_2,……,a_x)$
提取gcd
$=\sum\limits_{d=1}^n d^{kx}*\sum\limits_{a_1=1}^{\frac{n}{d}}\sum\limits_{a_2=1}^{\frac{n}{d}}……\sum\limits_{a_x=1}^{\frac{n}{d}} \prod\limits_{j=1}^{x} a_j^k*μ(d)^2*d*[gcd(a_1,a_2,……,a_x)==1]$
$=\sum\limits_{d=1}^n d^{kx}*μ(d)^2*d*\sum\limits_{a_1=1}^{\frac{n}{d}}\sum\limits_{a_2=1}^{\frac{n}{d}}……\sum\limits_{a_x=1}^{\frac{n}{d}} \prod\limits_{j=1}^{x} a_j^k*[gcd(a_1,a_2,……,a_x)==1]$
$=\sum\limits_{d=1}^n d^{kx}*μ(d)^2*d*\sum\limits_{g=1}^{n/d}\sum\limits_{g|(n/d)}\prod\limits_{j=1}^x a_j^k$
$=\sum\limits_{d=1}^n d^{kx}*μ(d)^2*d*\sum\limits_{g=1}^{n/d}μ(g)*g^{kx}*\sum\limits_{a_1=1}^{\frac{n/d}{g}}\sum\limits_{a_2=1}^{\frac{n/d}{g}}……\sum\limits_{a_x=1}^{\frac{n/d}{g}} \prod_{j=1}^x a_j^k$
$=\sum\limits_{d=1}^n d^{kx}*μ(d)^2*d*\sum\limits_{g=1}^{n/d}μ(g)*g^{kx}*\sum\limits_{i=1}^{\frac{n/d}{g}} i^{kx}$

代码

#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int pri[N],flg[N],mu[N];
int sum[N];
int sum1[N];
int sum2[N];
int g[N];
int k,x;
void init(int n) {
    mu[1] = 1;
    int tot = 0;
    for (int i = 2; i <= n; ++i) {
        if (!flg[i]) pri[++tot] = i, mu[i] = -1;
        for (int j = 1; j <= tot && i * pri[j] <= n; ++j) {
            flg[i * pri[j]] = 1;
            if (i % pri[j] == 0) {
                mu[i * pri[j]] = 0;
                break;
            }
            mu[i * pri[j]] = -mu[i];
        }
    }
    for (int i = 1; i <= n; ++i){
        sum[i]=(sum[i-1]+qpow(i,1ll*k*x+1)*mu[i]*mu[i])%p;
        sum1[i]=(sum1[i-1]+qpow(i,1ll*k*x)*mu[i]%p+p)%p;
        sum2[i]=(sum2[i-1]+qpow(i,k))%p;
    }
    for(int i=1;i<=n;i++){
        sum2[i]=qpow(sum2[i],x);
    }
    
}
int cal1(int n)
{
    return sum2[n];
}
int cal(int n)
{
    int ans=0;
    for(int i=1,j;i<=n;i=j+1){
        j=n/(n/i);
        ans=(ans+1ll*(sum1[j]-sum1[i-1])*cal1(n/i)%p+p)%p;
    }
    return ans;
}
void work()
{
    int n;
    scanf("%d",&n);
    int ans=0;
    for(int i=1,j;i<=n;i=j+1){
        j=n/(n/i);
        ans=(ans+1ll*(sum[j]-sum[i-1])*g[n/i]%p+p)%p;
    }
    printf("%d\n",ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d%d%d",&T,&k,&x);
    // T=10000,k=1000000000,x=1000000000;
    init(2e5);
    for(int i=1;i<=2e5;i++){
        g[i]=cal(i);
    }
    // cin>>T;
    while(T--){
        work();
    }
}

H.Yukikaze and Smooth numbers

lmj 赛后

题意

定义k光滑数为所有质因数都小于等于k的数,求n里面k光滑数的个数。

题解

首先根据容斥 可以化为$n-\sum_{p>m}μ(i)*(n/i)$,p为i的最小质因数。
对于这个式子,考虑去筛$μ(i)$,要求的就是所有质因数大于等于k的莫比乌斯函数的和,考虑使用min25筛处理。
如果$n<=k$,显然答案是n。
如果$n>k$,分为两种情况,$k*k>n$和$k*k<=n$。
先考虑$k*k<=n$的情况,即分块的时候求解$S(r,p_i)$和$S(l-1,p_i)$,$p_i$为第一个大于K的质因数。
然后对于$k*k>n$的情况,可以发现只要出现一个大于k的质数就不合法,那么就是在分块的时候求解区间有多少个质数即可,需要注意的是,由于区间是从$k+1$开始的,这并不一定满足是一个$n/l+1$的形式,所以对于第一个块需要特殊处理一下。

代码

#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e6+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
bool prime[N];
int tot;
int Sqr,n,K;
int pri[N],id1[N],id2[N],g[N],w[N],m,sp1[N];
void pre(int n)
{
    tot=0;
    prime[1]=1;
    for(int i=2;i<=n;i++){
        if(!prime[i]){
            pri[++tot]=i;
            sp1[tot]=sp1[tot-1]+1;
        }
        for(int j=1;j<=tot&&i*pri[j]<=n;j++){
            prime[i*pri[j]]=1;
            if(i%pri[j]==0)break;
        }
    }
}
int f(int x)
{
    return x==1?1:0;
}
int S(int x,int y)
{
    if(x<=1||x<pri[y])return 0;
    //if(mp.count({x,y}))return mp[{x,y}];
    int k=(x<=Sqr)?id1[x]:id2[n/x];
    int ret=g[k]-sp1[y-1];
    for(int i=y;i<=tot&&pri[i]*pri[i]<=x;i++){
        int t1=pri[i],t2=pri[i]*pri[i];
        for(int e=1;t2<=x;++e,t1=t2,t2*=pri[i]){
            ret-=S(x/t1,i+1)*f(e)+f(e+1);
        }
    }
    //return mp[{x,y}]=ret;
    return ret;
}
void pre1(int n)
{
    m=0;
    Sqr=sqrt(n);
    pre(Sqr);
    for(int i=1,j;i<=n;i=j+1){
        j=n/(n/i),w[++m]=n/i;
        g[m]=w[m]-1;
        if(w[m]<=Sqr)id1[w[m]]=m;
        else id2[j]=m;
    }
    for(int j=1;j<=tot;j++){
        for(int i=1;i<=m&&pri[j]*pri[j]<=w[i];i++){
            int k=(w[i]/pri[j]<=Sqr)?id1[w[i]/pri[j]]:id2[n/(w[i]/pri[j])];
            g[i]-=g[k]-sp1[j-1];
        }
    }
}
void work()
{
    if(1ll*K*K>n){
        int ans=n;
        int l=K+1,r=n/(n/l);
        pre1(K);
        int tmp=g[((l-1)<=Sqr)?id1[l-1]:id2[K/(l-1)]];
        pre1(n);
        tmp=g[(r<=Sqr)?id1[r]:id2[n/r]]-tmp;
        ans-=tmp*(n/l);
        //printf("%lld\n",ans);
        l=r+1;
        for(;l<=n;l=r+1){
            r=n/(n/l);
            ans-=(n/l)*(g[(r<=Sqr)?id1[r]:id2[n/r]]-g[((l-1)<=Sqr)?id1[l-1]:id2[n/(l-1)]]);
            //printf("%lld\n",ans);
        }
        printf("%d\n",ans);return;
    }
    //mp.clear();
    pre1(n);
    int t=1;
    int ans=n;
    while(t<=tot&&pri[t]<=K)t++;
    //printf("%d %d\n",t,tot);
    for(int i=K+1,j;i<=n;i=j+1){
        j=n/(n/i);
        ans-=(n/i)*(S(j,t)-S(i-1,t));
        //printf("---%d %d %d %lld %lld\n",j,i-1,t,S(j,t),S(i-1,t));
    }
    printf("%d\n",ans);
}
int main()
{
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        scanf("%d%d",&n,&K);
        if(n<=K){
            printf("%d\n",n);continue;
        }
        work();
    }
}

I.Divisibility

wrf (00:06:44) +0

题意

题解

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int inf=0x3f3f3f3f;
const ll mint=0x7fffffff;
const ll linf=1000000000000000000LL;
const ll mod=998244353LL;
const double eps=1e-3;

const int N=100020;

inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int main(void)
{
    //ios::sync_with_stdio(false);
    
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    
    for(int _=read();_>0;_--)
    {
        ll b=read(),x=read();

        if((b-1)%x==0) printf("T");
        else printf("F");
        printf("\n");
    }
    
    return 0;
}

J.Expectation

wrf (01:38:43) +0

题意

题解

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int inf=0x3f3f3f3f;
const ll mint=0x7fffffff;
const ll linf=1000000000000000000LL;
const ll mod=998244353LL;
const double eps=1e-3;

const int N=100020;

inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}




void exgcd(ll a,ll b,ll& x,ll& y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return ;
    }

    exgcd(b,a%b,x,y);
//cout<<a<<" "<<b<<" "<<x<<" "<<y<<"^"<<endl;
    ll k=x;
    x=y;
    y=k-(a/b)*y;
//cout<<a<<" "<<b<<" "<<x<<" "<<y<<"$"<<endl;
    return ;
}

ll inv(ll a,ll p)
{
    if(a==0)
    {
        return 0LL;
    }
    ll x,y;

    exgcd(a,p,x,y);

    return (x%p+p)%p;
}


typedef vector<ll> vec;
typedef vector<vec> matrix;

void init(vec& v,int n)
{
    v.resize(n);
}
void init(matrix& mat,int n)
{
    mat.resize(n);
    for(int i=0;i<n;i++) mat[i].resize(n);
}

ll det(matrix& mat)
{
    ll ans=1;
    int n=mat.size();
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            if(mat[j][i]!=0)
            {
                ll tr=mat[i][i]*inv(mat[j][i],mod)%mod;
                for(int k=i;k<n;k++)
                {
                    mat[j][k]=(mat[j][k]*tr%mod+mod-mat[i][k])%mod;
                }
                ans=ans*inv(tr,mod)%mod;
            }
        }
    }

    for(int i=0;i<n;i++)
    {
        ans=ans*mat[i][i]%mod;
    }
    return ans;
}





int main(void)
{
    //ios::sync_with_stdio(false);
    
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    
    for(int _=read();_>0;_--)
    {
        int n=read(),m=read();
        int mxt=0;
        vector<int> l(m),r(m),t(m);
        for(int i=0;i<m;i++) l[i]=read(),r[i]=read(),t[i]=read();

        ll u,d=0;
        matrix tu;
        init(tu,n-1);
        for(int k=0;k<m;k++)
        {
            int i=l[k]-1,j=r[k]-1;
            if(t[k]>0) 
            {
                if(i<n-1 && j<n-1) tu[i][j]++;
                if(i<n-1) tu[i][i]--;
            }
            swap(i,j);
            if(t[k]>0) 
            {
                if(i<n-1 && j<n-1) tu[i][j]++;
                if(i<n-1) tu[i][i]--;
            }
            mxt=max(mxt,t[i]);
        }
        for(int i=0;i<n-1;i++)
        {
            if(tu[i][i]<0) tu[i][i]+=mod;
        }
        u=det(tu);

        for(int rr=1;rr<=mxt;rr<<=1)
        {
            matrix ku;
            init(ku,n-1);
            for(int k=0;k<m;k++)
            {
                int i=l[k]-1,j=r[k]-1;
                if(t[k]&rr) 
                {
                    if(i<n-1 && j<n-1) ku[i][j]++;
                    if(i<n-1) ku[i][i]--;
                }
                swap(i,j);
                if(t[k]&rr) 
                {
                    if(i<n-1 && j<n-1) ku[i][j]++;
                    if(i<n-1) ku[i][i]--;
                }
            }
            // for(int i=0;i<n;i++)
            // {
            //     for(int j=0;j<n;j++)
            //     {
            //         if(ori[i][j]&r) 
            //         {
            //             if(i<n-1 && j<n-1) ku[i][j]++;
            //             if(i<n-1) ku[i][i]--;
            //         }
            //     }
            // }
            for(int i=0;i<n-1;i++)
            {
                if(ku[i][i]<0) ku[i][i]+=mod;
            }
            d=(d+det(ku)*rr%mod)%mod;
        }

        printf("%lld\n",d*inv(u,mod)%mod);
    }
    
    return 0;
}

K.Kirakira

题意

题解

代码

Responses