2019省选前做的题

2019省选前做的题

ARC098D Donation

一个点如果被经过多次,在最后那次再解救总是等效且更优的

考虑构造一个序列 $C_i=max(A_i-B_i,0)$ 表示在这个点上的任意时刻都至少有的金币数

那么我们考虑当前C最大的点x,去掉后会形成多个联通块,那么策略一定是走完其他联通块->x->某个联通块
于是我们可以把图转化成一棵树,重复上述操作,即儿子为各个联通块中最大点,这个可以nlogn解决

设 $f_x表示子树B的和,g_x表示搞定子树,进入前最少的金币数$

$g_x=min \ max(g_y,C_x)+f_x-f_y$

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
ll b[MAX_N];int c[MAX_N];
vc<int> son[MAX_N];
ll g[MAX_N];
void dp(int x)
{
if(son[x].size())
{
for(int t=0;t<(int)son[x].size();t++) dp(son[x][t]),b[x]+=b[son[x][t]];
g[x]=LLINF;
for(int t=0;t<(int)son[x].size();t++)
{
int y=son[x][t];
chmin(g[x], max(g[y],(ll)c[x])+(b[x]-b[y]) );
}
}
else g[x]=b[x]+c[x];
}
int pos[MAX_N];bool cmp(int x,int y){return c[x]<c[y];}
vc<int> to[MAX_N];
int fa[MAX_N];int findfa(int x){return x==fa[x]?x:fa[x]=findfa(fa[x]);}
void main()
{
int n=qread(),m=qread();for(int i=1;i<=n;i++) c[i]=qread(),b[i]=qread(),c[i]=max(int(c[i]-b[i]),0);
for(int i=1;i<=n;i++) pos[i]=i;sort(pos+1,pos+n+1,cmp);
for(int i=1;i<=m;i++){int x=qread(),y=qread();to[x].PB(y);to[y].PB(x);}
for(int i=1;i<=n;i++)
{
int x=pos[i];fa[x]=x;
for(int t=0;t<(int)to[x].size();t++)
{
int y=to[x][t],tt=findfa(y);
if(fa[y]!=0 and tt!=x) fa[tt]=x,son[x].PB(tt);
}
}
dp(pos[n]);write(g[pos[n]]);
}

CF371E Sonya Partymaker

我目前认为,把最长段转到n-1间是错误的做法,但不知为何得到AC且没能拍出错误,故只给出代码:

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
int m,n,st;pr mx;
int f[MAX_N][2],a[MAX_N];
void dp(int T,int op)
{
for(int i=st+1+op;i<=st+n-1;i++)
{
if(f[i-1][0]>=a[i]-T) chmax(f[i][0],a[i]+1);
if(f[i-1][1]>=a[i]-T) chmax(f[i][0],max(a[i-1]+T+1,a[i]+1) );
int tmp=max(f[i-1][0],f[i-1][1]);if(tmp>=a[i]) chmax(f[i][1],a[i]+T+1);
chmax(f[i][0],tmp);chmax(f[i][1],tmp);
}
}
bool check(int T)
{
int st=mx.SE;//printf("st=%d\n",st);
//left
{
memset(f,-0x3f,sizeof f);f[st][0]=a[st]+1;dp(T,0);
if( max(f[st+n-1][0],f[st+n-1][1])>=a[st]+m-T ) return 1;
}
//right
{
memset(f,-0x3f,sizeof f);f[st][1]=a[st]+T+1;dp(T,0);
if( max(f[st+n-1][0],f[st+n-1][1])>=a[st]+m ) return 1;
}
//right2
if(a[st]+T+1>=a[st+1])
{
memset(f,-0x3f,sizeof f);f[st+1][0]=max(a[st]+T+1,a[st+1]+1);dp(T,1);
if( max(f[st+n-1][0],f[st+n-1][1])>=a[st+1]+m-T ) return 1;
}
return 0;
}
void main()
{
m=qread(),n=qread();for(int i=1;i<=n;i++) a[i]=qread();
mx=MP(a[1]-1+m-a[n]+1,1);for(int i=2;i<=n;i++) mx=max(mx,MP(a[i]-a[i-1],i));st=mx.SE;
for(int i=1;i<=n;i++) a[n+i]=a[i]+m;
int l=0,r=mx.FR-1,ans=mx.FR;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
write(ans);
}

比较合理的做法应该是移动到1和2之间,从1开始dp,这样能避免很多奇怪的情况。

第一次dp,不考虑所有人在n-1段的贡献,得出还差长度ln,然后第二次dp,dp的初始值要求覆盖ln,然后判能否合上

不是很想再写一次了,所以口胡跑路了……


51nod1838 Jabby的网格

