此题爆零。原因不知道可以因费马小定理推出 b' = b MOD p。
可以看出，f(u,p) = v 在这道题里面意思就是 v = u MOD p，由于p是一个质数，那么可以知道所有的a[i]等价于a[i] % p，所有的b[i]等价于b[i] % (p-1)
懒得讲部分分 正解如下：
1、首先我们可以看出处理过后所有的a，b满足 0 <= a <= p-1，0 <= b <= p-2，又 p <= 5000 ，所以我们只需要算a，b的同时开俩桶记录0~p-1(p-2)分别在算a和算b中出现的次数即可，不需要实实在在枚举a，b。
2、算出次数后，也不需要用快速幂算次方了，可以看出 b 最多才5000-2，我们枚举a定下来，算次方时一个变量累计就好了。
这样算法为O(n+m+p^2)，可以过。
代码：
#include<bits/stdc++.h> using namespace std; #define ll long long #define pt putchar #define gc getchar #define ex pt('\n') #define ko pt(' ') const int MAXN = 1e6 + 5; const int P = 5e3 + 5; ll p,q; ll n,a[MAXN],A,B,C; ll m,b[MAXN],D,E,F; ll cnta[MAXN],cntb[MAXN],now; ll sum = 0; void in(ll &x) { ll num = 0,f = 1; char ch = gc(); while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = gc();} while(ch >= '0' && ch <= '9') {num = (num<<3) + (num<<1) + (ch-'0'); ch = gc();} x = num*f; } void out(ll x) { if(x < 0) x = -x,pt('-'); if(x > 9) out(x/10); pt(x % 10 + '0'); } ll quick_mi(ll a,ll b) { a %= p; ll ans = 1; while(b) { if(b & 1) ans = a*ans % p; a = a*a % p; b >>= 1; } return ans % p; } inline void init() { in(p); in(q); in(n); in(a[1]); in(a[2]); in(A); in(B); in(C); in(m); in(b[1]); in(b[2]); in(D); in(E); in(F); a[1] %= p,a[2] %= p; cnta[a[1]]++; cnta[a[2]]++; b[1] %= (p-1),b[2] %= (p-1); cntb[b[1]]++; cntb[b[2]]++; for(int i = 3;i <= n;i++) { a[i] = ((A*a[i-1] % p - (B*a[i-2] % p) + p) % p - C + p) % p; cnta[a[i]]++; } for(int i = 3;i <= m;i++) { b[i] = (((D*b[i-1] % (p-1) + E*b[i-2] % (p-1)) % (p-1) + (p-1)) % (p-1) + F + (p-1)) % (p-1); cntb[b[i]]++; } } inline void work() { for(int i = 0;i <= p-1;i++) { if(!cnta[i]) continue; now = 1; for(int j = 0;j <= p-2;j++) { if(now <= q) sum += cntb[j]*cnta[i]; now = now * i % p; } } out(sum); } int main() { init(); work(); return 0; }同样懒得说部分分你如果不想打正解就直接全排列40分+特判10分 = 50分不动脑子就可以得到。
正解考虑贪心。
先sort一遍，然后建立一个空序列，从小到大加入人，尽量往左边加，用线段树维护其正确性，最后序列即为答案。
可以看出一个数要想合法地加入序列中，那么一定要保证其向左或是向右（取其小值）可供比此数大的数加入的空格，要等于数据中所给出的此人记下来的比他高的人数，这样就一定能满足正确性。
你可以n^2 枚举数 + 插入数 70分。
当然线段树相当于把插入过程变为logn的，也很简单，就一开始整个线段树中空格数铺满，后面加人尽量向左加，加的位置空格数-1，然后updata一下上面的节点信息就可以啦。
代码：
#include<bits/stdc++.h> using namespace std; #define ll long long #define pt putchar #define gc getchar #define ex pt('\n') #define ko pt(' ') #define lx x << 1 #define rx x << 1 | 1 const int MAXN = 1e5 + 5; int n,space[MAXN<<2]; int ans[MAXN]; struct person { int h,idx,higher; bool operator < (const person one) const { return h < one.h; } }a[MAXN]; void in(int &x) { int num = 0,f = 1; char ch = gc(); while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = gc();} while(ch >= '0' && ch <= '9') {num = (num<<3) + (num<<1) + (ch-'0'); ch = gc();} x = num*f; } void out(int x) { if(x < 0) x = -x,pt('-'); if(x > 9) out(x/10); pt(x % 10 + '0'); } void build(int x,int l,int r) { if(l == r) {space[x] = 1; return;} int mid = (l + r) >> 1; build(lx,l,mid); build(rx,mid+1,r); space[x] = space[lx] + space[rx]; } void updata(int x,int l,int r,int pos) { if(l == r) {space[x]--; return;} int mid = (l + r) >> 1; if(pos <= mid) updata(lx,l,mid,pos); else updata(rx,mid+1,r,pos); space[x] = space[lx] + space[rx]; } int ask(int x,int l,int r,int need) { if(l == r) return l; int mid = (l + r) >> 1; if(need <= space[lx]) ask(lx,l,mid,need); else ask(rx,mid+1,r,need - space[lx]); } int main() { in(n); for(int i = 1;i <= n;i++) in(a[i].h),in(a[i].higher); sort(a+1,a+1+n); build(1,1,n); for(int i = 1;i <= n;i++) { int num = min(a[i].higher,n - i - a[i].higher) + 1; if(num <= 0 || num > n) {cout << "impossible"; return 0;} int now = ask(1,1,n,num); ans[now] = a[i].h; updata(1,1,n,now); } for(int i = 1;i < n;i++) out(ans[i]),ko; out(ans[n]); return 0; }第三题：不会，看不懂，学不来。
