Znzryb's Blog

2025钉耙编程-中国大学生算法设计暑期联赛（8）——最努力的活着

Posted on 2025-08-11 Edited on 2026-04-06

思路讲解

暴力程序是这样的。

i128 ans=0;
while(true){
    if(n<W) break;
    ans+=(1+N)*N/2-(sum+1)*sum/2;
    sum+=n/W;
    n-=n/W;
}
ans+=(1+N)*N/2-(sum+1)*sum/2;

不难发现，我们可以分块处理相同n/W的部分，以获得logn的时间复杂度。

AC代码

https://acm.hdu.edu.cn/contest/view-code?cid=1179&rid=14726

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#include <cstdio>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define lson(var) (var<<1)
#define rson(var) (var<<1|1)
#define fsp(x) fixed<<setprecision(x)
using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
#endif

using  ll = __int128;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
i128 N,M,Q,X,K,T,lT,W;

inline void __();
namespace QuickRead { // 快读
    char buf[1 << 21], *p1 = buf, *p2 = buf;
    inline int getc() {
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
    }
    template <typename T> void Cin(T &a) {
        T ans = 0;
        bool f = 0;
        char c = getc();
        for (; c < '0' || c > '9'; c = getc()) {
            if (c == '-') f = 1;
        }
        for (; c >= '0' && c <= '9'; c = getc()) {
            ans = ans * 10 + c - '0';
        }
        a = f ? -ans : ans;
    }
    template <typename T, typename... Args> void Cin(T &a, Args &...args) {
        Cin(a), Cin(args...);
    }
    template <typename T> void write(T x) { // 注意，这里输出不带换行
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
} // namespace QuickRead

using namespace QuickRead;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    Cin(lT);
    while(lT--)
        __();
    return 0;
}
/*

*/
i128 ans=0;
// void calres(ll n,ll obj,ll step){
//     // i128 l=(i128)N*(N-1)/2-(i128)(N-obj+1)*(N-obj)/2;
//     // i128 r=(i128)N*(N-1)/2-(i128)(N-n+1)*(N-n)/2;
//     i128 num=n-obj;
//     i128 l=(i128)(N-n+1)*(N-n)/2;
//     i128 r=(i128)(N-obj+1)*(N-obj)/2;
//     i128 res=(i128)(N+1)*N/2*((n-obj+1)/step)-(l+r)*((n-obj+1)/step)/2;
// #ifdef LOCAL
//     debug(n);debug(obj);
//     debug((ll)l);debug((ll)r);debug((ll)res);
//     cend;
// #endif
//     ans+=res;
// }
void calres(i128 n,i128 obj,i128 step,i128 num){
    i128 sum=(N+1)*N/2*num;
    i128 fn=N-n,fob=N-(obj+step);
    // =(fn+jd)^2
    i128 sumsq=num*(num-1)*(2*num-1)/6;
    i128 minus=fn*fn*num+sumsq*step*step+2*fn*(num-1+0)*num/2*step;
    minus+=(fn+fob)*num/2;
    minus/=2;
    ans+=sum-minus;
}
// ceil_div
template<typename T> T chu(T x,T y) {
    if ((x ^ y) < 0) return x / y;
    if (x % y == 0) return x / y;
    return x / y + 1;
}

inline void __(){
    Cin(N,W);
    i128 n=N;
    ans=0;
    while(true){
        if(n<W) break;
        i128 step=n/W;
        i128 obj=W*(n/W)-1;
        ll num=chu((n-obj),step);
        obj=n-step*num;
        calres(n, obj,n/W,num);
        n=obj;
    }
    ans+=(1+N)*N/2-(i128)(N-n+1)*(N-n)/2;
    write(ans);putchar('\n'); 
}
/*
前面因为long long溢出WA了一发
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1179&rid=14726
(1+N)*N/2-(sum+1)*sum/2:15
(1+N)*N/2-(sum+1)*sum/2:12
(1+N)*N/2-(sum+1)*sum/2:9
(1+N)*N/2-(sum+1)*sum/2:5

1
7 4

n:7
(1+N)*N/2-(sum+1)*sum/2:28
n:6
(1+N)*N/2-(sum+1)*sum/2:27
n:5
(1+N)*N/2-(sum+1)*sum/2:25
n:4
(1+N)*N/2-(sum+1)*sum/2:22
n:3
(1+N)*N/2-(sum+1)*sum/2:18
*/

心路历程（WA，TLE，MLE……）

容易发现，fob的计算一定是交给后面算的，就算是最后一个也是。

2025“钉耙编程”中国大学生算法设计暑期联赛（7）——龙族栖息地