限制:$步长 \leq M,不能同时为(x_K,y_K)(G的倍数),恰好走R步到达(T_x,T_y)​$
$$
\begin{aligned}
& pp(a,b)=将b划分为a个非负数=C_{a+b-1}^{a-1} \\
& f_x(a,b)=考虑x坐标,a步走了b且满足步长限制=\sum_{k=0}^{min(b/(M_x+1),a)} (-1)^k C_a^k pp(a,b-(M_x+1)k) \\
& g(k,t)=走了k次非法到达(tG,tG),这个可以 O(KRT_x/G) \\
& ans=\sum_{k=0}^R (-1)^k C_r^k \sum_{t=0}^{T_x/G} g(k,t)f_x(R-k,T_x-tG)f_y(R-k,T_y-tG)
\end{aligned}
$$
总复杂度为 $O(R^2T_x/G)​$

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
int pp(int a,int b){return C(a+b-1,a-1);}
int g[MAX_N][210];
int T[2],M[2],R,G;vc<int> ban;
int getf(int op,int a,int b)
{
int ans=0;
for(int k=0,t=1;k<=min(b/(M[op]+1),a);k++,t=-t)
add(ans,(MOD+(ll)t*C(a,k)*pp(a,b-(M[op]+1)*k)%MOD)%MOD );
return ans;
}
void main()
{
fac[0]=1;for(int i=1;i<MAX_M;i++) fac[i]=(ll)fac[i-1]*i%MOD;
inv[1]=1;for(int i=2;i<MAX_M;i++) inv[i]=ll(MOD-MOD/i)*inv[MOD%i]%MOD;
facinv[0]=1;for(int i=1;i<MAX_M;i++) facinv[i]=(ll)facinv[i-1]*inv[i]%MOD;
scanf("%d%d%d%d%d%d",&T[0],&T[1],&M[0],&M[1],&R,&G);
int K=qread();while(K--) ban.PB(qread());ban.PB(0);
sort(ban.begin(),ban.end());ban.resize(unique(ban.begin(),ban.end())-ban.begin());
g[0][0]=1;
for(int pp=0;pp<R;pp++) for(int t=0;t<=100;t++)
for(int s=0;s<(int)ban.size();s++) add(g[pp+1][t+ ban[s]/G ],g[pp][t]);
int ans=0;
for(int k=0;k<=R;k++)
{
int now=0;
for(int t=0;t<=min(T[0],T[1])/G;t++) add(now, (ll)g[k][t]*getf(0,R-k,T[0]-t*G)%MOD*getf(1,R-k,T[1]-t*G)%MOD );
add(ans,ll(MOD+(k&1?-1:1)*C(R,k))*now%MOD);
}
write(ans);
}

51nod1965 奇怪的式子

zjy神仙的题,但模数特别狗……(min25筛类算法不说复杂度系列)
$$
\begin{aligned}
& 设 S(n)=n(n+1)/2;不妨把答案拆成两个部分 \\
& Part A\\
& \prod \sigma_0(i)^i=\prod_i \prod_t^{P_i^t \leq N} (t+1)^{ S(N/P_i^t)P_i^t-S(N/P_i^{t+1})P_i^{t+1} } \\
& 这个对于P_i^2<N,直接计算;否则t=1(为实现方便第一部分不统计t=1) \\
& 2^{ \sum_i S(N/P_i)P_i } ,这个东西可以直接数论分块,借助min25筛出来的素数前缀和即可 \\
& Part B\\
& 设g(n,j)=\sum_{minp(i) \geq P_j或i \in P} \mu(i)质因数个数(i),ans=2^{ g(N,1) } ,设T(n,j)=\sum \mu(i) 辅助转移 \\
& T(n,j)=T(n,j-1)+(-1)( T(n/P_j,j+1)-(-j) )[P_j^2 \leq n] \\
& g(n,j)=g(n,j-1)+(-1)( g(n/P_j,j+1)+T(n/P_j,j+1)-2(-j) )[P_j^2 \leq n] \\
\end{aligned}
$$
卡常卡不动,跑路了……

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void write1(ll num){write(num);putchar(' ');}
void write2(ll num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<int,int>
#define PB push_back
#define vc vector
void chmax(int &x,const int y) {x=x>y?x:y;}
void chmin(ll &x,const int y) {x=x<y?x:y;}
const int MAX_N=2e6+10;
/*ll qmul(ll x,ll y,ll MOD)
{
x=(x%MOD+MOD)%MOD,y=(y%MOD+MOD)%MOD;
ll tmp=(ll)((double)x*y/MOD+1e-8)*MOD;
return (x*y-tmp+MOD)%MOD;//允许溢出
}*/
ll qmul(ll x,ll y,ll P) {return (x*y-(ll)((double)x/P*y+0.3)*P+P)%P;}//更快的版本
const ll MOD=1e12+39,MOD2=MOD-1;
void add(ll &x,ll y){x+=y;if(x>=MOD2)x-=MOD2;if(x<0)x+=MOD2;}
ll qpower(ll x,ll e)
{
ll ans=1;x%=MOD;e=e%MOD2+MOD2;
while(e)
{
if(e&1) ans=qmul(ans,x,MOD);
x=qmul(x,x,MOD)%MOD;e>>=1;
}
return ans;
}
ll S(ll n){return (n&1)?qmul(n,(n+1)/2,MOD2):qmul(n/2,n+1,MOD2);}
bool mark[MAX_N];int pp=0,p[MAX_N];ll sum[MAX_N];
void pre()
{
for(int i=2;i<MAX_N;i++)
{
if(!mark[i]) p[++pp]=i,sum[pp]=sum[pp-1]+i;
for(int j=1;j<=pp and i*p[j]<MAX_N;j++)
{
mark[i*p[j]]=1;
if(i%p[j]==0) break;
}
}
}
ll N,md,a[MAX_N];
#define id(x) ((x)<=md?a[(x)]:a[md+N/(x)])
vector<ll> num;
ll p1[MAX_N],p2[MAX_N],g[MAX_N],T[MAX_N];
ll xx[100];
void main()
{
pre();
int cs=qread();
while(cs--)
{
memset(a,0,sizeof a);num.resize(0);memset(xx,0,sizeof xx);
N=qread();md=sqrt(N)+1;
for(ll l=1,r;l<=N;l=r+1) r=N/(N/l),id(N/l)=num.size(),num.PB(N/l);
int m=num.size();
for(int t=0;t<m;t++)
{
p1[t]=(num[t]-1)%MOD2;
p2[t]=(num[t]&1)?qmul(num[t]+2,(num[t]-1)/2,MOD2):qmul((num[t]+2)/2,num[t]-1,MOD2);
}
for(int j=1;j<=pp;j++) for(int t=0;t<m and (ll)p[j]*p[j]<=num[t];t++)
{
add(p1[t],-(p1[id(num[t]/p[j])]-(j-1))%MOD2 );
add(p2[t],-qmul(p2[id(num[t]/p[j])]-sum[j-1],p[j],MOD2) );
}
for(int t=0;t<m;t++) T[t]=g[t]=-p1[t];
for(int j=pp;j>=1;j--) for(int t=0;t<m and (ll)p[j]*p[j]<=num[t];t++)
{
int go=id(num[t]/p[j]);if(go==t) puts("error2");
add(T[t],-(T[go]+j)%MOD2);add(g[t],-(g[go]+T[go]+j*2)%MOD2);
}
ll ans=1;xx[2]=g[0];
for(int j=1;j<=pp and (ll)p[j]*p[j]<=N;j++) for(ll t=1,now=p[j];now<=N;t++,now=now*p[j])
add(xx[t+1], (qmul(S(N/now),now,MOD2)-qmul(S(N/now/p[j]),(ll)p[j]*now,MOD2))%MOD2 );
ll sq=0;while((sq+1)*(sq+1)<=N) sq++;
for(ll l=1,r;l<=N;l=r+1)
{
r=N/(N/l);
if(r>sq) add(xx[2], qmul(S(N/l),p2[id(r)]-p2[id( max(sq,l-1) )],MOD2) );
}
for(int t=2;t<=50;t++) ans=qmul(ans,qpower(t,xx[t]),MOD);
write2((ans+MOD)%MOD);
}
}
};
signed main()
{
srand(time(0));
mine::main();
}

