好久沒寫了，問題還蠻多的。聽說這次是苯環哥哥出題
F題 小苯的因子查詢
思路
考慮求因子個數，用質因數分解；奇數因子只需要去掉質數為2的情況，用除法。
這里有個比較妙的細節是，提前處理出數字x的最小質因數，當然不處理也沒關系。
我出的bug
- 忘記逆元怎么求了，甚至連名字都忘記了，想了一會才想起來
- 1e6的讀入，忘記禁用同步和解除綁定了
- const int mod=998244353; 少了const
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ft first
#define sd second
const int mod=998244353;
const int N=1e6+10;
int prime[N],kk,vis[N];
pair<int,int> ans[N];//記錄第i個的奇數個數，因子個數
int total[N];//質因子為i的次冪int power(int x,int y)
{int res=1;while(y){if(y&1) res=res*x%mod;y/=2;x=x*x%mod;}return res%mod;
}
int inv(int y) {return power(y,mod-2);}
void Prime()
{for(int i=2;i<N;i++){if(vis[i]==0) prime[++kk]=i,vis[i]=kk;for(int j=i+i;j<N;j+=i){if(vis[j]==0) vis[j]=kk;//vis記錄最小質因數的編號，編號從1開始}}
}
void init()
{Prime();ans[1].ft=ans[1].sd=1;for(int i=2;i<N;i++)//遞推，更新下一個ans{int j=vis[i],tmp=i;while(j>0){int cnt=0;while(tmp%prime[j]==0)cnt++,tmp/=prime[j];if(total[prime[j]]==0)//增加一個質因子的情況{ans[i].sd=ans[i-1].sd*(cnt+1)%mod;}else //已有質因子的情況{ans[i].sd=ans[i-1].sd*inv(total[prime[j]]+1)%mod*(total[prime[j]]+cnt+1)%mod;}total[prime[j]]+=cnt;j=vis[tmp];}ans[i].ft=ans[i].sd*inv(total[2]+1)%mod;}
}
int solve(int n)
{int x=ans[n].ft;int y=ans[n].sd;int inv_y=inv(y);//cout<<x<<" "<<y<<" ";return x*inv_y%mod;}
signed main()
{//ios::sync_with_stdio(false);cin.tie(0);init();int n,t;ios::sync_with_stdio(0);cin.tie(0);cin>>t;while(t--){cin>>n;cout<<solve(n)<<" ";}return 0;
}一般大佬的Coding：
#include <bits/stdc++.h>
using namespace std;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
#define int long long
#define rep(i, a, b) for (int (i) = (a); (i) <= (b); ++i)
#define rep2(i, a, b) for (int (i) = (a); (i) >= (b); --i)
#define debug(x) std::cout << #x << " : " << x << "\n";
#define debug2(x,y) std::cout << #x << " : " << x << " " << #y << " : " << y << "\n";
const int MOD = 998244353;
const int N = 1e6 + 10;
long long power(long long a, int b, int p) {long long res = 1;while (b) {if (b & 1) res = res * a % p;b >>= 1;a = a * a % p;}return res;
}
long long inv(int x) { return power(x, MOD - 2, MOD); }
int fac[N];
void init() {fac[0] = 0;for (int i = 1; i <= N - 1; i++) {fac[i] = fac[i - 1] + __builtin_ctz(i);}
}
void solve()
{int n; cin >> n;cout << inv(fac[n] + 1) << " ";
}
signed main()
{std::ios::sync_with_stdio(false);// cout<<std::fixed<<std::setprecision(10);std::cin.tie(0);init();int t__ = 1;cin >> t__;while (t__--)solve();return 0;
}
D題 數組4.0
思路
排序分段，段和段之間只需一條邊即可連接；段和單點之間需要再考慮單點內部連接。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m;
int b[N],cnt[N];
int ans=0;void solve()
{if(n==1){cout<<0<<"\n";return ;}//只有一個數sort(b,b+n);m=unique(b,b+n)-b;if(m==1){cout<<n-1<<"\n";return ;}//只有一個元素ans=0;bool p=0;// p==1時，說明這是一段的左邊或者內部，而不是單點for(int i=1;i<m;i++){if(b[i]-b[i-1]==1){p=1;continue;}ans++;if(p==0) ans+=cnt[b[i-1]]-1; //說明上一段結束，此時也結束，說明上個點是單點p=0;}if(p==0)ans+=cnt[b[m-1]]-1;//單點cout<<ans<<"\n";}
signed main()
{int t;cin>>t;while(t--){for(int i=0;i<N;i++)cnt[i]=0;cin>>n;for(int i=0;i<n;i++)cin>>b[i],cnt[b[i]]++;solve();}return 0;
}
/*
1
7
1 2 4 4 6 7 8
*/
小苯的逆序對和
思路
簡單的思維題，直覺雙指針，然后把自己繞進去，最后畫座多峰的山就好理解了。
l找峰頂，mx記錄當前最高的峰頂，j作為指針，遍歷完滿足當前低于最高峰頂mx的最大答案，否則繼續更新l。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m;
int b[N],cnt[N];
int ans=0;void solve()
{int l=0,r=n-1;ans=0;int mx=b[l];while(l<r){while(l<r&&b[l]<b[l+1])l++;//左邊找這一段最大的,山峰if(l==r)break;mx=max(mx,b[l]);//此時最高的山峰int j=l+1;while(j<=r&&mx>b[j]){ans=max(mx+b[j],ans);j++;}l=j;}cout<<ans<<'\n';
}
signed main()
{int t;cin>>t;while(t--){cin>>n;for(int i=0;i<n;i++)cin>>b[i];solve();}return 0;
}
/*
1
7
1 2 4 4 6 7 8
*/
B題 token
前綴和，檢查兩遍才發現忘記開long long了，代碼就不展示了。
)
