杭电多校第六场1006 1007 1008题解，std

题是我出的，std是我写的。1006是原创套路。1008是原创贪心。1007是从CF上的题加强了一下子出的。

1006

此题算法复杂度为 $O(n \log n),n = \max_{(x,y) \in E} \max(x,y)$​​。考虑使用集合对称差卷积的方法进行计算。我们考虑集合对称差卷积，每次只能处理一个$[x\times2^n,x\times2^n+2^n-1] \times [y\times2^n,y\times2^n+2^n-1]$​​​​​ 的块。我们就先把所有最大的全在椭圆内的块处理了，再把次大的块处理了，依次类推……

但是这个算法是两个log的，还不够快。考虑优化这个算法，方法就是从底向上进行FWT的同时，进行到哪一层就把哪一层需要计算的块处理了。在算出乘积之后不需要急于进行反向的FWT，而是累加在结果数组上。

此题复杂度分析中有一点是要证明所有块的边长之和是 $O(n \log n)$ 的，这一事实可以以限制函数为单调函数为条件证明，而椭圆的边界可以拆分成四个单调函数。证明的思路是证明每个x坐标的横坐标块对应的y坐标块一定是常数个加上一些个块，而对于同一大小的块，“加上的块”的总长不能超过 $n$。由于长度为 $\log n$种，因此结论成立。

1007

首先，我们发现操作是可逆的，这就意味着我们从始至终只需要操作第一个图即可。而后我们发现题目中的图必须每个联通块都满足可以两个图可以相等，整个图才可以相等。

考虑一个联通块，首先这个联通块在两个图中的数字的multiset必须是一样的。而后我们可以发现，题目中的交换方式可以换个方式理解：将两个节点的数字和颜色都交换，再都翻转。这样的操作和原先的操作结果会是一样的。

这样的情况下，一个数字如果被交换了奇数次，他的颜色就会翻转，如果被交换了偶数次，则不会翻转。而后我们分情况讨论：

1. 图是一个二分图。那么我们把这个图黑白染色，我们发现对于一个数字，如果我们知道这个数字初始的黑白染色的颜色和节点的颜色，我们把这个数字交换到任何一个位置后，对应的节点的颜色就是已知的了。而且，由于图是联通的，数字是可以任意排列到所有节点上的。那么这时条件就是将数字按照(节点颜色^数字颜色)分成两个可重集合，题目中两个图的这两个可重集合必须是一样的。
2. 图不是一个二分图。这时候联通块里会有一个奇环。此时的条件是输入两个图里所有数字的可重集合必须相同，且颜色个数的奇偶性不能改变。这是由于我们可以把图看成一个二分图加上一些多余的边，我们可以对于任何一个奇环构造一个方案使得所有的数字不动，且只有两个位置的颜色翻转，不论那两个位置开始颜色如何。方案就是：对于奇环上的点顺序编号为1到n，先进行n-1次操作将1上的数字交换到n号节点，再进行一次操作交换1号和n号节点上的数字，再用n-2次操作将n号节点上的数字交换到二号节点。

1008

考虑范围为k的狙击手，可以攻击的范围是一个正方体。那我们不妨重新陈述一下题面，称狙击手从 $(x,y,z)$​ 可以攻击的范围是所有满足 $x \le x' \le x+2k, y \le y' \le y+2k,z \le z' \le z+2k$​ 的 $(x',y',z')$​。那么我们就会发现：如果我们的狙击手的某一维度的坐标小于剩余点的那一维度的最小坐标，我们就应该把狙击手移动的那一维度的最小坐标，因为这样只会让我们能狙击的目标增多。在我们三个维度都是那一维度的最小坐标时，狙击手就必须将三个维度中某一维度最小坐标的所有敌军都消灭，才能继续移动。这时我们可以贪心的选取所需 $k$ 最小的敌军消灭。复杂度 $O(n \log n)$。