THUSC2015 解密运算

先考虑所有字符都不同的情况,我们能立刻知道最后一个字符,然后根据字符找到排名,就能找到上一个字符是什么

那现在字符可能相同,考虑其特性,我们现在是希望得到以这个字符开始的排名

那对于以这个字符开头的那些串,字典序其实只跟下个字符开头相关,也就是按照作为结尾的那个排名

所以按【字符为第一关键字,排名为第二关键字】给字符重排即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
pr tmp[MAX_N];int a[MAX_N];
int ans[MAX_N];
void main()
{
int n=qread();qread();
for(int i=1;i<=n+1;i++)
{
a[i]=qread();
tmp[i]=MP(a[i],i);
}
sort(tmp+1,tmp+n+1+1);
for(int i=1;i<=n+1;i++) a[tmp[i].SE]=i;
for(int t=n,now=1;t>=0;t--)
{
ans[t]=tmp[a[now]].FR;
now=a[now];
}
for(int i=1;i<=n;i++) write1(ans[i]);
}

PA2014 Fiolki

每次合并新建节点,那么就是二叉树森林

把反应放到lca上处理,可以无脑线段树合并,也可以直接做

时间复杂度 $O(nlogn)​$

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
vector<int> son[MAX_N];bool v[MAX_N];
int ff[MAX_N][20],dep[MAX_N];
void pre(int x,int fa)
{
v[x]=1;
ff[x][0]=fa;for(int i=1;i<20;i++) ff[x][i]=ff[ff[x][i-1]][i-1];
for(int t=0;t<(int)son[x].size();t++)
{
int y=son[x][t];
dep[y]=dep[x]+1;pre(y,x);
}
}
int getlca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=19;i>=0;i--) if((1<<i)<=dep[x]-dep[y]) x=ff[x][i];
if(x==y) return x;
for(int i=19;i>=0;i--) if(ff[x][i]!=ff[y][i]) x=ff[x][i],y=ff[y][i];
return ff[x][0];
}
vector<pr> pp[MAX_N];
ll a[MAX_N],ans=0;
void solve(int x)
{
v[x]=1;
for(int t=0;t<(int)son[x].size();t++) solve(son[x][t]);
for(int t=0;t<(int)pp[x].size();t++)
{
int tx=pp[x][t].FR,ty=pp[x][t].SE;
ll tmp=min(a[tx],a[ty]);a[tx]-=tmp;a[ty]-=tmp;ans+=tmp*2;
}
}
int fa[MAX_N];int findfa(int x){return x==fa[x]?x:fa[x]=findfa(fa[x]);}
void main()
{
int n=qread(),m=qread(),tt=qread();
for(int i=1;i<=n;i++) a[i]=qread(),fa[i]=i;
int cnt=n;
while(m--)
{
int x=findfa(qread()),y=findfa(qread());
cnt++;son[cnt].PB(x);son[cnt].PB(y);
fa[x]=fa[y]=fa[cnt]=cnt;
}
for(int i=cnt;i>=1;i--) if(!v[i]) pre(i,0);
pre(cnt,0);
while(tt--)
{
int x=qread(),y=qread();
pp[getlca(x,y)].PB(MP(x,y));
}
memset(v,0,sizeof v);
for(int i=cnt;i>=1;i--) if(!v[i]) solve(i);
write(ans);
}

