2024/11/19 洛谷模拟赛

Chancylaser · 2024-11-20 08:22:34 · 个人记录

T1

T1卡我常？？？

首先观察式子 p\times i+q\times j=C，暴力的话得知道三个求得另外一个，询问是给了你 p,q 的，你得枚举个 i 或者 j，显然过不去。~~但是根据实测洛谷这样写就过了~~。

首先发现如果 max(p,q)\ge \sqrt C，我们是可以直接枚举的，因为最多枚举 \frac{C}{\sqrt C}=\sqrt C 次。否则我们这么枚举是很容易超时的。

那么直接考虑跟根号分治，考虑另一种情况，即 max(p,q)<\sqrt C，由于这种情况下 p\times q<C 所以我们可以预处理出所有 p,q < \sqrt C 的情况。

然而我们还需要枚举一层 i，那么综合时间复杂度为 O(n\sqrt n\log n)。需要极限卡常才能通过。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=3e5+5, MOD=998244353;
const int mx=152;

namespace IO {
    char buff[30000000],*p1=buff,*p2=buff;
    char get_c(){if(p1==p2)p2=(p1=p2)+fread(buff,1,30000000,stdin);return *p1++;}
    template<typename T>void read(T &x)
    {
        x=0;short sign=1;
        char ch=IO::get_c();
        while(ch<48||ch>57){if(ch==45)sign=-1;ch=get_c();}
        while(ch>=48&&ch<=57)x=(x<<3)+(x<<1)+ch-'0',ch=get_c();
        x*=sign;
    }
    template<typename T,typename...args> void read(T &x,args&... a) {
        read(x);
        read(a...);
    } 
    template<typename T>void write(T x) {
        if(x==0){*p2++='0',*p2++='\n';return;}
        static char stk[20];
        int tp=0;
        while(x>0) {stk[tp++]=x%10+'0';x/=10;}
        for(int i=tp-1;i>=0;i--) *p2++=stk[i];
        *p2++='\n';
        return;
    }
    template<typename T,typename...args>void write(T &x,args&... a) {
        write(x);
        write(a...);
    }
}
using namespace IO;

int n,m,c;
int a[N],b[N],pp[N],qq[N];

int T;
LL ans[N];
bool bk[mx+5][mx+5],vis[mx+5];
LL pk[mx+5][mx+5];

signed main(){
//  freopen("t1_4.in","r",stdin);
//  freopen("qwq1.out","w",stdout);

    read(n,m,c);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=m;i++) read(b[i]);

    read(T);

    for(int t=1;t<=T;t++){
        int p,q;
        read(pp[t],qq[t]);
        p=pp[t]; q=qq[t];
        if(p>mx){
            LL zans=0;
            for(int i=1;i*p<c && i<=n;i++){
                int res=c-i*p;
                if(res%q==0){
                    int j=res/q;
                    if(j>m) continue;
                    (zans+=(1ll*a[i]*b[j]%MOD));
                    if(zans>=MOD) zans-=MOD;
                }
            }
            ans[t]=zans;
        }
        else if(q>mx){
            LL zans=0;
            for(int j=1;j*q<c && j<=m;j++){
                int res=c-j*q;
                if(res%p==0){
                    int i=res/p;
                    if(i>n) continue;
                    (zans+=1ll*a[i]*b[j]%MOD);
                    if(zans>=MOD) zans-=MOD;
                }
            }   
            ans[t]=zans;        
        }
        else{
            bk[p][q]=1;
            vis[p]=1;
        }
    }

    for(int p=1;p<=mx && p<=n;p++){
        if(!vis[p]) continue;
        for(int i=1;i*p<c;i++){
            int res=c-i*p;
            for(int q=max(res/m,1);q<=mx && q<=m;q++){
                if(res%q!=0) continue;
                if(!bk[p][q]) continue;
                int j=res/q;
                pk[p][q]=(pk[p][q]+1ll*a[i]*b[j]%MOD);
                if(pk[p][q]>=MOD) pk[p][q]-=MOD;
            }
        }       
    }   

    p1=p2=buff;
    for(int i=1;i<=T;i++){
        if(pp[i]<=mx && qq[i]<=mx) ans[i]=pk[pp[i]][qq[i]];
        write(ans[i]);
    }
    fwrite(buff, 1, p2 - p1, stdout);
    return 0;
}

2024/11/19 洛谷模拟赛

T1

T2