Posted on 2025-08-09 Edited on 2026-04-06

思路讲解

AC代码

源代码

心路历程（WA，TLE，MLE……）

2025“钉耙编程”中国大学生算法设计暑期联赛（7）——矩形框选

Posted on 2025-08-08 Edited on 2026-04-06

思路讲解

我的做法还是我的做法，就是需要用zkw线段树卡一下常

复杂度是 $O(\sqrt k \times N \times \log(n))$ 。

AC代码

https://acm.hdu.edu.cn/contest/status?cid=1178&rid=15857

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#include <cstdio>
#include <vector>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define lson(var) (var<<1)
#define rson(var) (var<<1|1)
#define fsp(x) fixed<<setprecision(x)
using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
#endif

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;
namespace QuickRead { // 快读
    char buf[1 << 21], *p1 = buf, *p2 = buf;
    inline int getc() {
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
    }
    template <typename T> void Cin(T &a) {
        T ans = 0;
        bool f = 0;
        char c = getc();
        for (; c < '0' || c > '9'; c = getc()) {
            if (c == '-') f = 1;
        }
        for (; c >= '0' && c <= '9'; c = getc()) {
            ans = ans * 10 + c - '0';
        }
        a = f ? -ans : ans;
    }
    template <typename T, typename... Args> void Cin(T &a, Args &...args) {
        Cin(a), Cin(args...);
    }
    template <typename T> void write(T x) { // 注意，这里输出不带换行
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
} // namespace QuickRead

using namespace QuickRead;
inline void __();
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    Cin(lT);
    while(lT--)
        __();
    return 0;
}
/*

*/
// AC https://www.luogu.com.cn/record/229740484 P1253 扶苏的问题
// https://acm.hdu.edu.cn/contest/view-code?cid=1178&rid=15813 卡常卡过去了
template <typename T, typename value_type> struct base_segtree {
    static constexpr bool zkw = 0;
    static constexpr bool custom_leaf = 0;
    static constexpr bool pushdown_when_update = 1;

    int n, sz;
    vector<value_type> data;

    base_segtree(int n): n(n), sz(T::zkw ? bit_ceil(n) : n), data(sz << !T::custom_leaf, T::identity) {}
    static int bit_ceil(int n) { int k = 1; while (k < n) k <<= 1; return k; }

    T *derived() { return static_cast<T*>(this); }
    value_type val(int o) { 
        return val_impl(o, typename std::integral_constant<bool, T::custom_leaf>::type{});
    }
private:
    value_type val_impl(int o, std::true_type) {
        if (o < sz) return data[o];
        int i = o - sz;
        if (i >= n) return T::identity;
        return derived()->get_leaf(i);
    }
    value_type val_impl(int o, std::false_type) {
        return data[o];
    }
public:
    value_type get_leaf(int i) { return T::identity; }
    void pushup(int o) {
        data[o] = T::op(val(o << 1), val(o << 1 | 1));
    }
    void pushdown(int o) {}
    void call_pushdown(int i) { 
        int o = i + sz;
        for (int k = lg(o); k >= __builtin_ctz(o) + 1; k--) derived()->pushdown(o >> k); 
    }   
    void call_pushup(int i) { 
        int o = i + sz;
        for (int k = __builtin_ctz(o) + 1; k <= lg(o); k++) derived()->pushup(o >> k); 
    }
    value_type& operator[](int i) {
        static_assert(!T::custom_leaf, "custom leaf do not support operator[]");
        return data[i + sz];
    }
    void build() { 
        for(int o = sz - 1; o >= 1; o--) derived()->pushup(o); 
    }
    template <typename D> void update(int l, int r, D x) {
        if (T::pushdown_when_update) call_pushdown(l), call_pushdown(r);
        int l0 = l, r0 = r; l += sz, r += sz;
        for (; l < r; l >>= 1, r >>= 1) {
            if (l & 1) derived()->settag(l++, x);
            if (r & 1) derived()->settag(--r, x);
        }
        call_pushup(l0), call_pushup(r0);
    }
    value_type ask(int l, int r) {
        call_pushdown(l), call_pushdown(r);
        l += sz, r += sz;
        value_type resl = T::identity, resr = T::identity;
        for (; l < r; l >>= 1, r >>= 1) {
            if (l & 1) resl = T::op(resl, val(l++));
            if (r & 1) resr = T::op(val(--r), resr);
        }
        return T::op(resl, resr);
    }
    static int lg(int x) {
        return x == 0 ? -1 : 31 - __builtin_clz(x);
    }
};