CF1041F Ray in the tube

题意转化为:$k为偶,A在y=kx+b上有整数解,B在y=kx+k/2+b上有整数解$

枚举k,那么搞个map即可;考虑 $k=2^i \times 奇数c​$,发现对于每个i取c=1能覆盖最多的点,故只有log个k

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int n,m,a[MAX_N],b[MAX_N];map<int,int> mp;
int check(int k)
{
mp.clear();int mx=0;
for(int i=1;i<=n;i++)
{
int now=a[i];if(k>0) now%=k;
mp[now]++;chmax(mx,mp[now]);
}
for(int i=1;i<=m;i++)
{
int now=b[i]+k/2;if(k>0) now%=k;
mp[now]++;chmax(mx,mp[now]);
}
return mx;
}
void main()
{
n=qread();qread();for(int i=1;i<=n;i++) a[i]=qread();
m=qread();qread();for(int i=1;i<=m;i++) b[i]=qread();
int ans=0;chmax(ans,check(0));
for(ll k=2;k<=INF*2;k*=2) chmax(ans,check(k));
write(ans);
}

CF869D The Overdosing Ubiquity

真正影响方案计算的只有那2m个点向上的所有点(mlogn个),然后其他点是用来计算当前搜出来的路径的系数的

把那些点和边建成一个新图,在上面枚举起点计算简单路径,每个节点会被计算 $2^mm!$ 次,总复杂度为 $2^mm! (mlogn)^2$


CF1151E Number of Components

我的做法是考虑每条边的贡献,就是说对于每个联通块,左右两条线段都把他计算一次,除2即可

然后这样的话边界是只有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
ll a[MAX_N];
void main()
{
fac[0]=1;for(int i=1;i<MAX_N;i++) fac[i]=fac[i-1]*i%MOD;
inv[1]=1;for(int i=2;i<MAX_N;i++) inv[i]=ll(MOD-MOD/i)*inv[MOD%i]%MOD;
facinv[0]=1;for(int i=1;i<MAX_N;i++) facinv[i]=facinv[i-1]*inv[i]%MOD;
int n=qread();for(int i=1;i<=n;i++) a[i]=qread();
if(n==1) {puts("1");return;}
double ans=0,ans2=0;
if(a[1]<=a[2]) ans+=a[1]*(a[2]-a[1]),ans2+=a[1]*(n-a[2]+1);
else ans+=(n-a[1]+1)*(a[1]-a[2]),ans2+=a[2]*(n-a[1]+1);
if(a[n-1]<=a[n]) ans+=(a[n]-a[n-1])*(n-a[n]+1),ans2+=a[n-1]*(n-a[n]+1);
else ans+=a[n]*(a[n-1]-a[n]),ans2+=a[n]*(n-a[n-1]+1);
for(int i=2;i<=n-1;i++)
{
//left
{
ll x=a[i],y=a[i+1],z=a[i-1];if(x>y) swap(x,y);
if(z<x) ans2+=(x-z)*(n-y+1);
else if(z>y) ans2+=x*(z-y);
}
//right
{
ll x=a[i],y=a[i+1],z=a[i-1];if(x>z) swap(x,z);
if(y<x) ans2+=(x-y)*(n-z+1);
else if(y>z) ans2+=x*(y-z);
}
ll x=a[i],y=a[i+1],z=a[i-1];if(y>z) swap(y,z);
if(x<=y) ans+=x*(y-x);
else if(y<=x and x<=z) ans+=(x-y)*(z-x);
else ans+=(x-z)*(n-x+1);
}
write(round(ans+ans2/2));
}

然后问akc他是怎么做的,说完我就懂了,然后在5min内就写完一遍过了woc

就是逐个加入元素,那么有贡献当且仅当区间包含当前元素而且不包含上一个元素

1
2
3
4
5
6
7
8
9
10
ll a[MAX_N];
void main()
{
int n=qread();for(int i=1;i<=n;i++) a[i]=qread();
ll ans=a[1]*(n-a[1]+1);
for(int i=2;i<=n;i++)
if(a[i-1]<a[i]) ans+=(a[i]-a[i-1])*(n-a[i]+1);
else ans+=(a[i-1]-a[i])*a[i];
write(ans);
}

