Fansblog：
虽然想到了威尔逊定理，但是觉得用不上。
这里有个结论，那就是相邻的质数之间的最大距离 <= 1e5 + 5。
有了这个结论，我们就能暴力找到Q。
然后根据威尔逊定理 (p - 1)! mod p = p - 1。
那么(p - 1) ! = (p - 1) * (p - 2) * .... Q * ... 1= p - 1.
所以Q! = (p - 1) / ((p - 1) * (p - 2) * ... (Q + 1) )
但是这里因为p最大为1e14，所以单纯乘法可能会爆longlong。
所以对于每个乘法都要用快速乘。
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 3e5 + 5; const int M = 1e6 + 5; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e9 #define dbg(ax) cout << "now this num is " << ax << endl; bool check(LL x) { LL m = sqrt(x); for(int i = 2;i <= m;++i) { if(x % i == 0) return false; } return true; } LL quick_c(LL a,LL b,LL mod) { LL re = 0; while(b) { if(b & 1) re = (re + a) % mod; b >>= 1; a = (a << 1) % mod; } return re; } LL quick_mi(LL a,LL b,LL mod) { LL re = 1; while(b) { if(b & 1) re = quick_c(re,a,mod); a = quick_c(a,a,mod); b >>= 1; } return re; } int main() { int ca;scanf("%d",&ca); while(ca--) { LL p;scanf("%lld",&p); LL ans = p - 1,up; for(LL i = p - 1;;--i) { if(check(i)) { up = i; break; } } for(LL i = up + 1;i <= p - 1;++i) ans = quick_c(ans,quick_mi(i,p - 2,p),p); printf("%lld\n",ans); } // system("pause"); return 0; }
Find the answer：
这题个人觉得比较直白，很显然最优的取法是排序之后取最大的前缀和。
那么这点我们可以建一棵类似权值树的树，上面的节点的值代表排序后的a[L]。
然后每次查询区间最大的和即可。
注意的是这里不能对值离散化，也就是相同的点要看成不同的，这样方便计算个数。
但是这题的输出逆天了，必须要每个后面都带一个空格，不然就报pe...
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<LL,int> pii; const int N = 2e5 + 5; const int M = 4e5 + 5; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e9 #define dbg(ax) cout << "now this num is " << ax << endl; int a[N],b[N],ans[N]; struct QT{int id,x;}p[N]; struct Node{int L,r,num;LL sum;}node[M << 2]; bool cmp(QT a,QT b) { return a.x < b.x; } void Pushup(int idx) { node[idx].sum = node[idx << 1].sum + node[idx << 1 | 1].sum; node[idx].num = node[idx << 1].num + node[idx << 1 | 1].num; } void build(int L,int r,int idx) { node[idx].L = L,node[idx].r = r,node[idx].sum = node[idx].num = 0; if(L == r) { return ; } int mid = (L + r) >> 1; build(L,mid,idx << 1); build(mid + 1,r,idx << 1 | 1); } void update(int x,LL val,int idx) { if(node[idx].L == node[idx].r) { node[idx].sum = val; node[idx].num = 1; return ; } int mid = (node[idx].L + node[idx].r) >> 1; if(mid >= x) update(x,val,idx << 1); else update(x,val,idx << 1 | 1); Pushup(idx); } int query(LL up,int idx) { if(node[idx].sum <= up) { return node[idx].num; } int num = 0; if(node[idx << 1].sum <= up) { num += node[idx << 1].num; num += query(up - node[idx << 1].sum,idx << 1 | 1); } else num += query(up,idx << 1); return num; } int main() { int ca;scanf("%d",&ca); while(ca--) { int n,m;scanf("%d %d",&n,&m); for(int i = 1;i <= n;++i) scanf("%d",&a[i]),p[i].id = i,p[i].x = a[i]; sort(p + 1,p + n + 1,cmp); for(int i = 1;i <= n;++i) b[p[i].id] = i; build(1,n,1); for(int i = 1;i <= n;++i) { int ma = query(m - a[i],1); ans[i] = i - 1 - ma; update(b[i],a[i],1); } for(int i = 1;i <= n;++i) printf("%d ",ans[i]); printf("\n"); } //system("pause"); return 0; }
K Subsequence：
这题一直想的是怎么dp，居然是用费用流做的。
但是建模之后确实就很好理解了。
这里的一个问题就是普通费用流会被卡时间。
先把spfa换成dij，复杂度依旧不够，要再上原始对偶优化才行。
/ Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<LL,int> pii; const int N = 4e3 + 5; const int M = 4e6 + 5; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e9 #define dbg(ax) cout << "now this num is " << ax << endl; int a[N]; struct edge { int to, capacity, cost, rev; edge() {} edge(int to, int _capacity, int _cost, int _rev) :to(to), capacity(_capacity), cost(_cost), rev(_rev) {} }; struct Min_Cost_Max_Flow { int V, H[N + 5], dis[N + 5], PreV[N + 5], PreE[N + 5]; vector<edge> G[N + 5]; //调用前初始化 void Init(int n) { V = n; for (int i = 0; i <= V; ++i)G[i].clear(); } //加边 void add(int from, int to, int cap, int cost) { G[from].push_back(edge(to, cap, cost, G[to].size())); G[to].push_back(edge(from, 0, -cost, G[from].size() - 1)); } //flow是自己传进去的变量，就是最后的最大流，返回的是最小费用 pii Min_cost_max_flow(int s, int t, int f) { int flow = 0; int res = 0; fill(H, H + 1 + V, 0); while (f) {//f - 可以达到的最大的最大流 priority_queue <pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q; fill(dis, dis + 1 + V, INF); dis[s] = 0; q.push(pair<int, int>(0, s)); while (!q.empty()) { pair<int, int> now = q.top(); q.pop(); int v = now.second; if (dis[v] < now.first)continue; for (int i = 0; i < G[v].size(); ++i) { edge& e = G[v][i]; if (e.capacity > 0 && dis[e.to] > dis[v] + e.cost + H[v] - H[e.to]) { dis[e.to] = dis[v] + e.cost + H[v] - H[e.to]; PreV[e.to] = v; PreE[e.to] = i; q.push(pair<int, int>(dis[e.to], e.to)); } } } if (dis[t] == INF)break; for (int i = 0; i <= V; ++i)H[i] += dis[i]; int d = f; for (int v = t; v != s; v = PreV[v])d = min(d, G[PreV[v]][PreE[v]].capacity); f -= d; flow += d; res += d*H[t]; for (int v = t; v != s; v = PreV[v]) { edge& e = G[PreV[v]][PreE[v]]; e.capacity -= d; G[v][e.rev].capacity += d; } } return pii{flow,res}; } }; Min_Cost_Max_Flow MCMF; /* i - st[i,n] ed [i + n,2 * n] s - 2 * n + 3,t - st - 2 * n + 1,ed - 2 * n + 2 */ int main() { int ca;scanf("%d",&ca); while(ca--) { int n,k;scanf("%d %d",&n,&k); MCMF.Init(2 * n + 2); for(int i = 1;i <= n;++i) scanf("%d",&a[i]); int s = 0,t = 2 * n + 2; for(int i = 1;i <= n;++i) { MCMF.add(s,i,1,0); MCMF.add(i,i + n,1,-a[i]); MCMF.add(i + n,2 * n + 1,1,0); } MCMF.add(2 * n + 1,2 * n + 2,k,0); for(int i = 1;i <= n;++i) { for(int j = i + 1;j <= n;++j) { if(a[j] >= a[i]) MCMF.add(i + n,j,1,0); } } pii ans = MCMF.Min_cost_max_flow(s,t,INF); printf("%d\n",-ans.second); } // system("pause"); return 0; }