struct segtree: base_segtree<segtree, ll> {
    static constexpr bool zkw = 1;
    static constexpr ll identity = -INF;
   
    static ll op(ll a, ll b) { return max(a, b); }
    vector<ll> tag;
    vector<bool> fixed;
    segtree(int n): base_segtree(n), tag(sz), fixed(sz) {}
    segtree(const vector<ll>& a): base_segtree(a.size()), tag(sz), fixed(sz) {
        for(int i = 0; i < (int)a.size(); i++) (*this)[i] = a[i];
        build();
    }
    void settag(int o, pair<int, ll> t) {
        int op = t.first;
        ll x = t.second;
        if (op == 1) {
            data[o] = x;
            if (o < sz) tag[o] = 0, fixed[o] = 1;
        } else {
            data[o] += x;
            if (o < sz && !fixed[o]) tag[o] += x;
        }
    }
    void pushdown(int o) {
        if (fixed[o]) {
            settag(o << 1, make_pair(1, data[o]));
            settag(o << 1 | 1, make_pair(1, data[o]));
            fixed[o] = 0;
        }
        if (tag[o]) {
            settag(o << 1, make_pair(2, tag[o]));
            settag(o << 1 | 1, make_pair(2, tag[o]));
            tag[o] = 0;
        }
    }
};
// 注意调用的时候是左开右闭区间，0-based，具体来讲[l,r]->[l-1,r)
// tr.update(0,N,(pll){1,0})    是清空操作
// C++14需要为static constexpr成员提供定义
constexpr bool segtree::zkw;
constexpr ll segtree::identity;

inline void __(){
    Cin(N,K);
    vector<vpll> xyv(N+5);
    FOR(i,0,N-1){
        ll x,y,v;
        Cin(x,y,v);
        xyv[x].EB(y,v);
    }
    ll ans=0;
    segtree tr(N);
    FOR(i,1,sqrtl(K)){
        ll xlen=i,ylen=K/i;
        // if (xlen < 1 || ylen < 1) continue;
        tr.update(0,N,(pll){1,0});
        FOR(x,1,min(xlen,N)){
            for(auto&[y,v]:xyv[x]){
                tr.update(max(0ll,y-ylen),y,(pll){2,v});
            }
        }
        ans=max(ans,tr.ask(0, N));
        FOR(x,xlen+1,N){
            ll qv=x-xlen;
            for(auto&[y,v]:xyv[qv]){
                tr.update(max(0ll,y-ylen),y,(pll){2,-v});
            }
            for(auto&[y,v]:xyv[x]){
                tr.update(max(0ll,y-ylen),y,(pll){2,v});
            }
            ans=max(ans,tr.ask(0, N));
        }
    }
    FOR(i,1,sqrtl(K)){
        ll ylen=i,xlen=K/i;
        // if (xlen < 1 || ylen < 1) continue;
        tr.update(0,N,(pll){1,0});
        FOR(x,1,min(xlen,N)){
            for(auto&[y,v]:xyv[x]){
                tr.update(max(0ll,y-ylen),y,(pll){2,v});
            }
        }
        ans=max(ans,tr.ask(0, N));
        FOR(x,xlen+1,N){
            ll qv=x-xlen;
            for(auto&[y,v]:xyv[qv]){
                tr.update(max(0ll,y-ylen),y,(pll){2,-v});
            }
            for(auto&[y,v]:xyv[x]){
                tr.update(max(0ll,y-ylen),y,(pll){2,v});
            }
            ans=max(ans,tr.ask(0, N));
        }
    }
    write(ans);
    putchar('\n');
}
/*
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1178&rid=15857
*/

稍微优化过的版本，不过这两个都比较卡着这个时限。

https://acm.hdu.edu.cn/contest/view-code?cid=1178&rid=15813

源代码

// by Gospel_rock
#include <algorithm>
#include <bits/stdc++.h>
#include <cmath>
#include <cstdio>
#include <numeric>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define lson(var) (var<<1)
#define rson(var) (var<<1|1)
#define fsp(x) fixed<<setprecision(x)
using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
#endif

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