更显然的做法其实直接点数-边数就行了,没想到这个有点惭愧啊


CF1139D Steps to One

这东西我复杂度算错了,好jb菜啊

显然是建出nlogn条边的dag,在dag上计算期望,然后主要是边权怎么求
$$
g(x,y)=\sum [gcd(x/y,i/y)=1]=\sum_{d|\frac{x}{y}} \mu(d)\lfloor \frac{m}{dy} \rfloor
$$
然后其实直接枚举约数计算就好了,根本不需要优化,我就说为什么放在E那个煞笔题前面

时间复杂度为 $O(nlogn 约数个数)$ 复杂度不满

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
vc<int> dd[MAX_N];
map<int,int> g[MAX_N];
int f[MAX_N];
void main()
{
pre();
int m=qread();
for(int d=1;d<=m;d++) for(int num=d;num<=m;num+=d) dd[num].PB(d);
for(int y=1;y<=m;y++) for(int x=y;x<=m;x+=y)
{
int now=0;
for(int t=0;t<(int)dd[x/y].size();t++)
{
int d=dd[x/y][t];
add(now,mu[d]*(m/d/y));
}
g[x][y]=(ll)now*inv(m)%MOD;
}
f[1]=0;int ans=1;
for(int x=2;x<=m;x++)
{
f[x]=1;
for(int t=0;t<(int)dd[x].size();t++)
{
int y=dd[x][t];if(y==x) continue;
add(f[x],(ll)f[y]*g[x][y]%MOD);
}
f[x]=f[x]*inv(1-g[x][x])%MOD;
add(ans,(ll)f[x]*inv(m)%MOD);
}
write((ans+MOD)%MOD);
}

bzoj4274 Periodic Sum

在做这题之前我根本不知道,原来两边都在变化的那种乘积是有可能矩乘求的

本题的推导没有难点,注意一下细节即可,时间复杂度为 $O(n5^3)​$

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
int n,m,pp1,pp2;
char a[MAX_N];
int dec[MAX_N],dec2[MAX_N];
void main()
{
scanf("%s%d%d",a,&m,&MOD);n=strlen(a);reverse(a,a+n);
dec[0]=1;for(int i=1;i<MAX_N;i++) dec[i]=(ll)dec[i-1]*10%MOD;
dec2[0]=1;for(int i=1;i<MAX_N;i++) dec2[i]=(dec2[i-1]+dec[i])%MOD;
pp1=dec[n];pp2=dec2[n-1];
Matrix A;A.mm[0][0]=1;
A.mm[0][1]=pp1;A.mm[0][2]=-(ll)n*pp1%MOD;A.mm[0][3]=pp2;
A.mm[1][1]=pp1;A.mm[1][2]=-(ll)n*pp1%MOD;A.mm[1][3]=pp2;
A.mm[2][2]=pp1;A.mm[2][4]=pp2;
A.mm[3][3]=1; A.mm[3][4]=-n;
A.mm[4][4]=1;A=mpower(A,m-1);
int ans=0;
for(int i=0;i<n;i++)
{
Matrix now;now.mm[4][0]=1;
now.mm[2][0]=dec2[i];now.mm[3][0]=((ll)n*(m-1)-i)%MOD;
now.mm[0][0]=now.mm[1][0]=((ll)n*m-i)%MOD*dec2[i]%MOD;
add(ans,ll((A*now).mm[0][0])*(a[i]-'0')%MOD);
}
write((ans+MOD)%MOD);
}

51nod1989 竞赛表格

$$
f(i)=1+\sum_{j+rev(j)=i} f(j) \\
设 j+rev(j)的并集为S\\
f(i)=1+\sum_{j+rev(j)=i,j \in S} f(j)+\sum_{j+rev(j)=i,j \notin S} 1\\
f(i)=1+\sum_{j+rev(j)=i,j \in S} (f(j)-1)+\sum_{j+rev(j)=i} 1
$$

