#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int S=8;
ll mult_mod(ll a,ll b,ll c)
{
a%=c;
b%=c;
ll ret=0,tmp=a;
while (b)
{
if (b&1)
{
ret+=tmp;
if (ret>c)
{
ret-=c;
}
}
tmp<<=1;
if (tmp>c) tmp-=c;
b>>=1;
}
return ret;
}
ll pow_mod(ll a,ll n,ll mod)
{
ll ret=1;
ll temp=a%mod;
while (n)
{
if(n&1)
{
ret=mult_mod(ret,temp,mod);
}
temp=mult_mod(temp,temp,mod);
n>>=1;
}
return ret;
}
bool check(ll a,ll n,ll x,ll t)
{
ll ret=pow_mod(a,x,n);
ll last=ret;
for (int i=1; i<=t; i++)
{
ret=mult_mod(ret,ret,n);
if (ret==1&&last!=1&&last!=n-1)
{
return 1;
}
last=ret;
}
if (ret!=1)
{
return 1;
}
return 0;
}
bool Miller_Rabin(ll n)
{
if (n<2)
{
return 0;
}
if (n==2)
{
return 1;
}
if ((n&1)==0)
{
return 0;
}
ll x=n-1;
ll t=0;
while ((x&1)==0)
{
x>>=1;
t++;
}
srand(time(NULL));
for (int i=0; i<S; i++)
{
ll a=rand()%(n-1)+1;
if (check(a,n,x,t))
{
return 0;
}
}
return 1;
}
ll factor[100];
int tol;
ll gcd(ll a,ll b)
{
if (!b)
{
return a;
}
return gcd(b,a%b);
}
ll pollard_rho(ll x,ll c)
{
ll i=1,k=2;
srand(time(NULL));
ll x0=rand()%(x-1)+1;
ll y=x0;
while (1)
{
i++;
x0=(mult_mod(x0,x0,x)+c)%x;
ll d=gcd(y-x0,x);
if (d!=1&&d!=x)
{
return d;
}
if (y==x0)
{
return x;
}
if (i==k)
{
y=x0;
k+=k;
}
}
}
__int128 quick(__int128 a,__int128 b,__int128 p)
{
__int128 ret=1%p;
while (b)
{
if (b&1)
{
ret=ret*a%p;
}
b>>=1;
a=a*a%p;
}
return ret;
}
void findfac(ll n,ll k)
{
if (n==1)
{
return;
}
if (Miller_Rabin(n))
{
factor[tol++]=n;
return;
}
ll p=n;
ll c=k;
while (p>=n)
{
p=pollard_rho(p,c--);
}
findfac(p,k);
findfac(n/p,k);
}
__int128 inv(__int128 a,__int128 p){
return quick(a,p-2,p);
}
int main()
{
ll t,p,prime;
__int128 ans;
scanf("%lld",&t);
while (t--)
{
scanf("%lld",&p);
for (ll i=p-1; i>=2; i--)
{
if (Miller_Rabin(i))
{
prime=i;
break;
}
}
ans=p-1;
for (__int128 i=p-1;i>prime;i--){
ans=ans*inv(i,p)%p;
}
printf("%lld\n",(ll)ans);
}
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=200010;
ll w[N],b[N],n,m;
struct node{
ll num,sum;
}t[N*4];
struct data{
ll num,rk,id;
}a[N];
inline void build(ll rt,ll l,ll r) {
t[rt].num = t[rt].sum = 0;
if (l == r) {
return;
}
ll mid = (l + r) >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
}
inline void change(ll rt,ll pos,ll l,ll r) {
if (l == r) {
t[rt].num = 1;
t[rt].sum = b[pos];
return;
}
ll mid = (l + r) >> 1;
if (pos <= mid) {
change(rt << 1, pos, l, mid);
} else {
change(rt << 1 | 1, pos, mid + 1, r);
}
t[rt].sum = t[rt << 1].sum + t[rt << 1 | 1].sum;
t[rt].num = t[rt << 1].num + t[rt << 1 | 1].num;
}
inline ll query(ll rt,ll w,ll l,ll r) {
if (l == r) {
return t[rt].sum <= w ? t[rt].num : 0;
}
ll mid=(l+r)>>1;
if (t[rt << 1].sum <= w) {
return t[rt << 1].num + query(rt << 1 | 1, w - t[rt << 1].sum,mid+1,r);
} else {
return query(rt << 1, w, l, mid);
}
}
inline bool cmp1(data a,data b) {
return a.num < b.num;
}
inline bool cmp2(data a,data b) {
return a.id < b.id;
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%lld", &w[i]);
a[i].id = i;
a[i].num = w[i];
}
sort(a + 1, a + n + 1, cmp1);
for (int i = 1; i <= n; i++) {
a[i].rk = i;
b[i] = a[i].num;
}
sort(a + 1, a + n + 1, cmp2);
build(1, 1, n);
for (int i = 1; i <= n; i++) {
printf("%lld ", i - query(1, m - w[i], 1, n) - 1);
change(1, a[i].rk, 1, n);
}
printf("\n");
}
}
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PI;
const int maxn=5000;
const int inf=0x3f3f3f3f;
int a[maxn];
struct Min_Cost_Max_Flow{
struct edge{
int to,cap,cost,rev;
edge(){};
edge(int _to,int _cap,int _cost,int _rev):to(_to),cap(_cap),cost(_cost),rev(_rev){};
};
vector<edge>E[maxn];
int h[maxn],n,d[maxn],preV[maxn],preE[maxn];
void init(int n){
this->n=n;
for (int i=0;i<=n;i++){
E[i].clear();
h[i]=0;
}
}
void add(int from,int to,int cap,int cost){
E[from].push_back(edge(to,cap,cost,E[to].size()));
E[to].push_back(edge(from,0,-cost,E[from].size()-1));
}
PI dijkstra(int s,int t,int f){
int cost=0,flow=0;
for (int i=0;i<=n;i++){
h[i]=0;
}
while (f){
priority_queue<PI,vector<PI>,greater<PI> >q;
for (int i=0;i<=n;i++){
d[i]=inf;
}
d[s]=0;
q.push(make_pair(0,s));
while (!q.empty()){
PI now=q.top();
q.pop();
int v=now.second;
if (d[v]<now.first){
continue;
}
for (int i=0;i<E[v].size();i++){
edge &e=E[v][i];
if (e.cap>0&&d[e.to]>d[v]+e.cost+h[v]-h[e.to]){
d[e.to]=d[v]+e.cost+h[v]-h[e.to];
preV[e.to]=v;
preE[e.to]=i;
q.push(make_pair(d[e.to],e.to));
}
}
}
if (d[t]==inf)break;
for (int i=0;i<=n;i++){
h[i]+=d[i];
}
int d=f;
for (int i=t;i!=s;i=preV[i]){
d=min(d,E[preV[i]][preE[i]].cap);
}
f-=d;
flow+=d;
cost+=d*h[t];
for (int i=t;i!=s;i=preV[i]){
edge &e=E[preV[i]][preE[i]];
e.cap-=d;
E[i][e.rev].cap+=d;
}
}
return make_pair(flow,cost);
}
}G;
int main() {
int t,k,n;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
G.init(2*n+2);
int S = 0, T = 2 * n + 2;
G.add(S, n * 2 + 1, k, 0);
for (int i = 1; i <= n; i++) {
G.add(n * 2 + 1, i, 1, 0);
G.add(i, n + i, 1, -a[i]);
G.add(n + i, T, 1, 0);
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (a[i] <= a[j]) {
G.add(n + i, j, 1, 0);
}
}
}
PI ans=G.dijkstra(S,T,inf);
printf("%d\n",-ans.second);
}
}
题意：要求把一个序列分成连续的k块（可以去掉后缀），使得权值和最大的那一块权值最小，求出这个最小值
解法：二分这个权值，然后根据权值去把序列切块，如果能切成k块甚至更多，那么一定合法，否则不合法，怎么check呢？设d[i]为前 i 个数在最大权值限制在T时最多能切的块数，转移：对于所有的 L < i，如果sum[i] - sum[L] <= T，那么d[i] = max(d[i], d[L] + 1)，很显然这个dp check复杂度是n^2，我们变形：sum[i] - T <= sum[L]，我们二分找到最小的sum[L]，然后在线段树中查其区间[sum[L], max(sum[x])]最大值mx，d[i] = mx + 1即可，然后在线段树的 sum[i]点更新d[i]。