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;
}
View Code
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;
}
View Code
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;
}
View Code