https://codeforces.com/contest/1097
D. Makoto and a Blackboard
设$f(n)$为$n$的答案，那么由期望的定义可知$f$是个积性函数，那么问题转化成了求$f(p^x)$，其中$p$是质数。
那么直接暴力$dp$就好了，复杂度$O(\sqrt{n}+k\log^2 n)$。
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
#define lf double
#define ll long long
#define pii pair<int,int >
#define vec vector<int >
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
int n,k,f[60][10030],inv[maxn];
int qpow(int a,int x) {
int res=1;
for(;x;x>>=1,a=1ll*a*a%mod) if(x&1) res=1ll*res*a%mod;
return res;
}
int solve(int x,int c) {
for(int i=0;i<=c+1;i++) inv[i]=qpow(i,mod-2);
memset(f,0,sizeof f);f[c][0]=1;
for(int i=1;i<=k;i++)
for(int j=0;j<=c;j++)
for(int t=j;t<=c;t++)
f[j][i]=(f[j][i]+1ll*inv[t+1]*f[t][i-1]%mod)%mod;
int res=0;
for(int i=0;i<=c;i++) res=(res+1ll*qpow(x,i)*f[i][k]%mod)%mod;
return res;
}
signed main() {
read(n),read(k);int ans=1;
for(int i=2;i*i<=n;i++) {
if(n%i) continue;
int c=0;while(n%i==0) n/=i,c++;
ans=1ll*ans*solve(i,c)%mod;
}
if(n!=1) ans=1ll*ans*solve(n,1)%mod;write(ans);
return 0;
}
|
E. Egor and an RPG game
神仙题啊啊啊。。
首先可以构造出最坏的情况就是类似于：$1,3,2,6,5,4,10,9,8,7$，显然这组的答案是$4$，也就是说对于一个$k$，最大长度为$k(k+1)/2$的排列最坏为$k$。
那么我们就可以算出$f(n)$了。
然后我们考虑如何构造方案，我们先求出$lis$，也就是最长上升子序列，假设$|lis|\geqslant k$，那么我们直接把$lis$拉出来然后变成一个子问题，因为$\frac{k(k+1)}{2}-k=\frac{k(k-1)}2$，所以剩下的子问题也合法。
否则我们可以直接选出$|lis|$个下降子序列，这里考虑$lis$的二分求法，设$f_i$表示长度为$i$的上升子序列结尾最小的数是多少。
那么每次添加一个新的数$x$我们就在$f$上二分然后更新，那么每个$f$的历史值一定递减并且位置递增。
总复杂度$O(n\sqrt n \log n)$，因为最坏要做$\sqrt n$次$lis$。
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>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
#define lf double
#define ll long long
#define pii pair<int,int >
#define vec vector<int >
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
int a[maxn],n,t[maxn],len,sta[maxn],top,pre[maxn],rev[maxn];
vector<int > s[maxn];
void solve() {
read(n);for(int i=1;i<=n;i++) read(a[i]),rev[a[i]]=i;
vector<vector<int > > ans;
while(n) {
for(int i=0;i<=n;i++) t[i]=0,s[i].clear(),pre[i]=0;len=0;
vector<int > r;
for(int i=1;i<=n;i++) {
if(a[i]>t[len]) {
t[++len]=a[i],s[len].pb(a[i]);
pre[i]=rev[t[len-1]];
continue;
}
int x=lower_bound(t+1,t+len+1,a[i])-t;
s[x].pb(a[i]),t[x]=a[i];pre[i]=rev[t[x-1]];
}
int k=0;while((k+1)*(k+2)/2<=n) k++;
if(len<=k) {
for(int i=1;i<=len;i++) ans.pb(s[i]);
break;
}for(int i=rev[t[len]];i;i=pre[i]) r.pb(a[i]);
reverse(r.begin(),r.end());ans.pb(r);
int p=0;top=0;
for(int i=1;i<=n;i++) if(p>=r.size()||a[i]!=r[p]) sta[++top]=a[i];else p++;
for(int i=1;i<=top;i++) a[i]=sta[i],rev[a[i]]=i;
n-=len;
}write(ans.size());
for(int i=0;i<ans.size();i++) {
printf("%d ",ans[i].size());
for(int j=0;j<ans[i].size();j++) printf("%d ",ans[i][j]);puts("");
}
}
int main() {
int t;read(t);while(t--) solve();
return 0;
}
|
F. Alex and a TV Show
如果没有$3$操作那么显然可以用$\rm bitset$。
否则我们考虑一种这样的变换，原来假设$f_{i,j}$表示$i$集合中$j$的数量，现在我们改成$f_{i,j}$表示$i$集合中$j$的倍数的数量，那么$3$操作直接逐位相乘就行了。
$1$操作显然可以$O(v^2)$预处理，$3$操作直接利用莫比乌斯反演，也可以$O(v^2)$预处理系数然后直接转化为$\rm bitset$运算，$2$操作和原来没有区别。
那么总复杂度就是$O(\frac{qv}{\omega}+v^2)$。
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
| #include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
#define lf double
#define ll long long
#define pii pair<int,int >
#define vec vector<int >
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
const int maxn = 1e5+10;
const int M = 7001;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
int n,q,pri[maxn],mu[maxn],vis[maxn],tot;
bitset<M > t[maxn],r[M],s[M];
void sieve() {
mu[1]=1;
for(int i=2;i<M;i++) {
if(!vis[i]) mu[i]=1,pri[++tot]=i;
for(int j=1;j<=tot&&i*pri[j]<M;j++) {
vis[i*pri[j]]=1;
if(i%pri[j]==0) break;
mu[i*pri[j]]=mu[i];
}
}
}
int main() {
read(n),read(q);sieve();
for(int i=1;i<M;i++)
for(int j=1;j<=i;j++) if(i%j==0) r[i][j]=1;
for(int i=1;i<M;i++)
for(int j=i;j<M;j+=i) s[i][j]=mu[j/i];
while(q--) {
int op,x,y,z,v;read(op),read(x);
if(op==1) read(v),t[x]=r[v];
else if(op==2) read(y),read(z),t[x]=t[y]^t[z];
else if(op==3) read(y),read(z),t[x]=t[y]&t[z];
else read(v),putchar(((t[x]&s[v]).count()&1)+'0');
}
return 0;
}
|
G. Vladislav and a Great Legend
什么鬼题。。。看到$k$只有$200$先用斯特林数搞一波，式子变成：
第一个式子是第二类斯特林数的套路，后面是下降幂，不会的可以看看这个：斯特林反演。
然后我们现在就是要求后面那一块，设$f_{i,j}$表示$i$的子树里选中了$j$条边，对于每一个边的选法选点的方案数之和。
那么这个可以类似树上背包的转移，就是当前新加一个子树讨论下这个子树怎么选。
如果每次循环边界都写成$\min(k,sz_v)$这样，复杂度就是$O(nk)$。
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
| #include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
#define lf double
#define ll long long
#define pii pair<int,int >
#define vec vector<int >
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
const int maxn = 1e5+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
int s[202][202],f[maxn][202],fac[maxn],n,k,head[maxn],tot,sz[maxn],res[maxn],t[maxn];
struct edge{int to,nxt;}e[maxn<<1];
void ins(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot;}
void prepare() {
fac[0]=1;for(int i=1;i<maxn;i++) fac[i]=1ll*fac[i-1]*i%mod;
s[0][0]=1;
for(int i=1;i<=200;i++)
for(int j=1;j<=i;j++) s[i][j]=(1ll*j*s[i-1][j]%mod+s[i-1][j-1]%mod)%mod;
}
void dfs(int x,int fa) {
sz[x]=1;f[x][0]=1;
for(int pps=head[x],v;pps;pps=e[pps].nxt) {
if((v=e[pps].to)==fa) continue;dfs(v,x);
for(int i=0;i<=min(k,sz[x]);i++) t[i]=f[x][i];
for(int i=1;i<=min(k,sz[v]);i++) f[x][i]=(0ll+f[x][i]+f[v][i]+f[v][i-1])%mod;
f[x][0]=(f[x][0]+f[v][0])%mod;
for(int i=0;i<=min(k,sz[x]);i++)
for(int j=0;j<=min(k-i,sz[v]);j++) {
f[x][i+j]=(f[x][i+j]+1ll*t[i]*f[v][j]%mod)%mod;
f[x][i+j+1]=(f[x][i+j+1]+1ll*t[i]*f[v][j]%mod)%mod;
res[i+j]=(res[i+j]+1ll*t[i]*f[v][j]%mod)%mod;
res[i+j+1]=(res[i+j+1]+1ll*t[i]*f[v][j]%mod)%mod;
}
sz[x]+=sz[v];
}
}
int main() {
prepare();read(n),read(k);
for(int i=1,x,y;i<n;i++) read(x),read(y),ins(x,y),ins(y,x);
dfs(1,0);int ans=0;
for(int i=1;i<=k;i++) ans=(ans+1ll*s[k][i]*fac[i]%mod*res[i]%mod)%mod;
write(ans);
return 0;
}
|