题解：P17239 『STA - R10』雨落玫瑰

lailai0916 · 2026-08-31 06:46:10 · 题解

题意简述

对每个 x\in[1,n]，记：

求所有满足 P_x\le Q_x 的 P_x 之和，答案对 10^9+3579 取模。

解题思路

先忽略下取整，记：

当 A_x\le D_x 时，一定有 P_x\le Q_x。当 A_x\ge D_x+1 时，一定有 P_x>Q_x。

剩余部分满足 D_x<A_x<D_x+1，此时 P_x-Q_x\in\{0,1\}。

令：

前两类位置分别满足：

以及：

两个条件都对应一个整数区间。若 u>0，区间为：

以及：

若 u<0，不等号方向反转，区间为：

以及：

所有端点都与 [1,n] 取交。u=0 时直接判断常量不等式。实现中使用有符号向下取整和向上取整，避免负数除法的舍入问题。

第一个区间的贡献就是 \sum P_x。第二个区间内，P_x-Q_x 只能为 0 或 1，并且有：

因此第二个区间的合法贡献为：

问题转化为同时计算一次与二次下取整和。

定义 G(n,a,b,m) 处理 0\le x<n，并返回：

其中：

设 a=q_am+a'，b=q_bm+b'，则 y_x=q_ax+q_b+y'_x。记：

去掉整除部分后，三个量满足：

二次和满足：

带权和满足：

下面只需处理 0\le a,b<m。令：

对 1\le h\le Y，令 t_h 为最小的满足 y_x\ge h 的 x，则：

把 h=k+1 代入，可以改写为：

所以所有 t_h 的一次和、二次和与带权和，正好由 G(Y,m,m-b+a-1,a) 递归得到。

设递归结果为 T=\sum t_h、U=\sum t_h^2、V=\sum(h-1)t_h，则按格点交换求和可得：

二次和为：

带权和为：

每次递归都会交换除数与余数，层数为对数级。区间 [l,r] 只需平移成 x=l+k，调用 G(r-l+1,a,al+b,m)。

每组数据的时间复杂度为 O(\log V)，递归栈空间复杂度为 O(\log V)。这里 V 表示输入参数的最大值。

正确性证明

三个实数区间完整覆盖所有位置，且边界分别采用 \le、严格不等号和 \ge。因此，没有位置被遗漏或重复计算。

在中间区间内，P_x-Q_x 只能为 0 或 1。对应恒等式在两种取值下都成立，所以减去的部分恰好是 P_x>Q_x 时的贡献。

类欧递归先精确拆出 q_ax+q_b。剩余部分通过阈值 t_h 统计格点。

每个满足 y_x\ge h 的格点被计算一次。因此，三个递推式分别准确给出一次和、二次和与带权和。

两个区间的下取整和均被准确计算。第一个区间全部合法，第二个区间再删除所有不合法贡献。因此，算法得到的答案正确。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
__extension__ using i128=__int128;
const ll mod=1000003579;
const ll inv2=500001790;
struct Data
{
    ll s,s2,sx;
};
struct Range
{
    ll l,r;
};
ll norm(ll x)
{
    x%=mod;
    if(x<0)x+=mod;
    return x;
}
ll value(i128 x)
{
    x%=mod;
    if(x<0)x+=mod;
    return (ll)x;
}
ll mul(ll x,ll y)
{
    return value((i128)x*y);
}
ll sum1(ll n)
{
    return value((i128)n*(n-1)/2);
}
ll sum2(ll n)
{
    return value((i128)n*(n-1)*(2*n-1)/6);
}
Data calc(ll n,ll a,ll b,ll m)
{
    if(!n)return {0,0,0};
    ll qa=a/m,qb=b/m;
    a%=m;
    b%=m;
    Data g={0,0,0};
    if(a)
    {
        ll y=(ll)(((i128)a*(n-1)+b)/m);
        if(y)
        {
            Data t=calc(y,m,m-b+a-1,a);
            ll ny=y%mod,nn=n%mod;
            g.s=norm(mul(nn,ny)-t.s);
            g.s2=norm(mul(nn,mul(ny,ny))-mul(2,t.sx)-t.s);
            g.sx=norm(mul(ny,sum1(n))-mul(norm(t.s2-t.s),inv2));
        }
    }
    ll x1=sum1(n),x2=sum2(n),pa=qa%mod,pb=qb%mod;
    Data res;
    res.s=norm(g.s+mul(pa,x1)+mul(pb,n%mod));
    res.s2=norm(g.s2+mul(mul(pa,pa),x2)+mul(mul(pb,pb),n%mod)+mul(mul(mul(2,pa),pb),x1)+mul(mul(2,pa),g.sx)+mul(mul(2,pb),g.s));
    res.sx=norm(g.sx+mul(pa,x2)+mul(pb,x1));
    return res;
}
i128 floor_div(i128 x,i128 y)
{
    i128 q=x/y,r=x%y;
    if(r&&((r<0)!=(y<0)))q--;
    return q;
}
i128 ceil_div(i128 x,i128 y)
{
    return -floor_div(-x,y);
}
Range cut(i128 l,i128 r,ll n)
{
    l=max(l,(i128)1);
    r=min(r,(i128)n);
    if(l>r)return {1,0};
    return {(ll)l,(ll)r};
}
Range le(i128 a,i128 b,ll n)
{
    if(a>0)return cut(1,floor_div(b,a),n);
    if(a<0)return cut(ceil_div(b,a),n,n);
    if(b>=0)return {1,n};
    return {1,0};
}
Range mid(i128 a,i128 b,i128 w,ll n)
{
    if(a>0)return cut(floor_div(b,a)+1,ceil_div(b+w,a)-1,n);
    if(a<0)return cut(floor_div(b+w,a)+1,ceil_div(b,a)-1,n);
    if(b<0&&0<b+w)return {1,n};
    return {1,0};
}
Data query(ll a,ll b,ll m,Range q)
{
    if(q.l>q.r)return {0,0,0};
    ll c=(ll)((i128)a*q.l+b);
    return calc(q.r-q.l+1,a,c,m);
}
void solve()
{
    ll a,b,c,d,e,f,n;
    cin>>a>>b>>c>>d>>e>>f>>n;
    i128 k=(i128)a*f-(i128)d*c;
    i128 v=(i128)e*c-(i128)b*f;
    i128 w=(i128)c*f;
    Range q1=le(k,v,n);
    Range q2=mid(k,v,w,n);
    ll ans=query(a,b,c,q1).s;
    if(q2.l<=q2.r)
    {
        Data x=query(a,b,c,q2);
        Data y=query(d,e,f,q2);
        ll bad=mul(norm(x.s2+x.s-y.s2-y.s),inv2);
        ans=norm(ans+x.s-bad);
    }
    cout<<ans<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}