Starry

发表于 更新于 分类于 本文字数： 338 阅读时长 ≈ 1 分钟

暴力枚举集合划分，然后字符串哈希更新答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

using ll=long long;

const ull P=13;
const int maxn=125009; 
ull ha[maxn],po[maxn],tar;
vector<char> ls;
string s,t;
int ans[maxn],tot,cov[386];

ull gethash(int l,int r){
	return ha[r]-ha[l-1]*po[r-l+1];
}

int id(char a){return lower_bound(all(ls),a)-ls.begin()+1;}

void gen_ha(){
	tar=0;
	for(auto it:t)tar=tar*P+cov[id(it)];
	for(int i=1;i<=s.size();++i)ha[i]=ha[i-1]*P+cov[id(s[i-1])];
}

void solve(){
	for(int i=1;i+t.size()-1<=s.size();++i){
		if(gethash(i,i+t.size()-1)==tar){
			ans[i]=min(ans[i],(int)(ls.size())-tot);
		}
	}
}

void dev(int dep){
	if(dep>ls.size()){
		gen_ha();
		solve();
		return;
	}
	cov[dep]=++tot;
	dev(dep+1);
	tot-=1;
	for(int i=1;i<=tot;++i){
		cov[dep]=i;
		dev(dep+1);
	}
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(ans,0x3f,sizeof(ans));
    set<char> se;
    cin>>s>>t;
    for(auto it:s)se.insert(it);
    for(auto it:t)se.insert(it);
    for(auto it:se)ls.push_back(it);
    sort(all(ls));
    po[0]=1;
    for(int i=1;i<=s.length();++i)po[i]=P*po[i-1];
    dev(1);
	for(int i=1;i+t.size()-1<=s.size();++i)cout<<ans[i]<<" \n"[i+t.size()-1==s.size()];
    return 0;
}

发表于 更新于 分类于 本文字数： 713 阅读时长 ≈ 3 分钟

考虑a只有一个和多个这两种本质不同计数方法。

一个的数量为,则有

多个的数量为,则有

而对于每个b，我们可以用NTT算出需要至个a的方案数

于是就得到一个方案，枚举b用NTT计算出a贡献，然后再枚举问询加上相应的贡献到答案上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

using ll=long long;

const int mod=998244353;
const int g=3,gi=332748118,NR=1<<21;
ll n=1e6,k,a[(int)3e5+9],b[(int)3e5+9],q,c[(int)3e5+9],precn1[(int)3e5+9],po[(int)1e6+9],precn2[(int)3e5+9],ans[(int)3e5+9],bit,len;
int fac[(int)1e6+9],inv[(int)1e6+9];
int A[NR],B[NR],rev[NR];

int C(int n,int m){
	if(m>n||n<0||m<0)return 0;
	return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}

int powmod(int a,int b){
	int res=1;
	for(;b>0;b>>=1,a=1ll*a*a%mod)if(b&1)res=1ll*res*a%mod;
	return res;
}

void NTT(int *a,int type){
	for(int i=0;i<len;++i)if(rev[i]>i)swap(a[rev[i]],a[i]);
	for(int k=1;k<len;k<<=1){
		int wn=powmod(type==1?g:gi,(mod-1)/(k<<1));
		for(int i=0;i<len;i+=(k<<1)){
			int w=1;
			for(int j=0;j<k;++j,w=1ll*w*wn%mod){
				int x=a[i+j],y=1ll*a[i+j+k]*w%mod;
				a[i+j]=(x+y)%mod,a[i+j+k]=(x-y+mod)%mod;
			}
		}
	}
	if(type==1)return;
	int invn=powmod(len,mod-2);
	for(int i=0;i<len;++i)a[i]=1ll*a[i]*invn%mod;
}

