T1
solution
考虑每个质数能产生的贡献是它的所有倍数项的贡献，即对于质数 \(p\)，只有 \(p^{n + 1 - p},(2p)^{n + 1 - 2p},\cdots,(p\lfloor \frac{n}{p} \rfloor)^{n + 1 - p\lfloor \frac{n}{p} \rfloor}\) 这些项有贡献。
code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e7+5;
int n;
int p[665000],cnt=0;
bool f[N];
ll sum[665000];
void pre(){memset(f,1,sizeof(f));for(int i=2;i<=n;++i){if(f[i]) p[++cnt]=i;for(int j=1;j<=cnt&&i*p[j]<=n;++j){f[i*p[j]]=0;if(i%p[j]==0) break;}}
}
ll calc(int x){int num=n/x;return 1ll*num*(n+1)-1ll*x*num*(num+1)/2;
}
int main(){freopen("factorial.in","r",stdin);freopen("factorial.out","w",stdout);cin>>n;pre();for(int i=1;i<=cnt;++i){ll k=0;ll c=p[i];while(1){k+=calc(c);c*=p[i];if(c>n) break;}sum[i]=k;}printf("f(%d)=",n);if(sum[1]==1) printf("2");else printf("2^%lld",sum[1]);for(int i=2;i<=cnt;++i){if(sum[i]==1) printf("*%d",p[i]);else printf("*%d^%lld",p[i],sum[i]);}printf("\n");fclose(stdin);fclose(stdout);return 0;
}
T2
solution
无向图中两点间的简单路径必过一点，此点为割点。
那么能两两连边的就只有同一个点双中的点。
注意：割点连接的是点双。
（不知道为什么，以前一直记的是割点连边双，割边连点双）
code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5;
int read(){int num=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){num=(num<<1)+(num<<3)+ch-'0';ch=getchar();}return num*f;
}
int n,m;
ll sum=0;
vector<int> G[N];
int dfn[N],low[N],cnt=0,bcc=0;
stack<int> s;
vector<int> ans[N];
void tarjan(int u,int fa){dfn[u]=++cnt;low[u]=cnt;s.push(u);for(int i=0;i<G[u].size();++i){int v1=G[u][i];if(v1==fa) continue;if(!dfn[v1]){tarjan(v1,u);low[u]=min(low[u],low[v1]);if(low[v1]>=dfn[u]){++bcc;while(s.top()!=v1){ans[bcc].push_back(s.top());s.pop();}ans[bcc].push_back(s.top());s.pop();ans[bcc].push_back(u);}}else low[u]=min(low[u],dfn[v1]);}if(fa==0&&G[u].size()==0) ans[++bcc].push_back(u);
}
int main(){freopen("graph.in","r",stdin);freopen("graph.out","w",stdout);n=read();m=read();for(int i=1;i<=m;++i){int ui=read(),vi=read();G[ui].push_back(vi);G[vi].push_back(ui);}for(int i=1;i<=n;++i)if(!dfn[i]){while(!s.empty()) s.pop();tarjan(i,0);}for(int i=1;i<=bcc;++i){ll t=1ll*ans[i].size();sum+=t*(t-1)/2;}printf("%lld\n",sum);fclose(stdin);fclose(stdout);return 0;
}
T3
solution
统计满足一定条件的数的数量（即计数），对数位有要求，提供数字区间限制，上界很大，暴力会超时，考虑用数位 DP。
从高位到低位确定满足条件的数，枚举一个前缀与 \(x\) 一致，接下来的一位比 \(x\) 小，考虑一下此时后面位的取值就是还没有被确定的那些位的任意选择。我们用并查集把限制关系维护一下，很容易计算出满足条件的数。
code
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
const int mod=19260817;
int n,m;
int a[N],b[N];
int fa[N];
int cf[N];
int find(int x){if(fa[x]!=x) fa[x]=find(fa[x]);return fa[x];
}
int solve(int c[]){int tot=0;int res=0;for(int i=1;i<=n;++i)if(fa[i]==i)tot++;for(int i=n;i>=1;--i){if(fa[i]==i){tot--;res=(res+c[i]*cf[tot])%mod;}if(c[find(i)]<c[i]) res=(res+cf[tot])%mod;if(c[find(i)]!=c[i]) break;}return res;
}
int main(){freopen("counting.in","r",stdin);freopen("counting.out","w",stdout);cin>>n;cf[0]=1;for(int i=1;i<=n;++i){fa[i]=i;cf[i]=cf[i-1]*10%mod;}for(int i=1;i<=n;++i) scanf("%d",&a[i]);for(int i=1;i<=n;++i) scanf("%d",&b[i]);cin>>m;for(int i=1;i<=m;++i){int ui,vi;scanf("%d%d",&ui,&vi);int uf=find(ui),vf=find(vi);if(uf==vf) continue;fa[min(uf,vf)]=max(uf,vf);}printf("%d\n",(solve(b)-solve(a)+mod)%mod);fclose(stdin);fclose(stdout);return 0;
}
T4（原题解）
solution
考虑时刻我们购买的灯笼都一定形成一个区间（否则一定有一段是目前没用的）,我们设 dpx,y 表示当前区间左端点为 \(a_x\), 右端点为 \(b_y\), 我们可以处理出来每个灯笼的 \(a_x\) 和 \(b_x\) 对能到达的区间的限制, \(dp_{x,y}\) 所代表的区间就是 \(a_x\) 的限制和 \(b_y\) 的限制的交集。
考虑转移顺序, 我们按照 \(a_x\) 递增, \(b_x\) 递减的顺序遍历每一个状态, 考虑转移有三种情况。
- \(dp_{x,y′} + c_{y′}\to dp_{x,y},y′\) 在 \((x,y)\) 限制区间内。
- \(dp_{x′,y} + c_{x′}\to dp_{x,y},x′\) 在 \((x,y)\) 限制区间内。
- \(dp_{x′,x′} + c_{x′}\to dp_{x,y},x′\) 在 \((x,y)\) 限制区间内。 考虑前两种转移, 对于同一个 \(x\)，\(b_{y1} < b_{y2}\), 那么 \((x,y_1)\) 的限制区间一定是 \((x,y_2)\) 的限制区间的子区间, 于是我们可以用一个优先队列维护 \(dp_{x,y′} + c_{y′}\), 堆顶转移不了 pop 即可。
考虑第三种转移, 因为 \(dp_{x′,x′}\) 种类很少其实也不是什么问题, 我们把 \(dp_{x′,y}\), 其中 \((a_y,b_y)\) 是 \((a_{x′},b_{x′})\) 的子区间的 \(dp\) 值设为 \(dp_{x′,x′}\), 用上面的转移即可。
code
#include <bits/stdc++.h>
#define N 2100
using namespace std;
int n, k, h[N], p[N], c[N], a[N], b[N], lim[N][2][2], dp[N][N];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>ql[N], qr[N];
int main() {//freopen("lantern.in", "r", stdin);//freopen("lantern.out", "w", stdout);cin.tie(0)->sync_with_stdio(0);cin >> n >> k;for (int i = 1; i <= n; i++)cin >> h[i];for (int i = 1; i <= k; i++) {cin >> p[i] >> c[i] >> a[i] >> b[i];lim[i][0][0] = p[i] + 1;while (lim[i][0][0] > 1 && h[lim[i][0][0] - 1] >= a[i])lim[i][0][0]--;lim[i][0][1] = p[i] - 1;while (lim[i][0][1] < n && h[lim[i][0][1] + 1] >= a[i])lim[i][0][1]++;lim[i][1][0] = p[i] + 1;while (lim[i][1][0] > 1 && h[lim[i][1][0] - 1] <= b[i])lim[i][1][0]--;lim[i][1][1] = p[i] - 1;while (lim[i][1][1] < n && h[lim[i][1][1] + 1] <= b[i])lim[i][1][1]++;}vector<int> vl, vr;for (int i = 1; i <= k; i++)vl.push_back(i), vr.push_back(i);sort(vl.begin(), vl.end(),[&](int x, int y) { return a[x] == a[y] ? b[x] > b[y] : a[x] < a[y]; });sort(vr.begin(), vr.end(),[&](int x, int y) { return b[x] == b[y] ? a[x] < a[y] : b[x] > b[y]; });memset(dp, -1, sizeof(dp));for (auto i : vl)for (auto j : vr) {if (i != j && a[i] <= a[j] && b[i] >= b[j]) {dp[i][j] = dp[i][i];} else if (i != j && a[j] <= a[i] && b[j] >= b[i]) {dp[i][j] = dp[j][j];} else if (a[i] <= a[j] && b[i] <= b[j]) {int l = max(lim[i][0][0], lim[j][1][0]),r = min(lim[i][0][1], lim[j][1][1]);if (l > min(p[i], p[j]) || r < max(p[i], p[j]))continue;if (l == 1 && r == n) {dp[i][j] = 0;} else {while (!ql[i].empty() &&(p[ql[i].top().second] < l || p[ql[i].top().second] > r ||a[ql[i].top().second] > b[j]))ql[i].pop();if (!ql[i].empty()) {int tmp = ql[i].top().first;if (dp[i][j] == -1 || dp[i][j] > tmp)dp[i][j] = tmp;}while (!qr[j].empty() &&(p[qr[j].top().second] < l || p[qr[j].top().second] > r ||b[qr[j].top().second] < a[i]))qr[j].pop();if (!qr[j].empty()) {int tmp = qr[j].top().first;if (dp[i][j] == -1 || dp[i][j] > tmp)dp[i][j] = tmp;}}}if (dp[i][j] != -1) {ql[i].push({dp[i][j] + c[j], j});qr[j].push({dp[i][j] + c[i], i});}}for (int i = 1; i <= k; i++) {cout << (dp[i][i] == -1 ? -1 : dp[i][i] + c[i]) << '\n';}return 0;
}