Znzryb's Blog

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

Posted on 2025-08-07 Edited on 2026-02-18

思路讲解

使用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-02-18

思路讲解

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。

2025牛客暑期多校训练营8——Inversion Number Parity

Posted on 2025-08-07 Edited on 2026-02-18

思路讲解

AC代码

源代码

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

START198B——Minimize Maximum Mex

Posted on 2025-08-06 Edited on 2026-02-18

思路讲解

这个检查器还是有点难想到怎么样去写的。

auto check=[&](ll mid){
    bool oka=false,okb=false;;
    FOR(i,0,mid){
        if(cnta[i]==0){
            oka=true;
        }
        if(cntb[i]==0){
            okb=true;
        }
    }
    if(oka && okb){
        return true;
    }
    ll cnt=0;
    FOR(i,0,mid){   // 只要不是强制的，一定可以让i都在A中，或者i都在b中
        if(!forced[i]) ++cnt;
    }
    if(cnt>=2) return true;
    return false;
};

AC代码

源代码

// by Gospel_rock
#include <algorithm>
#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;

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 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>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+9; // 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;
}
/*

*/
inline void __(){
    cin>>N;
    vll A(N),B(N);
    set<ll> memo;
    FOR(i,0,N+5){
        memo.insert(i);
    }
    vll cnta(N+5),cntb(N+5);
    FOR(i,0,N-1){
        cin>>A[i];
        ++cnta[A[i]];
    }
    FOR(i,0,N-1){
        cin>>B[i];
        ++cntb[B[i]];
    }
    vb forced(N+5,false);
    FOR(i,0,N-1){
        if(A[i]==B[i]) forced[A[i]]=true;
    }
    auto check=[&](ll mid){
        bool oka=false,okb=false;;
        FOR(i,0,mid){
            if(cnta[i]==0){
                oka=true;
            }
            if(cntb[i]==0){
                okb=true;
            }
        }
        if(oka && okb){
            return true;
        }
        ll cnt=0;
        FOR(i,0,mid){   // 只要不是强制的，一定可以让i都在A中，或者i都在b中
            if(!forced[i]) ++cnt;
        }
        if(cnt>=2) return true;
        return false;
    };
    ll low=0,hig=N+3;
    while(low<hig){
        ll mid=low+hig>>1;
        if(check(mid)){
            hig=mid;
        }else{
            low=mid+1;
        }
    }
    cout<<low<<"\n";
}
/*
AC
https://www.codechef.com/viewsolution/1179820888
1
4
2 3 1 2
1 3 1 3
*/

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

START198B——Restricted Removals（字符串）

Posted on 2025-08-06 Edited on 2026-02-18

思路讲解

https://www.codechef.com/viewsolution/1179874822

我们的贪心做法用AI树状数组给过去了（其实我也想到了，但是我觉得复杂度也太离谱了吧，就没试）。

my solution is a kind of greedy.

It is not difficult to observe that delete the last element matched is the best, because it affect the least elements.

so just do it.

certainly, using vector or list can not go through all tests.

but if you using fenwick tree which can find the kth element, all problems will be solved.

AC代码

https://www.codechef.com/viewsolution/1179893708

源代码

// 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;

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 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>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+9; // 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 __();
// by znzryb
// 普通的单点修改区间查询树状数组，含有查找第K个空位，第K个元素的功能
// https://www.codechef.com/viewsolution/1179893708 第K个元素测试
// 第K个空位的测试应该是一道abc的题目，但是当时没保存
struct BIT { 
    vector < ll > tr;
    int n;
    inline int lowbit(int x) {
        return x & (-x);
    }
    BIT(int ln) { // 构造+初始化函数
        n = ln;
        tr.resize(n + 5, 0);
    }
    inline void add(int p, int x) {
        if (p == 0) return;
        while (p <= n) {
            tr[p] += x;
            p += lowbit(p);
        }
    }
    inline ll query(int l, int r) {
        ll lres = 0, rres = 0;
        l -= 1;
        while (l > 0) {
            lres += tr[l];
            l -= lowbit(l);
        }
        while (r > 0) {
            rres += tr[r];
            r -= lowbit(r);
        }
        return rres - lres;
    }
    inline int findkth(int k) { // 找到第k个元素，当然应当是要求只能出现0和1
        int x = 0,sum=0;
        for(int i=__lg(n);~i;--i){
            x+=1<<i;
            if(x>=n || sum+tr[x]>=k){
                x-=1<<i;
            }else{
                sum+=tr[x];
            }
        }
        return x + 1; // 我们始终让cx < k，所以返回的就是最大的比k小的，+1就是新元素出现的地方
    }
    inline int kthspace(int k) {  // 找到第k个空位，当然应当是要求只能出现0和1
        int cx = 0;
        for (int i = 1 << 20; i > 0; i >>= 1) {  // 这个你可以理解为不断缩小步长的搜索
          if (cx + i <= n && lowbit(cx + i) - tr[cx + i] < k) {
            // lowbit(cx)-tr[cx+i] 表示cx+i这个树状数组区间有多少空位
            k -= lowbit(cx + i) - tr[cx + i];
            cx += i;
          }
        }
        return cx + 1;  // 我们始终让cx < k，所以返回的就是最大的比k小的，+1就是新空位出现的地方
      }
};

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

*/
inline void __(){
    cin>>N>>M;
    vll A(N+5),B(M+5);
    FOR(i,1,N){
        cin>>A[i];
    }
    FOR(i,1,M){
        cin>>B[i];
    }
    BIT tr(max(N,M)+5);
    FOR(i,1,N){
        tr.add(i,1);
    }
    ll n=N;
    // vb vis(N+5);
    while (n) {
        ll lim=min(M,n);
        bool ok=false;
        ROF(i,lim,1){
            ll pos=tr.findkth(i);
            if(A[pos]==B[i]){
                tr.add(pos,-1);
                ok=true;
                break;
            }
        }
        if(!ok) break;
        n--;
    }
    cout<<n<<"\n";
}
/*
AC
https://www.codechef.com/viewsolution/1179893708
1
3 2
1 0 1
1 1

1
3 2
0 0 1
0 0

*/