inline void __();
namespace QuickRead { // 快读
    char buf[1 << 21], *p1 = buf, *p2 = buf;
    inline int getc() {
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
    }
    template <typename T> void Cin(T &a) {
        T ans = 0;
        bool f = 0;
        char c = getc();
        for (; c < '0' || c > '9'; c = getc()) {
            if (c == '-') f = 1;
        }
        for (; c >= '0' && c <= '9'; c = getc()) {
            ans = ans * 10 + c - '0';
        }
        a = f ? -ans : ans;
    }
    template <typename T, typename... Args> void Cin(T &a, Args &...args) {
        Cin(a), Cin(args...);
    }
    template <typename T> void write(T x) { // 注意，这里输出不带换行
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
} // namespace QuickRead

using namespace QuickRead;

// AC https://www.luogu.com.cn/record/229740484 P1253 扶苏的问题
template <typename T, typename value_type> struct base_segtree {
    static constexpr bool zkw = 0;
    static constexpr bool custom_leaf = 0;
    static constexpr bool pushdown_when_update = 1;

    int n, sz;
    vector<value_type> data;

    base_segtree(int n): n(n), sz(T::zkw ? bit_ceil(n) : n), data(sz << !T::custom_leaf, T::identity) {}
    static int bit_ceil(int n) { int k = 1; while (k < n) k <<= 1; return k; }

    T *derived() { return static_cast<T*>(this); }
    value_type val(int o) { 
        return val_impl(o, typename std::integral_constant<bool, T::custom_leaf>::type{});
    }
private:
    value_type val_impl(int o, std::true_type) {
        if (o < sz) return data[o];
        int i = o - sz;
        if (i >= n) return T::identity;
        return derived()->get_leaf(i);
    }
    value_type val_impl(int o, std::false_type) {
        return data[o];
    }
public:
    value_type get_leaf(int i) { return T::identity; }
    void pushup(int o) {
        data[o] = T::op(val(o << 1), val(o << 1 | 1));
    }
    void pushdown(int o) {}
    void call_pushdown(int i) { 
        int o = i + sz;
        for (int k = lg(o); k >= __builtin_ctz(o) + 1; k--) derived()->pushdown(o >> k); 
    }   
    void call_pushup(int i) { 
        int o = i + sz;
        for (int k = __builtin_ctz(o) + 1; k <= lg(o); k++) derived()->pushup(o >> k); 
    }
    value_type& operator[](int i) {
        static_assert(!T::custom_leaf, "custom leaf do not support operator[]");
        return data[i + sz];
    }
    void build() { 
        for(int o = sz - 1; o >= 1; o--) derived()->pushup(o); 
    }
    template <typename D> void update(int l, int r, D x) {
        if (T::pushdown_when_update) call_pushdown(l), call_pushdown(r);
        int l0 = l, r0 = r; l += sz, r += sz;
        for (; l < r; l >>= 1, r >>= 1) {
            if (l & 1) derived()->settag(l++, x);
            if (r & 1) derived()->settag(--r, x);
        }
        call_pushup(l0), call_pushup(r0);
    }
    value_type ask(int l, int r) {
        call_pushdown(l), call_pushdown(r);
        l += sz, r += sz;
        value_type resl = T::identity, resr = T::identity;
        for (; l < r; l >>= 1, r >>= 1) {
            if (l & 1) resl = T::op(resl, val(l++));
            if (r & 1) resr = T::op(val(--r), resr);
        }
        return T::op(resl, resr);
    }
    static int lg(int x) {
        return x == 0 ? -1 : 31 - __builtin_clz(x);
    }
};

struct segtree: base_segtree<segtree, ll> {
    static constexpr bool zkw = 1;
    static constexpr ll identity = -INF;
   