void solve(){
	for(int i=1;i<=k;++i){
		ll cn1=precn1[b[i]-1],cn2=precn2[b[i]-1];
		len=1,bit=0;
		while(len<(cn1+2ll*cn2+1ll))len<<=1,bit+=1;
		for(int i=0;i<len;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
		for(int i=0;i<len;++i)A[i]=C(cn1,i)*po[i]%mod,B[i]=C(2ll*cn2,i);
		NTT(A,1),NTT(B,1);
		for(int i=0;i<len;++i)A[i]=1ll*A[i]*B[i]%mod;
		NTT(A,0);
		for(int j=1;j<=q;++j){
			ll sy=(c[j]-2)/2-b[i];
			if(sy>=0&&sy<len){
				ans[j]=(ans[j]+A[sy])%mod;
			}
		}
	}
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    po[0]=fac[0]=inv[0]=1;
    for(int i=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%mod,po[i]=2ll*po[i-1]%mod;
    inv[n]=powmod(fac[n],mod-2);
	for(int i=n-1;i;--i)inv[i]=1ll*inv[i+1]*(i+1)%mod;
    cin>>n>>k;
    for(int i=1,x;i<=n;++i)cin>>x,a[x]+=1;
    for(int i=1;i<=3e5;++i)precn1[i]=precn1[i-1]+(a[i]==1),precn2[i]=precn2[i-1]+(a[i]>1);
    for(int i=1;i<=k;++i)cin>>b[i];
    cin>>q;
    for(int i=1;i<=q;++i)cin>>c[i];
    solve();
	for(int i=1;i<=q;++i)cout<<ans[i]<<"\n";
    return 0;
}

发表于 更新于 分类于 本文字数： 258 阅读时长 ≈ 1 分钟

回头膜一下jls的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

using ll=long long;

ll tt,n,k,fa[(int)2e5+9],cnt; 
vi g[(int)2e5+9];

ll dfs(int u,int fa,int dep,ll x){
	ll res=0;
	for(auto it:g[u]){
		res=max(dfs(it,u,dep+1,x),res);
	}
	res+=1;
	if(res>=x&&fa!=1)cnt+=1,res=0;
	//cerr<<u<<"::"<<res<<"__"<<x<<"??"<<cnt<<"\n";
	return res;
}

bool check(ll x){
	cnt=0;
	dfs(1,1,0,x);
	//cerr<<"++"<<cnt<<"__\n";
	return cnt<=k;
}

void solve(){
	cin>>n>>k;
	for(int i=1;i<=n;++i)g[i].clear();
	for(int i=2;i<=n;++i)cin>>fa[i],g[fa[i]].push_back(i);
	ll l=1,r=n-1;
	while(l<r){
		ll mid=(l+r)>>1;
		if(check(mid))r=mid;
		else l=mid+1;
	}
	cout<<l<<'\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>tt;
    f(sb,1,tt)solve();
    return 0;
}

发表于 更新于 分类于 本文字数： 125 阅读时长 ≈ 1 分钟

抄题解好手？mark一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
#define int long long
using namespace std;
int d[4000009];
int n,M,T,mod,p;
signed main(){
	for(scanf("%lld",&T);T;--T){
		scanf("%lld%lld",&n,&mod);
		for(M=1;M<=n;M<<=1);
		fill(d+1,d+M+n+2,1);//注意！！！一定要多fill一个，否则QAQ行可能有问题。
		for(int i=1,a=0,b=0;i<=n;++i){
			scanf("%lld%lld",&a,&b);
			a==1?d[p=i+M]=b%mod:d[p=b+M]=1;
			while(p>>=1)d[p]=d[p<<1]*d[p<<1|1]%mod;//QAQ
			printf("%lld\n",d[1]);
		}
	}
	return 0;
}

发表于 更新于 分类于 本文字数： 395 阅读时长 ≈ 1 分钟

老是写挂:)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>

using namespace std;

using ll=long long ;


const int maxn=2e5+9;
struct Node{
	ll l,r,v,tag;
}tr[maxn<<2];

ll n,f,a[maxn];

void build(int l,int r,int tot){
	if(l==r){
		tr[tot].v=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(l,mid,tot<<1),build(mid+1,r,(tot<<1)|1);
	tr[tot].v=tr[tot<<1].v+tr[(tot<<1)|1].v;
}

void update(int nl,int nr,int tot,int l,int r,ll x){
	int mid=(nl+nr)>>1;
	if(tr[tot].tag&&nl!=nr){
		tr[tot<<1].v+=tr[tot].tag*(mid-nl+1ll),tr[(tot<<1)|1].v+=tr[tot].tag*(nr-mid+0ll);
		tr[tot<<1].tag+=tr[tot].tag,tr[(tot<<1)|1].tag+=tr[tot].tag;
		tr[tot].tag=0;
	}
	if(l<=nl&&nr<=r){
		tr[tot].v+=(nr-nl+1ll)*x,tr[tot].tag+=x;
		return ;
	}
	if(mid>=l)update(nl,mid,tot<<1,l,r,x);
	if(mid<r)update(mid+1,nr,(tot<<1)|1,l,r,x);
	tr[tot].v=tr[tot<<1].v+tr[(tot<<1)|1].v;
}

ll query(int nl,int nr,int tot,int l,int r){
	ll mid=(nl+nr)>>1,res=0;
	if(tr[tot].tag&&nl!=nr){
		tr[tot<<1].v+=tr[tot].tag*(mid-nl+1ll),tr[(tot<<1)|1].v+=tr[tot].tag*(nr-mid+0ll);
		tr[tot<<1].tag+=tr[tot].tag,tr[(tot<<1)|1].tag+=tr[tot].tag;
		tr[tot].tag=0;
	}
	if(l<=nl&&nr<=r)return tr[tot].v;
	if(mid>=l)res+=query(nl,mid,tot<<1,l,r);
	if(mid<r)res+=query(mid+1,nr,(tot<<1)|1,l,r);
	return res;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>f;
	for(int i=1;i<=n;++i)cin>>a[i];
	build(1,n,1);
	for(int i=1,x,y,z,w;i<=f;++i){
		cin>>x;
		if(x==1){
			cin>>y>>z>>w;
			update(1,n,1,y,z,w);
		}else if(x==2){
			cin>>y;
			update(1,n,1,1,1,y);
		}else if(x==3){
			cin>>y;
			update(1,n,1,1,1,-y);
		}else if(x==4){
			cin>>y>>z;
			cout<<query(1,n,1,y,z)<<"\n";
		}else cout<<query(1,n,1,1,1)<<"\n";
	}
}
0%