CXJY-Day 8
Axell
8月 05, 2019
T1
KMP，求出每个前缀匹配的最大后缀，即Next数组，然后可以发现以i->Next[i]建立一棵树，树上的若干节点的所有lca就是符合条件的pq
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct node{
int Next,y;
}Pth[1000005];
int cnt,head[1000005];
void add(int x,int y){
cnt++;
Pth[cnt]={head[x],y};
head[x]=cnt;
}
int n,k,Next[1000005],siz[1000005];
char s[1000005];
ll A,ans[1000005],fac[1000005],mod=998244353;
ll power(ll x,ll y){
ll ret=1;
while (y){
if (y&1) ret=ret*x%mod;
x=x*x%mod;
y>>=1;
}
return ret;
}
ll C(ll x,ll y){
return fac[x]*power(fac[y],mod-2)%mod*power(fac[x-y],mod-2)%mod;
}
void dfs(int x,int dep,int prv){
siz[x]=1;
for (int i=head[x];i;i=Pth[i].Next){
int y=Pth[i].y;
if (y==prv) continue;
dfs(y,dep+1,x);
siz[x]+=siz[y];
}
if (siz[x]>=k) ans[x]+=C(siz[x],k);
ans[x]%=mod;
if (ans<0) ans[x]+=mod;
A+=ans[x]*(dep+dep+1)%mod;
A%=mod;
}
int main(){
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
cin>>k;
scanf("%s",s+1);
n=strlen(s+1);
fac[0]=1;
for (int i=1;i<=n+1;++i) fac[i]=fac[i-1]*i%mod;
for (int i=2,j=0;i<=n;++i){
while (j>0 && s[j+1]!=s[i]) j=Next[j];
if (s[j+1]==s[i]) j++;
Next[i]=j;
}
for (int i=1;i<=n;++i){
add(Next[i],i);
}
dfs(0,0,-1);
cout<<A<<endl;
return 0;
}T2
TODO
#include<bits/stdc++.h>
using namespace std;
const int MX=2005,CHARC=257,MXL=8000000;
const int dx[4]={0,-1,0,1},dy[4]={1,0,-1,0};
const char op[4]={'R','U','L','D'};
int dir[CHARC];
const char ch[4][2]={ {'<','>'},{'u','n'},{'>','<'},{'n','u'}};
int n,m,RINGC;
char a[MX][MX],b[MX][MX];
bool vis[MX][MX];
char ans[MXL+5];int ansc;
void ini(){
dir['<']=0,dir['>']=2,dir['u']=1,dir['n']=3;
}
void move(int di,int &x,int &y){
ans[ansc++]=op[di];
int xt=x+dx[di],yt=y+dy[di];
if(xt<0||xt>=n||yt<0||yt>=m)return;
int xx=xt+dx[dir[a[xt][yt]]],yy=yt+dy[dir[a[xt][yt]]];
a[x][y]=ch[di][0],a[xt][yt]=ch[di][1];
x=xx,y=yy;
a[x][y]='o';
}
void work0(int &x,int &y){ // the augment path between two 'o's
while(b[x][y]!='o'){
move(dir[b[x][y]],x,y);
}
}
void reducering(int &x,int &y,int di){
int x0=x,y0=y;
move(di,x,y);
while(x!=x0||y!=y0){
move(dir[b[x][y]],x,y);
}
}
void dfs(int &x,int &y){
vis[x][y]=true;
for(int i=0;i<4;i++){
int xt=x+dx[i],yt=y+dy[i];
if(xt<0||xt>=n||yt<0||yt>=m||a[xt][yt]=='#')continue;
if(vis[xt][yt])continue;
if(a[xt][yt]!=b[xt][yt]){ // found a ring
++RINGC;
reducering(x,y,i);
}
vis[xt][yt]=true;
int td=dir[a[xt][yt]];
move(i,x,y);
dfs(x,y);
move(td^2,x,y);
}
}
bool check(){
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(a[i][j]!=b[i][j])
return false;
return true;
}
void solve(){
int x,y;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(a[i][j]=='o')x=i,y=j;
work0(x,y);
dfs(x,y);
if(check())cout<<ans<<endl;
else cout<<"I"<<endl;
}
int main(){
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
ios::sync_with_stdio(false);
ini();
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)
cin>>b[i];
solve();
return 0;
}T3
TODO
#include <cstdio>
#include <iostream>
#include <cstring>
#include <tr1/unordered_map>
#include <cmath>
#include <algorithm>
//#define int long long
using namespace std;
using namespace tr1;
const int maxn = 200000 + 10, mod = 998244353;
void R(int &x) {
x = 0;
char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') {
x = (x << 3) + (x << 1) + c - '0';
c = getchar();
}
}
int Prime[maxn], vis[maxn], Z[maxn], V[maxn], G[maxn], Inv6, Cnt[maxn], n, m, q, K[maxn], Lim;
int qpow(int x, int y) {
int ans = 1;
while (y) {
if (y & 1)
ans = 1ll * x * ans % mod;
x = 1ll * x * x % mod;
y >>= 1;
}
return ans;
}
int Sum(int x) { return 1ll * x * (x + 1) % mod * ((2 * x + 1) % mod) % mod * Inv6 % mod; }
int add(int x, int y) {
x += y;
if (x >= mod)
x -= mod;
return x;
}
void Get() {
for (int i = 2; i < maxn; i++) {
if (!vis[i])
Prime[++Prime[0]] = i;
for (int j = 1; j <= Prime[0]; j++) {
if (1ll * i * Prime[j] >= maxn)
break;
vis[i * Prime[j]] = 1;
if (i % Prime[j] == 0)
break;
}
}
}
void work(int x) {
if (Z[0] == 10)
return;
int k = sqrt(x);
for (int i = 1; i <= Z[0]; i++)
if (x % Z[i] == 0) {
while (x % Z[i] == 0) x /= Z[i];
}
for (int i = 1; Prime[i] <= k; i++) {
if (x == 1)
break;
if (x % Prime[i] == 0) {
Z[++Z[0]] = Prime[i];
while (x % Prime[i] == 0) x /= Prime[i];
}
}
if (x != 1)
Z[++Z[0]] = x;
}
void Calc() {
Lim = sqrt(n);
for (int i = 1; i <= n; i = V[V[0]] + 1) {
V[++V[0]] = n / (n / i);
G[V[0]] = Sum(V[V[0]]);
}
for (int w = 1; w <= Z[0]; w++) {
int p = Z[w], p2 = 1ll * p * p % mod;
for (int i = V[0]; V[i] >= p; i--) {
int to = V[i] / p;
if (to > Lim)
to = V[0] - n / to + 1;
G[i] = (G[i] - 1ll * G[to] * p2 % mod + mod) % mod;
}
}
}
unordered_map<int, int> P;
void dfs(int w, int data) {
if (w == Z[0] + 1) {
Cnt[++Cnt[0]] = data;
if (!P.count(data))
P[data] = 0;
return;
}
dfs(w + 1, data);
while (1ll * data * Z[w] <= n) {
data *= Z[w];
dfs(w + 1, data);
}
}
signed main() {
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
Get();
Inv6 = qpow(6, mod - 2);
R(n);
R(m);
R(q);
for (int i = 1; i <= m; i++) {
int p, x;
R(p);
R(x);
work(p);
if (!P.count(p))
P[p] = 0;
P[p] = (P[p] + x) % mod;
}
while (q--) {
int x;
R(x);
K[++K[0]] = x;
work(x);
}
sort(Z + 1, Z + 1 + Z[0]);
dfs(1, 1);
sort(Cnt + 1, Cnt + 1 + Cnt[0]);
for (int w = 1; w <= Z[0]; w++) {
int p = Z[w];
for (int i = 1; i <= Cnt[0]; i++) {
if (Cnt[i] % p != 0)
continue;
int tmp = Cnt[i] / p;
while (!P.count(tmp)) tmp /= p;
P[Cnt[i]] = add(P[Cnt[i]], 1ll * (Cnt[i] / tmp) * P[tmp] % mod) % mod;
}
}
Calc();
for (int i = 1; i <= Cnt[0]; i++) {
int to = n / Cnt[i];
if (to > Lim)
to = V[0] - n / to + 1;
P[Cnt[i]] = 1ll * P[Cnt[i]] * G[to] % mod;
}
for (int w = 1; w <= Z[0]; w++) {
int p = Z[w];
for (int i = Cnt[0]; i >= 1; i--) {
if (1ll * Cnt[i] * p > n)
continue;
int tmp = Cnt[i] * p;
while (!P.count(tmp) && 1ll * tmp * p <= n) tmp *= p;
if (P.count(tmp))
P[Cnt[i]] = add(P[Cnt[i]], 1ll * P[tmp] * (tmp / Cnt[i]) % mod);
}
}
for (int i = 1; i <= K[0]; i++) printf("%d\n", P[K[i]]);
}匹配
匹配的任意两条边没有公共顶点
TODO：二分图最大匹配
生成树
BZOJ 2654
http://uoj.ac/problem/3
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/cxjy-day-8/
