1 solutions

  • 0
    @ 2024-10-18 15:11:24

    模拟,前缀和,排序,二分(或者尺取)

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<string>
    #include<cstring>
    #include<cmath>
    using namespace std;
    typedef long long ll;
    const ll mod=998244353;
    const ll size=2e3+10;
    ll n,m,ans,num,tb,ta,a[size],b[size],sa[size*size/2],sb[size*size/2];
    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<<1)+(x<<3)+ch-'0';ch=getchar();}
        return x*f;
    }
    ll gcd(ll a,ll b)
    {
    	if(b)while((a%=b)&&(b%=a));
    
    	return a+b;
    }
    int main(){
        n=read();m=read();
       // num=n*(n+1)/2%mod;num=num*m%mod*(m+1)%mod;num=num*power(2,mod-2)%mod;
        for(ll i=1;i<=n;i++) a[i]=read(),a[i]+=a[i-1];
        for(ll i=1;i<=m;i++) b[i]=read(),b[i]+=b[i-1];
        for(ll l=1;l<=m;l++){
            for(ll r=l;r<=m;r++){
                sb[++tb]=b[r]-b[l-1];
            }
        }
        for(ll l=1;l<=n;l++){
            for(ll r=l;r<=n;r++){
                sa[++ta]=a[r]-a[l-1];
            }
        }
        sort(sa+1,sa+1+ta);
        sort(sb+1,sb+1+tb);
        ll l=0;
        for(ll i=1;i<=ta;i++){
            while(sb[l+1]<sa[i]&&l+1<=tb) l++;
            ans=ans+l;
        }
        int kk=gcd(ans,ta*tb);
    	cout << ans/kk << "/" << ta*tb/kk;
        return 0;
    }
    
    

    Information

    ID
    6991
    Time
    1500ms
    Memory
    256MiB
    Difficulty
    9
    Tags
    (None)
    # Submissions
    65
    Accepted
    3
    Uploaded By