    static ll op(ll a, ll b) { return max(a, b); }
    vector<ll> tag;
    vector<bool> fixed;
    segtree(int n): base_segtree(n), tag(sz), fixed(sz) {}
    segtree(const vector<ll>& a): base_segtree(a.size()), tag(sz), fixed(sz) {
        for(int i = 0; i < (int)a.size(); i++) (*this)[i] = a[i];
        build();
    }
    void settag(int o, pair<int, ll> t) {
        int op = t.first;
        ll x = t.second;
        if (op == 1) {
            data[o] = x;
            if (o < sz) tag[o] = 0, fixed[o] = 1;
        } else {
            data[o] += x;
            if (o < sz && !fixed[o]) tag[o] += x;
        }
    }
    void pushdown(int o) {
        if (fixed[o]) {
            settag(o << 1, make_pair(1, data[o]));
            settag(o << 1 | 1, make_pair(1, data[o]));
            fixed[o] = 0;
        }
        if (tag[o]) {
            settag(o << 1, make_pair(2, tag[o]));
            settag(o << 1 | 1, make_pair(2, tag[o]));
            tag[o] = 0;
        }
    }
};

// C++14需要为static constexpr成员提供定义
constexpr bool segtree::zkw;
constexpr ll segtree::identity;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    Cin(lT);
    while(lT--)
        __();
    return 0;
}
/*

*/
struct XYV{
    ll x,y,v;
    XYV(ll x,ll y,ll v) {this->x=x,this->y=y,this->v=v;}
};
inline void __(){
    Cin(N,K);
    // FOR(i,0,N+5){
    //     FOR(j,0,N+5)
    //         D[i][j]=0;
    // }
    // vtll xyv;
    vector<vector<XYV>> xyv(N+5);
    vtll xxx;
    ll tot=1,xtot=0;
    FOR(i,0,N-1){
        ll x,y,v;
        Cin(x,y,v);
        xxx.EB(x,y,v);
    }
    sort(all(xxx));
    for(auto&[x,y,v]:xxx){
        if(xyv[tot].empty() || xtot==x){
            xyv[tot].EB(x,y,v);
        }else{
            xyv[++tot].EB(x,y,v);
            xtot=x;
        }
    }
    ll ans=0;
    segtree tr(N);

    map<ll,ll> mp;
    FOR(i,1,sqrtl(K)){
        ll xlen=i,ylen=K/i;
        mp[xlen]=max(mp[xlen],ylen);
    }
    for(auto&[xlen,ylen]:mp){
        // if (xlen < 1 || ylen < 1) continue;
        tr.update(0,N,(pll){1,0});
        ll st=1;
        FOR(i,1,tot){
            ll ix=xyv[i][0].x;
            ll stx=xyv[st][0].x;
            while(ix-stx+1>xlen){
                for(auto&[x,y,v]:xyv[st]){
                    // tr.add(y-ylen+1, y, -v);
                    tr.update(max(0ll,y-ylen),y,(pll){2,-v});
                }
                ++st;
                stx=xyv[st][0].x;
            }
            for(auto&[x,y,v]:xyv[i]){
                tr.update(max(0ll,y-ylen),y,(pll){2,v});
            }
            ans=max(ans,tr.ask(0, N));
        }
    }

    for(auto&[ylen,xlen]:mp){
        // if (xlen < 1 || ylen < 1) continue;
        tr.update(0,N,(pll){1,0});
        ll st=1;
        FOR(i,1,tot){
            ll ix=xyv[i][0].x;
            ll stx=xyv[st][0].x;
            while(ix-stx+1>xlen){
                for(auto&[x,y,v]:xyv[st]){
                    // tr.add(y-ylen+1, y, -v);
                    tr.update(max(0ll,y-ylen),y,(pll){2,-v});
                }
                ++st;
                stx=xyv[st][0].x;
            }
            for(auto&[x,y,v]:xyv[i]){
                tr.update(max(0ll,y-ylen),y,(pll){2,v});
            }
            ans=max(ans,tr.ask(0, N));
        }
    }
    write(ans);
    putchar('\n');
}
/*
WA
https://acm.hdu.edu.cn/contest/view-code?cid=1178&rid=5684
TLE
https://acm.hdu.edu.cn/contest/view-code?cid=1178&rid=8240
WA 
https://acm.hdu.edu.cn/contest/view-code?cid=1178&rid=10273
可能是需要去变换这个边长
TLE
https://acm.hdu.edu.cn/contest/view-code?cid=1178&rid=11241
TLE
https://acm.hdu.edu.cn/contest/view-code?cid=1178&rid=11820
1
4 9
1 2 10
2 1 10
2 3 10
3 2 10

1
3 6
1 1 5
2 1 5
3 1 5

ans:15
*/

自己写的线段树rmq，会比之前的快一点。

https://acm.hdu.edu.cn/contest/view-code?cid=1178&rid=19430

源代码

// by Gospel_rock
#include <algorithm>
#include <bits/stdc++.h>
#include <cmath>
#include <cstdio>
#include <numeric>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define lson(var) (var<<1)
#define rson(var) (var<<1|1)
#define fsp(x) fixed<<setprecision(x)
using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
#endif

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

