rank 15 T1 100，T2 80 ，T3 9，T4 0
本来不想交的，但快结束的时候回头看见huge在看着我就慌了。
T1 新的阶乘
签到题，将跑个类似于埃氏筛的东西就行了，时间复杂度\(O(n\log\log n)\)。
点此查看代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t;i += p)
#define drep(i,s,t,p) for(int i = s;i >= t;i -= p)
#ifdef LOCAL
FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
#else
FILE *InFile = freopen("factorial.in","r",stdin),*OutFile = freopen("factorial.out","w",stdout);
#endif
using ll = long long;using ull = unsigned long long;
using db = double;using ldb = long double;
#define int long long
const int N = 1e7 + 10;
vector<int> prime;
bool vis[N];int n;
inline void euler(int n){
rep(i,2,n,1){
if(!vis[i]) prime.emplace_back(i);
for(auto j:prime){
if(i * j > n) break;
vis[i * j] = true;
}
}
}
int num[N],have[N];
inline void solve(){
cin>>n;
// if(n == 1) return cout<<"f(1)=1\n",void();
euler(n);
for(auto i:prime){
int tot = 1,f = 1;
for(int j = i;j <= n;j += i){
num[i] += (have[j] = have[j/i] + 1)*(n - j + 1);
}
for(int j = i;j <= n; j += i) have[j] = 0;
}
cout<<"f("<<n<<")=";
#define pii pair<int,int>
#define mk make_pair
vector<pii> ans;
for(int i = 0;i < prime.size(); ++i)
if(num[prime[i]]) ans.emplace_back(mk(prime[i],num[prime[i]]));
for(int i = 0;i < ans.size(); ++i){
if(ans[i].second == 1) cout<<ans[i].first;
else cout<<ans[i].first<<'^'<<ans[i].second;
if(i != ans.size() - 1) cout<<'*';
}
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
solve();
}
博弈树
80pts是记搜，随便打。
看到这个题先想打表找规律，发现当无法走的时候肯定是到了树的直径的一个顶点，所以先求出树的直径。
发现谁先从直径的一个端点走到另一个端点时谁就赢，所以如果先手一开始在直径的端点处就赢了。
如果先手一开始不在直径端点处，那么两个人肯定会在直径上磨蹭，大概就是你往左走n个我往右走n+1个这样，直到另一方到达直径的一个端点。
如果先手一开始不在直径上，那么一定会直接跳到直径上。然后就这样模拟，发现当且仅当先手一开始在直径中点时，后手会赢。
至于一棵树有好几条直径，都一样的。
点此查看代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t;i += p)
#define drep(i,s,t,p) for(int i = s;i >= t;i -= p)
#ifdef LOCAL
FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
#else
FILE *InFile = freopen("tree.in","r",stdin),*OutFile = freopen("tree.out","w",stdout);
#endif
using ll = long long;using ull = unsigned long long;
using db = double;using ldb = long double;
const int N = 1e5 + 10;
#define eb emplace_back
vector<int> e[N];
int n,q,dist[N],fa[N];
inline int bfs(int s){
queue<int> q;bitset<N> vis;
q.push(s);dist[s] = 1;vis.set(s);
int ed = s,edn = 0;
while(q.size()){
int x = q.front();q.pop();
for(int y:e[x]){
if(vis[y]) continue;
dist[y] = dist[x] + 1;
fa[y] = x;q.push(y);
vis[y] = true;
if(dist[y] > edn) edn = dist[y],ed = y;
}
}
return ed;
}
inline void solve(){
cin>>n>>q;rep(i,1,n-1,1){int u,v;cin>>u>>v;e[u].eb(v);e[v].eb(u);}
int s,t;t = bfs(s = bfs(1));
int dis = dist[t];
if(dis&1){
int x = t;
while(fa[x]){if(dist[x] <= (dis+1)/2) break;x = fa[x];}
while(q--){
int p;cin>>p;
if(p == x) cout<<"Bob\n";
else cout<<"Alice\n";
}
}
else while(q--) cout<<"Alice\n";
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
solve();
}
T3 划分
简单题，赛时没想到确实唐。
如果前k位没有1，那么最优解一定是第1个1之前选分至少\(k-1\)段，直接组合数。
反之，发现最优解一定是选出一段\(n-k+1\)的，剩下的每个数单独分一块。
考虑如何判断二进制数大小，用The classic problem那个二分+哈希的方法求出lcp长度，然后看后一位大小即可。
因为害怕被卡写的三模数哈希，然后喜提最裂解。
点此查看代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t;i += p)
#define drep(i,s,t,p) for(int i = s;i >= t;i -= p)
#ifdef LOCAL
FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
#else
FILE *InFile = freopen("divide.in","r",stdin),*OutFile = freopen("divide.out","w",stdout);
#endif
using ll = long long;using ull = unsigned long long;
using db = double;using ldb = long double;
const int N = 2e6 + 10,mod = 998244353;
struct ThreeModHash{
ll p1[N],h1[N];const ll m1 = 2432021027;
ll p2[N],h2[N];const ll m2 = 998244353;
ll p3[N],h3[N];const ll m3 = 1e9+3579;
inline void init(char *s){
int n = strlen(s+1);
p1[0] = p2[0] = p3[0] = 1;
rep(i,1,n,1) p1[i] = 1ll*p1[i-1]*2707%m1;
rep(i,1,n,1) p2[i] = 1ll*p2[i-1]*2%m2;
rep(i,1,n,1) p3[i] = 1ll*p3[i-1]*233%m3;
rep(i,1,n,1) h1[i] = (h1[i-1]*2707+s[i])%m1;
rep(i,1,n,1) h3[i] = (h3[i-1]*233+s[i])%m3;
rep(i,1,n,1) h2[i] = (h2[i-1]*2+s[i]-'0')%m2;
}
inline ll get1(int l,int r){return (h1[r] - h1[l-1]*p1[r-l+1]%m1+m1)%m1;}
inline ll get2(int l,int r){return (h2[r] - h2[l-1]*p2[r-l+1]%m2+m2)%m2;}
inline ll get3(int l,int r){return (h3[r] - h3[l-1]*p3[r-l+1]%m3+m3)%m3;}
inline bool cmp(int l1,int r1,int l2,int r2){
return (get1(l1,r1) == get1(l2,r2) && get2(l1,r1) == get2(l2,r2) && get3(l1,r1) == get3(l2,r2));
}
}hs;
namespace Combination{
const int mod = 998244353;
inline int power(int a,int b,int mod){
int res = 1;
for(;b;b >>= 1,a = 1ll*a*a%mod)
if(b&1) res = 1ll*res*a%mod;
return res;
}
inline int Inv(int a){return power(a,mod-2,mod);}
int fac[N],inv[N];
inline void init(int n){
fac[0] = 1;rep(i,1,n,1) fac[i] = 1ll*fac[i-1]*i%mod;
inv[n] = Inv(fac[n]);drep(i,n-1,0,1) inv[i] = 1ll*inv[i+1]*(i+1)%mod;
}
inline int C(int n,int m){return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;}
}using Combination::C;
int n,k,fst,sum[N];char s[N];
inline void solve1(){
int len = n - k,ans = 0,p = fst;
rep(i,fst,k,1) if(sum[i + len - 1] - sum[i - 1] == len) ans++,p = i;
if(ans){
cout<<(hs.get2(p,p+len-1)*2+sum[n]-len+mod)%mod<<' '<<ans<<'\n';
return;
}
ans = 1;
rep(i,fst + 1,k,1){
int l = 1,r = len + 1,res = 1;
while(l <= r){
int mid = (l + r) >> 1;
if(hs.cmp(i,i+mid-1,p,p+mid-1)) res = mid,l = mid + 1;
else r = mid - 1;
}
// l = res;
if(res == len + 1) ans++;
if(l < len && s[p+l-1] < s[i+l-1]) p = i,ans = 1;
}
// cerr<<p<<'\n';
// cerr<<hs.get2(p,p+len-1)<<'\n';
cout<<(hs.get2(p,p+len-1)*2+sum[n]-(sum[p+len-1]-sum[p-1]))%mod<<' ';
cout<<ans<<'\n';
}
inline void solve(){
cin>>n>>k>>(s+1);hs.init(s);
Combination::init(n);fst = n;
rep(i,1,n,1) if(s[i] == '1'){fst = i;break;}
rep(i,1,n,1) sum[i] = sum[i - 1] + s[i] - '0';
if(n == k) return cout<<sum[n]<<' '<<1<<'\n',void();
if(fst >= k){
cout<<hs.get2(fst,n)<<' ';
int ans = 0;
rep(i,k-1,fst-1,1) ans = (ans + C(fst-1,i)) % mod;
cout<<ans<<'\n';
return void();
}
solve1();
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
solve();
}
划分
打的\(O(n2^k\log n)\)的爆搜，然后由于忘记将调试改回去了挂了8pts。
不会