然后答案其实不会超过ll,剩下自己想即可,时间复杂度的分析的话写完就会了

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void write1(ll num){write(num);putchar(' ');}
void write2(ll num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<ll,int>
#define PB push_back
#define vc vector
void chmax(int &x,const int y) {x=x>y?x:y;}
void chmin(int &x,const int y) {x=x<y?x:y;}
int MOD=1e9+7;
void add(int &x,int y){x+=y;if(x>=MOD) x-=MOD;if(x<=-MOD) x+=MOD;}
const int MAX_N=1e5+10;
vc<pr> gg;
ll dec[20];
ll rev(ll num)
{
int n=log10(num)+1;
ll ans=0;for(int i=0;i<n;i++) ans+=dec[n-1-i]*(num/dec[i]%10);
return ans;
}
int calc(int n,int pos)
{
if(pos==0) return min(n,9)-max(1,n-9)+1;
return min(n,9)-max(0,n-9)+1;
}
int a[20];
void dfs(int pos,int cnt)
{
if(pos!=0)
{
ll num2=0;for(int i=0;i<pos;i++) num2+=(ll)a[i]*(dec[i]+dec[2*pos-i-1]);
if(num2 and num2<=10000000000ll) gg.PB(MP(num2,cnt));
}
if(pos==5) return;
for(int i=0;i<=18;i++)
{
a[pos]=i;
if(i%2==0)
{
ll num2=dec[pos]*i;for(int j=0;j<pos;j++) num2+=(ll)a[j]*(dec[j]+dec[2*pos-j]);
if(num2) gg.PB(MP(num2,cnt));
}
dfs(pos+1,cnt*calc(i,pos));
a[pos]=0;
}
}
vc<pr> g2;ll ff[4000000];
void main()
{
dec[0]=1;for(int i=1;i<=18;i++) dec[i]=dec[i-1]*10;
dfs(0,1);sort(gg.begin(),gg.end());
for(int t=0;t<(int)gg.size();t++)
{
if(t==0 or gg[t-1].FR!=gg[t].FR) g2.PB(gg[t]);
else g2[g2.size()-1].SE+=gg[t].SE;
}
for(int t=0;t<(int)g2.size();t++)
{
ff[t]+=1+g2[t].SE;ll num=g2[t].FR+rev(g2[t].FR);
ff[lower_bound(g2.begin(),g2.end(),MP(num,0))-g2.begin()]+=ff[t]-1;
}
for(int t=1;t<(int)g2.size();t++) ff[t]+=ff[t-1];
int q=qread();ll ans=0;
while(q--)
{
ll l=qread(),r=qread();MOD=qread();
int fl=lower_bound(g2.begin(),g2.end(),MP(l,0))-g2.begin();
int fr=upper_bound(g2.begin(),g2.end(),MP(r,INF))-g2.begin()-1;
ans^=(ff[fr]-(fl==0?0:ff[fl-1])+(r-l+1)-(fr-fl+1))%MOD;
}
write(ans);
}
};
signed main()
{
srand(time(0));
mine::main();
}

CF889E Mod Mod Mod

神仙题……即使有tyb带我依然搞了很久;不知道为什么全世界都是秒懂,直到现在都感觉有些别扭

先扔几个结论,都很好证明:【被更小的数模,只有log次】、【最优方案一定有某个余数为ai-1,否则整体+1即可】
$$
\begin{aligned}
& 首先这个a可以处理为一个递减的,然后为了方便我们设 x_i=X\%a_1\%a_2…\%a_i,ans_i=\sum_{t=1}^i x_t \\
& 然后非常关键的一步是, 将ans_i表示为 ix_i+S_i,即把前面的x多出来的部分放在S_i里面 \\
& 然后定义一个 g(i,mx),表示使得 \forall x_i \in[1,mx],S_i \geq g(i,mx)的最大g \\
& g(1,a_1-1)=0,ANS={max} jn+g(n,j)(注意这里不一定对应,但g是个不递增的函数,所以不会算错) \\
& 考虑怎么转移,设 A=a
{i+1},然后只需改变mx \geq A的部分 \\
& g(i,mx)+i(mx-mx\%A) \to g(i+1,mx\%A) (推导可考虑把x_{i+1}补上去然后化一下形式)\\
& g(i,mx)+i(\lfloor \frac{mx+1}{A} \rfloor A-A) \to g(i+1,A-1) (找到最大的的?A-1,然后同上推导)\\
& 搞个map啥的维护一下,时间复杂度为 O(nlognlogA)
\end{aligned}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
ll a[MAX_N];
map<ll,ll> g;
typedef map<ll,ll>::iterator IT;
void main()
{
int n=qread();for(int i=1;i<=n;i++) a[i]=qread();//实际实现不需要处理
g[a[1]-1]=0;
for(int i=1;i<n;i++)
{
ll lstg=-1,A=a[i+1];
for(IT it=g.lower_bound(A);it!=g.end();it++)
{
ll mx=it->FR,gg=it->SE;
g[mx%A]=max(g[mx%A], (mx-mx%A)*i+gg );
g[A-1]=max(g[A-1], ((mx+1-A)/A)*A*i+gg );
if(g.count(lstg)) g.erase(g.find(lstg));lstg=it->FR;
}
if(g.count(lstg)) g.erase(g.find(lstg));
}
ll ans=0;
for(IT it=g.begin();it!=g.end();it++) ans=max(ans, it->FR*n+it->SE );
write(ans);
}

CF1155F Delivery Oligopoly 【Snoi2013】Quare

这个模型似乎挺经典的

考虑如何将一个边双分解,首先一个点是边双,然后加入一条两端都连向当前联通块的链后依然是边双

$设f(S)=当前边双集合为S的最小代价,g(S,x,y)表示一条两端为x、y的链的最小代价​$

算法复杂度为 $O(2^nn^3+3^nn^2)​$ 常数极小,可通过本题

重边、输出方案啥的处理方法都很简单,就不细说了

hdu6115 Factory

考虑根号分治,对于两个都<T的询问用虚树合并+dp计算,否则枚举每个大块计算答案,这个部分换根即可线性,复杂度为 $O(n \sqrt n)$