inline void __();
namespace QuickRead { // 快读
    char buf[1 << 21], *p1 = buf, *p2 = buf;
    inline int getc() {
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
    }
    template <typename T> void Cin(T &a) {
        T ans = 0;
        bool f = 0;
        char c = getc();
        for (; c < '0' || c > '9'; c = getc()) {
            if (c == '-') f = 1;
        }
        for (; c >= '0' && c <= '9'; c = getc()) {
            ans = ans * 10 + c - '0';
        }
        a = f ? -ans : ans;
    }
    template <typename T, typename... Args> void Cin(T &a, Args &...args) {
        Cin(a), Cin(args...);
    }
    template <typename T> void write(T x) { // 注意，这里输出不带换行
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
} // namespace QuickRead

using namespace QuickRead;


// 参考zkw的PPT 以及 https://www.luogu.com.cn/record/207546670
// 参考题解 https://www.luogu.com.cn/article/w3gfeebh
// AC https://www.luogu.com.cn/record/232784803 RMQ 
// AC https://acm.hdu.edu.cn/contest/view-code?cid=1178&rid=19430 矩形框选卡常
constexpr ll preset=-INF;
struct SEG{
    static ll op(const ll &a,const ll &b){
        return max(a,b);
    }
    int n,sz=1,dep;
    vector<ll> tr;vector<ll> tag;vector<bool> fixed;
    SEG(int n){     // 传入的时候可以传大一点
        this->n=n+2;
        dep=__lg(this->n)+1;
        sz=1<<dep;
        tr.resize((sz<<1)+5,preset);
        tag.resize((sz<<1)+5,0);
        fixed.resize((sz<<1)+5,false);
    }
    void pushup(int o){tr[o]=op(tr[o<<1],tr[o<<1|1]);}
    void settag(int o,ll x){
        tr[o]+=x;
        if(!fixed[o]) tag[o]+=x;
    }
    void settag2(int o,ll x){   // 覆盖
        tr[o]=x;
        tag[o]=0;
        fixed[o]=true;
    }
    void pushdown(int o){ 
        int l=o<<1,r=l|1;   // 左儿子，右儿子
        if(fixed[o]){
            settag2(l, tr[o]);
            settag2(r, tr[o]);
            fixed[o]=false;
        }
        if(tag[o]){
            settag(l, tag[o]);
            settag(r, tag[o]);
            tag[o]=0;
        }
    }
    void push(int l,int r){
        //        在j层，l，r变为了同一点
        int i=dep,j=__lg(l^r);
        while (i<j) {   // 就是为了避免一下重复下推
            pushdown(l>>i--);
        }
        while(i){
            pushdown(l>>i),pushdown(r>>i--);
        }
    }
    void assign(int i,ll x){   
        tr[i+sz]=x;
    }
    void build(){
        for(int o=sz-1;o>=1;--o){
            pushup(o);
        }
    }
    ll query(int l,int r){
        ll res=preset;
        // 变为开区间，并加上sz
        l=l-1+sz,r=r+1+sz;
        push(l,r);
        for(;l^r^1;l>>=1,r>>=1){
            // l^r^1 表示 只要 l 与 r 还不是同一个父亲的两兄弟，就继续上跳。
            if(~l&1){   
                // l是偶数，说明l是父节点的左儿子，开区间，将其右儿子加入答案
                res=op(res,tr[l^1]);
            }
            if(r&1){
                res=op(tr[r^1],res);
            }
        }
        return res;
    }
    void add(int l,int r,ll x){
        int w=1;
        l=l-1+sz,r=r+1+sz;
        push(l, r);
        for(;l^r^1;pushup(l>>=1),pushup(r>>=1),w<<=1){
            if(~l&1){
                settag(l^1, x);
            }
            if(r&1){
                settag(r^1, x);
            }
        }
        for (l >>= 1; l; l >>= 1) pushup(l);
    }
    void modify(int l,int r,ll x){
        int w=1;
        l=l-1+sz,r=r+1+sz;
        push(l, r);
        for(;l^r^1;pushup(l>>=1),pushup(r>>=1),w<<=1){
            if(~l&1){
                settag2(l^1, x);
            }
            if(r&1){
                settag2(r^1, x);
            }
        }
        for (l >>= 1; l; l >>= 1) pushup(l);
    }
};

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    Cin(lT);
    while(lT--)
        __();
    return 0;
}
/*

*/
struct XYV{
    ll x,y,v;
    XYV(ll x,ll y,ll v) {this->x=x,this->y=y,this->v=v;}
};
inline void __(){
    Cin(N,K);
    // FOR(i,0,N+5){
    //     FOR(j,0,N+5)
    //         D[i][j]=0;
    // }
    // vtll xyv;
    vector<vector<XYV>> xyv(N+5);
    vtll xxx;
    ll tot=1,xtot=0;
    FOR(i,0,N-1){
        ll x,y,v;
        Cin(x,y,v);
        xxx.EB(x,y,v);
    }
    sort(all(xxx));
    for(auto&[x,y,v]:xxx){
        if(xyv[tot].empty() || xtot==x){
            xyv[tot].EB(x,y,v);
        }else{
            xyv[++tot].EB(x,y,v);
            xtot=x;
        }
    }
    ll ans=0;
    SEG tr(N);

    map<ll,ll> mp;
    FOR(i,1,sqrtl(K)){
        ll xlen=i,ylen=K/i;
        mp[xlen]=max(mp[xlen],ylen);
    }
    for(auto&[xlen,ylen]:mp){
        // if (xlen < 1 || ylen < 1) continue;
        tr.modify(1,N,0);
        ll st=1;
        FOR(i,1,tot){
            ll ix=xyv[i][0].x;
            ll stx=xyv[st][0].x;
            while(ix-stx+1>xlen){
                for(auto&[x,y,v]:xyv[st]){
                    // tr.add(y-ylen+1, y, -v);
                    tr.add(max(0ll,y-ylen)+1,y,-v);
                }
                ++st;
                stx=xyv[st][0].x;
            }
            for(auto&[x,y,v]:xyv[i]){
                tr.add(max(0ll,y-ylen)+1,y,v);
            }
            ans=max(ans,tr.tr[1]);
        }
    }

    for(auto&[ylen,xlen]:mp){
        // if (xlen < 1 || ylen < 1) continue;
        tr.modify(1,N,0);
        ll st=1;
        FOR(i,1,tot){
            ll ix=xyv[i][0].x;
            ll stx=xyv[st][0].x;
            while(ix-stx+1>xlen){
                for(auto&[x,y,v]:xyv[st]){
                    // tr.add(y-ylen+1, y, -v);
                    tr.add(max(0ll,y-ylen)+1,y,-v);
                }
                ++st;
                stx=xyv[st][0].x;
            }
            for(auto&[x,y,v]:xyv[i]){
                tr.add(max(0ll,y-ylen)+1,y,v);
            }
            ans=max(ans,tr.tr[1]);
        }
    }

    write(ans);
    putchar('\n');
}
/*
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1178&rid=19430
1
4 9
1 2 10
2 1 10
2 3 10
3 2 10

1
3 6
1 1 5
2 1 5
3 1 5

ans:15
*/

