选取字符串
建出失配树以后直接dp就好了。但场上现推的kmp……
点此查看代码
#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("string.in","r",stdin),*OutFile = freopen("string.out","w",stdout);
// FILE *InFile = stdin,*OutFile = 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 = 1e6 + 10,mod = 998244353;
int n,k,fac[N<<2],inv[N<<2],sum[N],nxt[N],ct[N],dep[N],siz[N],ans = 0;
char s[N];
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);}
inline int C(int n,int m){
if(m > n) return 0;
return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
vector<int> son[N];
void dfs(int x){
dep[x] = dep[nxt[x]] + 1;
siz[x] = 1;
for(auto y:son[x]){
dfs(y);
siz[x] += siz[y];
ct[x] = (ct[x] - C(siz[y],k) + mod)%mod;
}
ct[x] = (ct[x] + C(siz[x],k))%mod;
ans = (ans + 1ll*ct[x]*dep[x]%mod*dep[x]%mod)%mod;
}
inline void solve(){
cin>>k>>(s+1);n = strlen(s+1);
n<<=2;
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;
n>>=2;
int j = 0;
son[0].emplace_back(1);
rep(i,2,n,1){
while(j && s[i] != s[j+1]) j = nxt[j];
j += (s[i] == s[j+1]);
nxt[i] = j;son[nxt[i]].emplace_back(i);
}
dfs(0);
cout<<ans;
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
solve();
}
取石子
打表找规律发现当且仅当\(lowbit(\oplus_ia_i)\le k\)时先手必胜。
然后发现每次增加的一定为\(2^k\)且不降，直接暴力枚举即可，时间复杂度\(O(n\log V)\)。
点此查看代码
#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 = stdin,*OutFile = stdout;
FILE *InFile = freopen("nim.in","r",stdin),*OutFile = freopen("nim.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 = 5e4 + 10;
int n,k,a[N];
bool f[50],flag,cp[50];
inline void solve(){
cin>>n>>k;rep(i,1,n,1) cin>>a[i];
int lgk = __lg(k);
rep(i,0,lgk,1){rep(j,1,n,1) f[i]^=(a[j]>>i)&1;flag |= f[i];}
if(!flag) cout<<"0\n";
else{
cout<<"1\n";
rep(i,1,n,1){
rep(j,0,lgk,1) cp[j] = f[j];
int sum = 0;
rep(j,0,__lg(a[i]),1){
if(!cp[j]) continue;
sum |= 1<<j;
if(sum > k) break;
cout<<i<<' '<<sum<<'\n';
rep(l,j,lgk,1) cp[l] ^= a[i]>>l&1;
a[i] -= 1<<j;
rep(l,j,lgk,1) cp[l] ^= a[i]>>l&1;
}
}
}
}
signed main(){cin.tie(nullptr)->sync_with_stdio(false);solve();}
均衡区间
记\(ml_{i},sl_{i},mr_{i},sr_{i}\)分别表示左边第一个比\(a_i\)大的数的位置，左边第一个比\(a_i\)小的数的位置，右边第一个比\(a_i\)大的数的位置，右边第一个比\(a_i\)小的数的位置。记\(L_{i}=\min\{ml_{i},sl_{i}\}\)
假如\([i,j]\)是一个合法区间，那么有\(i<L_{j}\And R_{i}<j\)，二维数点。正反求两遍就好了。
点此查看代码
#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 = stdin,*OutFile = stdout;
FILE *InFile = freopen("interval.in","r",stdin),*OutFile = freopen("interval.out","w",stdout);
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 1e6 + 10;
int n,a[N],ans1[N],ans2[N],id;
int mr[N],ml[N],sr[N],sl[N],L[N],R[N];
struct BIT{
int mx,tree[N];
inline void init(int n){mx = n;memset(tree,0,sizeof tree);}
inline int lb(int x){return (x&(-x));}
inline void upd(int pos,int val){rep(i,pos,mx,lb(i)) tree[i] += val;}
inline int qry(int pos){int res = 0;drep(i,pos,1,lb(i)) res += tree[i];return res;}
}T;
stack<int> sta;
inline void get(int *ans){
drep(i,n,1,1){while(sta.size() && a[sta.top()] < a[i]) ml[sta.top()] = i,sta.pop();sta.push(i);}
while(sta.size()) ml[sta.top()] = 1,sta.pop();
drep(i,n,1,1){while(sta.size() && a[sta.top()] > a[i]) sl[sta.top()] = i,sta.pop();sta.push(i);}
while(sta.size()) sl[sta.top()] = 1,sta.pop();
rep(i,1,n,1){while(sta.size() && a[sta.top()] < a[i]) mr[sta.top()] = i,sta.pop();sta.push(i);}
while(sta.size()) mr[sta.top()] = n,sta.pop();
rep(i,1,n,1){while(sta.size() && a[sta.top()] > a[i]) sr[sta.top()] = i,sta.pop();sta.push(i);}
while(sta.size()) sr[sta.top()] = n,sta.pop();
rep(i,1,n,1) L[i] = min(ml[i],sl[i]),R[i] = max(mr[i],sr[i]);
T.init(n);vector<pair<int,int> > vec;
rep(i,1,n,1) vec.emplace_back(L[i],i);
sort(vec.begin(),vec.end(),greater<pair<int,int> >());
int now = -1;
drep(i,n,1,1){
while(now < n-1 && vec[now+1].first > i){now++;T.upd(vec[now].second,1);}
ans[i] = T.qry(T.mx)-T.qry(R[i]);
}
}
inline void solve(){
cin>>n>>id;rep(i,1,n,1) cin>>a[i];
get(ans1);
rep(i,1,n,1) cout<<ans1[i]<<' ';cout<<'\n';
reverse(a+1,a+1+n);get(ans2);
reverse(ans2+1,ans2+1+n);
rep(i,1,n,1) cout<<ans2[i]<<' ';
}
signed main(){cin.tie(nullptr)->sync_with_stdio(false);solve();}
禁止套娃
不会。
p