1006 STD

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
#define tcT template<class T
#define tcTU tcT, class U
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define each(a,x) for (auto& a: x)
const int mod = 1000000007;
constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
tcTU> T lstTrue(T lo, T hi, U f) { lo --; assert(lo <= hi); while (lo < hi) { T mid = lo+(hi-lo+1)/2; f(mid) ? lo = mid : hi = mid-1; } return lo; }

const int MX = (2<<22)+10;
ll a,b,c,d,e,f;
int N,miv[MX],xv2[MX],yv2[MX],resv[MX],li[MX*2],ri[MX*2];

inline int mul(int x,int y){return 1ll*x*y%mod;}
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int sub(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int sq(int x){return 1ll*x*x%mod;}
int mpow(int a,int b){return b == 0 ? 1 : ( b&1 ? mul(a,sq(mpow(a,b/2))) : sq(mpow(a,b/2)));}

void solve(){
    cin>>a>>b>>c>>d>>e>>f;
    ll xbnd = lstTrue(0,4000000,[&](ll x){return (4*c*a-e*e)*x*x<=4*c*f;});
    ll ybnd = lstTrue(0,4000000,[&](ll x){return (4*c*a-e*e)*x*x<=4*a*f;});
    int cn = max(b+xbnd,d+ybnd)+10;
    N = 1;while(N<cn)N*=2;
    F0R(i,N){
        yv2[i] = miv[i];
        xv2[i] = 1ll*yv2[i]*yv2[i]%mod;
        resv[i] = 0;
    }
    F0R(ii,N){
        if(ii<b-xbnd || ii>b+xbnd){
            li[ii+N] = 1;ri[ii+N] = 0;
            continue;
        }
        ll i = ii-b,cv = e*e*i*i-4*c*(a*i*i-f),ce = sqrt(cv);
        while(ce*ce>cv)ce-=1; while((ce+1)*(ce+1)<=cv)ce+=1;
        ri[ii+N] = fdiv(-e*i+ce,c*2)+d;
        li[ii+N] = fdiv(-e*i-ce+c*2-1,c*2)+d;
    }
    int msk = N-2;
    R0F(i,N){
        li[i] = N-((N-max(li[i*2],li[i*2+1]))&msk);
        ri[i] = ((min(ri[i*2],ri[i*2+1])+1)&msk)-1;
        if(pct(i) == 1)msk-=msk&-msk;
    }
    auto conv = [&](int* xxa,int i){
        for(int s =0;s<N;s+=i*2){
            int* f1 = xxa+s,*f2 =xxa+s+i;
            for(int j=0;j<i;j++){ int c1 = f1[j],c2 = f2[j]; f1[j]=add(c1,c2); f2[j]=sub(c1,c2); }
        }
    };
    for(int i = 1;i<N;i*=2){
        int s;
        function<void(int,int)> calc= [&](int l,int r){
            for(int j=l;j<r;j+=i){
                int *a = xv2+s,*b = yv2+j,*res = resv+(s^j);
                for(int k=0;k<i;k++) res[k]=(1ll*a[k]*b[k]+res[k])%mod;
            }
        };
        for(s =0;s<N;s+=i){
            int id = (N+s)/i;
            if(li[id]>ri[id])continue;
            if(li[id/2]>ri[id/2]){
                calc(li[id],ri[id]+1);
            }else{
                calc(li[id],li[id/2]);
                calc(ri[id/2]+1,ri[id]+1);
            }
        }
        conv(xv2,i);conv(yv2,i);conv(resv,i);
    }
    for(int i = 1;i<N;i*=2) conv(resv,i);
    int ans = 0;
    F0R(i,N) ans=add(ans,(1ll*((1ll*resv[i]*i)%mod)*((1ll*i*i)%mod))%mod);
    ans=mul(ans,mpow(N,mod-2));
    cout<<ans<<"\n";
}

int main() {
    int T;cin>>T;
    miv[0] = miv[1]= 1;
    FOR(i,2,MX) miv[i] = mod-(long long)mod/i*miv[mod%i]%mod;
    while(T--){
        solve();
    }
    return 0;
}