心路历程（WA，TLE，MLE……）

P1919 【模板】高精度乘法 | A*B Problem 升级版

Posted on 2025-08-07 Edited on 2026-04-06

思路讲解

使用FFT。

注意给FFT喂入的是从低到高的。

输出前注意去除前导0。

string A,B;
cin>>A>>B;
vll a,b;
ROF(i,SZ(A)-1,0){
    a.pb(A[i]-'0');
}
ROF(i,SZ(B)-1,0){
    b.pb(B[i]-'0');
}
vll ans=multiply(a, b);
ll carry=0;
FOR(i,0,SZ(ans)-1){
    ans[i]+=carry;
    carry=ans[i]/10;
    ans[i]%=10;
}
while (!ans.empty() && ans.back()==0) {
    ans.pop_back();
}
if(SZ(ans)==0){
    cout<<0;
    return;
}
ROF(i,SZ(ans)-1,0){
    cout<<ans[i];
}

AC代码

https://www.luogu.com.cn/record/229526218

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define lson(var) (var<<1)
#define rson(var) (var<<1|1)
#define fsp(x) fixed<<setprecision(x)
using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
#endif

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using cd=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

inline void __();
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    // cin>>lT;
    // while(lT--)
        __();
    return 0;
}
/*

*/
// 理论讲解 https://www.bilibili.com/video/BV1za411F76U/
// 参考（抄的） https://cp-algorithms.com/algebra/fft.html
// 多项式乘法 https://www.luogu.com.cn/record/229525769
using cd=complex<double>;
void fft(vector<cd> &a,bool invert){
    ll n=SZ(a);
    if(n==1) return;
    vector<cd> a0(n/2),a1(n/2); // a0 even a1 odd
    FOR(i,0,n/2-1){
        a0[i]=a[2*i];
        a1[i]=a[2*i+1];
    }
    fft(a0,invert),fft(a1,invert);
    double ang=2*pi/n*(invert?-1:1);
    cd w(1),wlen={cos(ang),sin(ang)};   // wlen 是步进长度
    FOR(i,0,n/2-1){ 
        // A(x)=Ae(x^2)+x*Ao(x^2)   A(-x)=Ae(x^2)-x*Ae(x^2)
        // a[i]=a0[i]+a1[i] -a[i]=a0[i]-a1[i]; 
        // a[i] 和 a[i+n/2] 是单位圆上相反的一对
        a[i]=a0[i]+w*a1[i];
        a[i+n/2]=a0[i]-w*a1[i];
        if(invert){ 
            // 每次都除了2，一共有log2(n)层，所以一共除了2^log2(n)=n
            a[i]/=2;
            a[i+n/2]/=2;
        }
        w*=wlen;
    }
}
vll multiply(vll &a,vll &b){
    vector<cd> fa(all(a)),fb(all(b));
    ll n=1;
    while(n<SZ(a)+SZ(b)){
        n<<=1;
    }
    fa.resize(n);fb.resize(n);
    fft(fa,false);fft(fb,false);
    FOR(i,0,n-1) fa[i]*=fb[i];
    fft(fa,true);
    vll res(n);
    //              避免精度损失
    FOR(i,0,n-1) res[i]=llround(fa[i].real());
    return res;
}
inline void __(){
    string A,B;
    cin>>A>>B;
    vll a,b;
    ROF(i,SZ(A)-1,0){
        a.pb(A[i]-'0');
    }
    ROF(i,SZ(B)-1,0){
        b.pb(B[i]-'0');
    }
    vll ans=multiply(a, b);
    ll carry=0;
    FOR(i,0,SZ(ans)-1){
        ans[i]+=carry;
        carry=ans[i]/10;
        ans[i]%=10;
    }
    while (!ans.empty() && ans.back()==0) {
        ans.pop_back();
    }
    if(SZ(ans)==0){
        cout<<0;
        return;
    }
    ROF(i,SZ(ans)-1,0){
        cout<<ans[i];
    }
}
/*
AC
https://www.luogu.com.cn/record/229526218
*/