下面这份代码在根号内还带个log

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
//#define double long double
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void write1(ll num){write(num);putchar(' ');}
void write2(ll num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<int,int>
#define PB push_back
#define vc vector
void chmax(int &x,const int y) {x=x>y?x:y;}
void chmin(int &x,const int y) {x=x<y?x:y;}
const int MAX_N=1e5+10;
vc<pr> to[MAX_N];int dis[MAX_N],dfn2[MAX_N],dep2[MAX_N];int gogo[MAX_N];//向上的边权
int mp[2*MAX_N][21],pp=0,dfn[MAX_N];int gmin(int x,int y){return dep2[x]<dep2[y]?x:y;}
void dfs(int x,int fa)
{
dep2[x]=dep2[fa]+1;
mp[++pp][0]=x;dfn[x]=pp;
for(int t=0;t<(int)to[x].size();t++)
{
int y=to[x][t].FR,c=to[x][t].SE;if(y==fa) continue;
dis[y]=dis[x]+c;dfs(y,x);gogo[y]=c;
mp[++pp][0]=x;
}
dfn2[x]=pp;
}
int lg[MAX_N*2],bin[100];
int getlca(int x,int y)
{
x=dfn[x],y=dfn[y];if(x>y) swap(x,y);
int t=lg[y-x+1];return gmin(mp[x][t],mp[y-bin[t]+1][t]);
}
int getdis(int x,int y){return dis[x]+dis[y]-2*dis[getlca(x,y)];}
bool cmp(int a,int b){return dfn[a]<dfn[b];}
bool in(int fa,int x){return dfn[fa]<=dfn[x] and dfn[x]<=dfn2[fa];}
vc<int> on[MAX_N];
vc<int> ss[MAX_N];int id[MAX_N];
int preans[350][MAX_N];
priority_queue< pr,vc<pr>,greater<pr> > q;
int dep[MAX_N];bool v[MAX_N];
int solve1(int now)
{
while(q.size()) q.pop();memset(dep,0x3f,sizeof dep);memset(v,0,sizeof v);
for(int t=0;t<(int)ss[now].size();t++) q.push(MP(0,ss[now][t])),dep[ss[now][t]]=0;
while(q.size())
{
int x=q.top().SE;q.pop();
if(v[x]) continue;v[x]=1;
for(int t=0;t<(int)on[x].size();t++) chmin(preans[id[now]][on[x][t]],dep[x]);
for(int t=0;t<(int)to[x].size();t++)
{
int y=to[x][t].FR,c=to[x][t].SE;
chmin(dep[y],dep[x]+c);q.push(MP(dep[y],y));
}
}
return 0;
}
stack<int> sta;
int fa[MAX_N],fm[MAX_N];vc<int> son[MAX_N];
int f[MAX_N];
void dfs1(int x)
{
f[x]=INF;if(fm[x]==0) f[x]=0;
for(int t=0;t<(int)son[x].size();t++)
{
int y=son[x][t],c=gogo[y];dfs1(y);
chmin(f[x],f[y]+c);
}
}
void insert(pr &now,int num)
{
if(num<=now.FR) now.SE=now.FR,now.FR=num;
else chmax(now.SE,num);
}
int getnum(pr now,int num){return now.FR==num?now.SE:now.FR;}
int ans;
void dfs2(int x,int tt)
{
pr tmp=MP(tt,INF);if(fm[x]==0) insert(tmp,0);
for(int t=0;t<(int)son[x].size();t++)
{
int y=son[x][t],c=gogo[y];
insert(tmp,f[y]+c);
}
if(fm[x]==1)
chmin(ans, tmp.FR );
for(int t=0;t<(int)son[x].size();t++)
{
int y=son[x][t],c=gogo[y];
dfs2(y,getnum(tmp,f[y]+c)+c);
}
}
vc<int> gg;
int solve2(int a,int b)
{
while(sta.size()) sta.pop();
int n=ss[a].size(),m=ss[b].size();
int p1=0,p2=0;gg.clear();
for(int t=0;t<n+m;t++)
{
int now;
if(p2==m or (p1<n and dfn[ss[a][p1]]<=dfn[ss[b][p2]]) ) now=ss[a][p1++],fm[now]=0;
else now=ss[b][p2++],fm[now]=1;
if(sta.size() and sta.top()==now) return 0;//重复
int lst=0;while(sta.size() and !in(sta.top(),now)) lst=sta.top(),sta.pop();
if(!lst) ;
else
{
int lca=getlca(lst,now);
if(!sta.size()) sta.push(lca),gg.PB(lca),fm[lca]=2,fa[lca]=0,fa[lst]=fa[now]=lca;
else if(sta.top()!=lca and now!=lca) fa[lca]=sta.top(),sta.push(lca),gg.PB(lca),fm[lca]=2,fa[lst]=fa[now]=lca;
}
if(sta.size()) fa[now]=sta.top(); else fa[now]=0;sta.push(now);gg.PB(now);
}
while(sta.size()>1) sta.pop();int rt=sta.top();fa[rt]=0;
for(int t=0;t<(int)gg.size();t++) {int x=gg[t];son[fa[x]].PB(x),gogo[x]=getdis(fa[x],x);}
ans=INF;dfs1(rt);
dfs2(rt,INF);
for(int t=0;t<(int)gg.size();t++) son[fa[gg[t]]].clear();
return ans;
}
void main()
{
bin[0]=1;for(int i=1;i<40;i++) bin[i]=bin[i-1]<<1;
lg[1]=0;for(int i=2;i<MAX_N*2;i++) lg[i]=lg[i>>1]+1;
int T=qread();
while(T--)
{
for(int i=0;i<MAX_N;i++) to[i].clear(),ss[i].clear(),on[i].clear();
int n=qread(),m=qread();
for(int i=1;i<n;i++){int x=qread(),y=qread(),c=qread();to[x].PB(MP(y,c));to[y].PB(MP(x,c));}
dfs(1,0);
for(int t=1;t<=20;t++) for(int i=1;i<=pp-bin[t]+1;i++) mp[i][t]=gmin(mp[i][t-1],mp[i+bin[t-1]][t-1]);
int kk=0;
for(int i=1;i<=m;i++)
{
int k=qread();
while(k--) {int x=qread();ss[i].PB(x);on[x].PB(i);}
sort(ss[i].begin(),ss[i].end(),cmp);ss[i].resize(unique(ss[i].begin(),ss[i].end())-ss[i].begin());
kk+=ss[i].size();
}
memset(preans,0x3f,sizeof preans);
int qq=qread(),lstans=0;
int T=sqrt(kk*log2(qq)),cnt=0;
for(int i=1;i<=m;i++)
if((int)ss[i].size()<=T) id[i]=0;
else id[i]=++cnt,solve1(i);
while(qq--)
{
int a=qread(),b=qread();
if(a==b) write2(lstans=0);
else if(!id[a] and !id[b]) write2(lstans=solve2(a,b));
else
{
if(!id[a]) swap(a,b);
write2(lstans=preans[id[a]][b]);
}
}
}
}
};
signed main()
{
//freopen("a.in","r",stdin);
srand(time(0));
mine::main();
}

