比赛链接https://www.jisuanke.com/contest/3098?view=challenges
B题 拉格朗日插值
题意 T组输入。一个n次多项式 f(x) ，每项的系数不知道，只知道f(0),f(1)..f(n) 的值,m个询问，L,R。计算$sum_{i=L}^{R}f(i)quad mod(9999991)$
$(1leq Tleq 5) $
$(1leq nleq 1000) $
$(1leq mleq 2000) $
$(1leq Lleq R leq 9999990)$
解析 遇到这题我是崩溃的，听大家说是拉格朗日插值，找到了一个快速拉格朗日的板子，贴上去就过了。。。
#include<bits/stdc++.h> using namespace std; #define maxn 1010 typedef long long LL; const LL mod = 9999991; LL powmod(LL aa, LL x) { LL res = 1; for(; x > 0; x >>= 1) { if(x & 1)res = (res * aa) % mod; aa = (aa * aa) % mod; } return res; } struct lagrange { #define ll long long #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define D 2010 //D比MAXN大100就行 ll a[D], f[D], g[D], p[D], p1[D], p2[D], b[D], h[D][2], C[D]; void init(int M) {//初始化：参数填MAXN + 20 f[0] = f[1] = g[0] = g[1] = 1; rep(i, 2, M + 5) f[i] = f[i - 1] * i % mod; g[M + 4] = powmod(f[M + 4], mod - 2); per(i, 1, M + 4) g[i] = g[i + 1] * (i + 1) % mod; } /*给定一组样本数据a[]，规模为0-d，计算出第n项*/ ll calcn(int d, ll *a, ll n) { if (n <= d) return a[n]; p1[0] = p2[0] = 1; rep(i, 0, d + 1) { ll t = (n - i + mod) % mod; p1[i + 1] = p1[i] * t % mod; } rep(i, 0, d + 1) { ll t = (n - d + i + mod) % mod; p2[i + 1] = p2[i] * t % mod; } ll ans = 0; rep(i, 0, d + 1) { ll t = g[i] * g[d - i] % mod * p1[i] % mod * p2[d - i] % mod * a[i] % mod; if ((d - i) & 1) ans = (ans - t + mod) % mod; else ans = (ans + t) % mod; } return ans; } /* 给定一组观测点(0, a[0]), (1, a[1]), ...，(m, a[m])，、 样本点的个数为a(x)的最高次+1。 求在该函数模型下，a[0]+a[1]+...+a[n]的和。 */ ll ta[D]; ll polysum(ll m, ll *a, ll n) { // 给定a[0].. a[m]，求sum_{i=0}^{n}a[i] memcpy(ta, a, sizeof(a[0]) * (m + 1)); ta[m + 1] = calcn(m, ta, m + 1); rep(i, 1, m + 2)ta[i] = (ta[i - 1] + ta[i]) % mod; return calcn(m + 1, ta, n); } }; int main() { int t; scanf("%d",&t); while(t--){ ll a[maxn],n,m; scanf("%lld%lld",&n,&m); for(int i=0;i<=n;i++){ scanf("%lld",&a[i]); } lagrange ri; ri.init(maxn+20); while(m--){ ll l,r; scanf("%lld%lld",&l,&r); printf("%lld ",(ri.polysum(n,a,r)-ri.polysum(n,a,l-1)+mod)%mod); } } }
H题 FWT+线段树
题意 一个n代表A，B数组的长度，A,B两个数组中的数两两或(二进制运算)一下 ，得到一个不去重C数组(显然C的长度为n*n)。接下来一个m代表操作次数，每次输入两个数L,R
如果L等于0，表示询问C数组中第R个数，否则表示C数组中第L个数到第R个数 开根号。
解析 用FWT求出来 or 之后 每个数的个数，然后建立权值线段树，或者前缀和+二分，都可以log时间复杂度求出第k个数是几。只需要知道这个数开了几次根号，L，R会很大，
但是数量只有那么多，离散化一下就可以解决了,1e5开根号大于5次就是1了，小于5次暴力开就好了。
#include <bits/stdc++.h> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef long long ll; typedef pair<int,int> Pii; const int maxn = 3e5+10; ll a[maxn],b[maxn],c[maxn]; void FWT_or(ll *a,int N,int opt) { for(int i=1;i<=N;i<<=1) for(int p=i<<1,j=0;j<=N;j+=p) for(int k=0;k<i;++k) if(opt==1)a[i+j+k]=a[j+k]+a[i+j+k]; else a[i+j+k]=a[i+j+k]-a[j+k]; } ll C[maxn]; int lowbit(int x) { return x&(-x); } ll bitgetsum(int x) { ll ans=0; for(int i=x;i>0;i-=lowbit(i)) ans+=C[i]; return ans; } void bitupdate(int x,int z) { for(int i=x;i<=3e5;i+=lowbit(i)) C[i]+=z; } struct ndoe { ll l,r; }q[maxn]; vector<ll> v; int getid(ll x){ return lower_bound(all(v),x)-v.begin()+1; } ll sum[maxn*4]; void pushUp(int rt) { sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void build(int l,int r,int rt) { if(l==r){ sum[rt]=c[l]; return; } int m=(l+r)>>1; build(l,m,rt<<1); build(m+1,r,rt<<1|1); pushUp(rt); } int query(ll val,int l,int r,int rt) { if(l==r){ return l; } int mid=(l+r)>>1; if(sum[rt<<1]>=val) return query(val,l,mid,rt<<1); else return query(val-sum[rt<<1],mid+1,r,rt<<1|1); } int main() { int n,x,m; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&x);a[x]++; } for(int i=0;i<n;i++){ scanf("%d",&x);b[x]++; } n=2e5; FWT_or(a,n,1);FWT_or(b,n,1); for(int i=0;i<=n;i++) c[i]=1ll*a[i]*b[i]; FWT_or(c,n,-1);build(1,n,1); scanf("%d",&m); for(int i=0;i<m;i++){ scanf("%lld%lld",&q[i].l,&q[i].r); v.pb(q[i].r); if(q[i].l!=0) v.pb(q[i].l); } sort(all(v)); v.erase(unique(all(v)),v.end()); for(int i=0;i<m;i++){ if(q[i].l!=0){ bitupdate(getid(q[i].l),1); bitupdate(getid(q[i].r)+1,-1); } else{ int ans,times = bitgetsum(getid(q[i].r)); if(times>=5){ ans=1; } else{ ans = query(q[i].r,1,n,1); while(times--){ ans=floor(sqrt(ans)); } } printf("%d ",ans); } } return 0; }