心路历程（WA，TLE，MLE……）

P3803 【模板】多项式乘法（FFT）

Posted on 2025-08-07 Edited on 2026-04-06

思路讲解

https://www.bilibili.com/video/BV1za411F76U/

AC代码

https://www.luogu.com.cn/record/229525769

源代码

// by Gospel_rock
#include <algorithm>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define lson(var) (var<<1)
#define rson(var) (var<<1|1)
#define fsp(x) fixed<<setprecision(x)
using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
#endif

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using cd=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);

ll N,M,Q,X,K,T,lT;

inline void __();
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    // cin>>lT;
    // while(lT--)
        __();
    return 0;
}
/*

*/
// 理论讲解 https://www.bilibili.com/video/BV1za411F76U/
// 参考（抄的） https://cp-algorithms.com/algebra/fft.html
// 多项式乘法 https://www.luogu.com.cn/record/229525769
using cd=complex<double>;
void fft(vector<cd> &a,bool invert){
    ll n=SZ(a);
    if(n==1) return;
    vector<cd> a0(n/2),a1(n/2); // a0 even a1 odd
    FOR(i,0,n/2-1){
        a0[i]=a[2*i];
        a1[i]=a[2*i+1];
    }
    fft(a0,invert),fft(a1,invert);
    double ang=2*pi/n*(invert?-1:1);
    cd w(1),wlen={cos(ang),sin(ang)};   // wlen 是步进长度
    FOR(i,0,n/2-1){ 
        // A(x)=Ae(x^2)+x*Ao(x^2)   A(-x)=Ae(x^2)-x*Ae(x^2)
        // a[i]=a0[i]+a1[i] -a[i]=a0[i]-a1[i]; 
        // a[i] 和 a[i+n/2] 是单位圆上相反的一对
        a[i]=a0[i]+w*a1[i];
        a[i+n/2]=a0[i]-w*a1[i];
        if(invert){ 
            // 每次都除了2，一共有log2(n)层，所以一共除了2^log2(n)=n
            a[i]/=2;
            a[i+n/2]/=2;
        }
        w*=wlen;
    }
}
vll multiply(vll &a,vll &b){
    vector<cd> fa(all(a)),fb(all(b));
    ll n=1;
    while(n<SZ(a)+SZ(b)){
        n<<=1;
    }
    fa.resize(n);fb.resize(n);
    fft(fa,false);fft(fb,false);
    FOR(i,0,n-1) fa[i]*=fb[i];
    fft(fa,true);
    vll res(n);
    //              避免精度损失
    FOR(i,0,n-1) res[i]=llround(fa[i].real());
    return res;
}
inline void __(){
    cin>>N>>M;
    vll A(N+1),B(M+1);
    FOR(i,0,N) cin>>A[i];
    FOR(i,0,M) cin>>B[i];
    vll ans=multiply(A, B);
    // while (!ans.empty() && ans.back()==0) {
    //     ans.pop_back();
    // }
    if(ans.empty()) cout<<0;
    FOR(i,0,N+M) cout<<ans[i]<<" ";
    cout<<"\n";
}
/*
WA https://www.luogu.com.cn/record/229525510
AC https://www.luogu.com.cn/record/229525769
*/

心路历程（WA，TLE，MLE……）

那么WA了几发，发现是因为这个多项式乘法他要求的输出个数是N+M。

不用去除后导0。