GDKOI2018D2T4

那时候啥都不会的我似乎乱搞这题搞了很久……所以想再做一次,结果又还是不会

首先我们看完后很自然的想法是直接 $ans=\sum_{i=1}^n\frac{S2(L,i) P_n^i}{n-i+1} $

然后可以得到80分,但似乎是死路一条了……

考虑题目有什么性质没有利用,即 $\frac{1}{k+1}$

考虑一个式子: $(1-1)^{k+1}=\sum_{i=0}^{k+1} (-1)^{i+1}C_{k+1}^{i+1}->\frac{1}{k+1}=\sum_{i=0}^k (-1)^iC_k^i \frac{1}{i+1}$

$ans=\sum_{i=0}^{n-1} (-1)^iC_n^i \frac{1}{i+1} (n-i)^L$

幂函数是完全积性函数,可以线筛

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
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
//#define double long double
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void write1(ll num){write(num);putchar(' ');}
void write2(ll num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<int,int>
#define PB push_back
#define vc vector
void chmax(int &x,const int y) {x=x>y?x:y;}
void chmin(int &x,const int y) {x=x<y?x:y;}
const int MOD=998244353;
void add(ll &x,ll y){x+=y;if(x>=MOD) x-=MOD;if(x<=-MOD) x+=MOD;}
ll qpower(ll x,int e)
{
ll ans=1;
while(e)
{
if(e&1) ans=ans*x%MOD;
x=x*x%MOD;e>>=1;
}
return ans;
}
ll inv2(ll x){return qpower(x,MOD-2);}
const int MAX_N=5e6+10;
bool mark[MAX_N];int prn=0,pp[MAX_N],nk[MAX_N];
void pre(int nn)
{
nk[1]=1;
for(int i=2;i<MAX_N;i++)
{
if(!mark[i]) pp[++prn]=i,nk[i]=qpower(i,nn);
for(int j=1;j<=prn and (ll)i*pp[j]<MAX_N;j++)
{
int t=i*pp[j];mark[t]=1;
nk[t]=(ll)nk[i]*nk[pp[j]]%MOD;
if(i%pp[j]==0) break;
}
}
}
ll fac[MAX_N],inv[MAX_N],facinv[MAX_N];
ll C(int n,int m){return fac[n]*facinv[m]%MOD*facinv[n-m]%MOD;}
void main()
{
fac[0]=1;for(int i=1;i<MAX_N;i++) fac[i]=fac[i-1]*i%MOD;
inv[1]=1;for(int i=2;i<MAX_N;i++) inv[i]=ll(MOD-MOD/i)*inv[MOD%i]%MOD;
facinv[0]=1;for(int i=1;i<MAX_N;i++) facinv[i]=facinv[i-1]*inv[i]%MOD;
int n=qread(),L=qread();pre(L);
ll ans=0;
for(int i=0,t=1;i<=n-1;i++,t=-t) add(ans, (ll)t*C(n,i)*inv[i+1]%MOD*nk[n-i]%MOD );
write((ans+MOD)%MOD);
}
};
signed main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/90dc.html
转载请注明出处,谢谢!