# 2019 牛客多校第九场

## The power of Fibonacci

64bit IO Format: %lld

## 题目描述

Amy asks Mr. B  problem A. Please help Mr. B to solve the following problem.
Let Fi be fibonacci number.F0 = 0, F1 = 1, Fi = Fi-1 + Fi-2Given n and m, please calculate\sum_{i = 0}^n F_i^m∑i=0nFim​ As the answer might be very large, output it module 1000000000.

## 输入描述:

The first and only line contains two integers n, m(1 <= n <= 1000000000, 1 <= m <= 1000).

## 输出描述:

Output a single integer, the answer module 1000000000.

## 输入

5 5

## 输出

3402

## 说明

05 + 15 + 15 + 25 + 35 + 55 = 3402

## 输入

10 10

## 输出

696237975

## 说明

Don't forget to mod 1000000000

## 输入

1000000000 1000

## 输出

641796875

## 说明

Time is precious.

#### F[i] – F[i-1] – F[i-2] = 0F[i]^2 – 2 F[i-1]^2 – 2 F[i-2]^2 + F[i-3] = 0F[i]^3 – 3 F[i-1]^3 – 6 F[i-2]^3 + 3 F[i-3] + F[i-4] = 0可以推广吗？可以的，就是Fibonmial Coeficent，通过简单的分析可以得到递推因为m的范围是10，需要结合多项式取模

#include <bits/stdc++.h>
using namespace std;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand()%x;}
typedef long long ll;
ll f[10010000];
ll md[2];
ll qp(ll a,ll b,ll p){
ll ret=1;
while(b){
if(b&1) ret=ret*a%p;
a=a*a%p;
b>>=1;
}
return ret;
}
const ll mod=1e9;
int main(){
md[0]=512;md[1]=1;for(int i=1;i<=9;i++) md[1]*=5;
ll n,m;
scanf("%lld%lld",&n,&m);
f[0]=0,f[1]=1;
ll ans[2];
ans[1]=0;ans[0]=0;
for(int pt=0;pt<=1;pt++){
int j=2;f[j]=f[j-1]+f[j-2];
j++;
for(;;j++){
f[j]=(f[j-1]+f[j-2])%md[pt];
if(f[j]==0 && f[j-1]==1) break;
}
for(int i=0;i<j;i++){
ll su=1ll*n/j;
if(i<=n%j) su++;
ans[pt]=(ans[pt]+qp(f[i],1ll*m,mod)*1ll*su)%md[pt];
}
}
while(ans[1]%md[0]!=ans[0]) ans[1]+=md[1];
printf("%lld\n",ans[1]);
return 0;
}


64bit IO Format: %lld

## 题目描述

Amy asks Mr. B  problem B. Please help Mr. B to solve the following problem.

Let p = 1000000007. Given two integers b and c, please find two integers x and y(0≤x≤y<p)(0 \leq x \leq y < p)(0≤x≤y<p), such that (x+y) mod p=b(x + y) \bmod p = b(x+y)modp=b
(x×y) mod p=c(x \times y) \bmod p = c(x×y)modp=c

## 输入描述:

The first line contains an integer t, which is the number of test cases (1 <= t <= 10).In the following t lines, each line contains two integers b and c (0 <= b, c < p).

## 输出描述:

For each test case, please output x, y in one line.If there is a solution, because x <= y, the solution is unique.If there is no solution, please output -1, -1

## 输入

10
4 4
5 6
10 10
10 25
20000 100000000
0 5
3 6
220 284
0 1
1000000000 1000000000


## 输出

2 2
2 3
-1 -1
5 5
10000 10000
474848249 525151758
352077071 647922939
448762649 551237578
-1 -1
366417496 633582504

#### 解二次方程，核心在于求二次剩余（求平方根）如果p % 4 =3，x^2 % p = a那么x = ±pow(a, (p+1)/4, p)然后就和一般的方程一样解就可以了签到题

#include <bits/stdc++.h>
using namespace std;
mt19937 mrand(random_device {}());
int rnd(int x) {
return mrand()%x;
}
typedef long long ll;
int k;
ll a,p,w;
struct T {
ll x,y;
};
T mul_two(T a,T b,ll p) {
T ans;
ans.x=(a.x*b.x%p+a.y*b.y%p*w%p)%p;
ans.y=(a.x*b.y%p+a.y*b.x%p)%p;
return ans;
}

T qpow_two(T a,ll n,ll p) {
T ans;
ans.x=1;
ans.y=0;
while(n) {
if(n&1) ans=mul_two(ans,a,p);
n>>=1;
a=mul_two(a,a,p);
}
return ans;
}

ll qpow(ll a,ll n,ll p) {
ll ans=1;
a%=p;
while(n) {
if(n&1) ans=ans*a%p;
n>>=1;
a=a*a%p;
}
return ans%p;
}

ll Legendre(ll a,ll p) {
return qpow(a,(p-1)>>1,p);
}

int solve(ll n,ll p) {
if(p==2) return 1;
if(Legendre(n,p)+1==p) return -1;
ll a,t;
while(1) {
a=rand()%p;
t=a*a-n;
w=(t%p+p)%p;
if(Legendre(w,p)+1==p) break;
}
T tmp;
tmp.x=a;
tmp.y=1;
T ans=qpow_two(tmp,(p+1)>>1,p);
return ans.x;
}
int main() {
int T;
scanf("%d",&T);
ll p=1000000007;
while(T--){
ll b,c;
scanf("%lld%lld",&b,&c);
ll a=(b*b%p-4*c%p+p)%p;
if(a==0){
ll inv2=qpow(2,p-2,p);
ll x=b*inv2%p;ll y=(b-x+p)%p;
printf("%lld %lld\n",min(x,y),max(x,y));
continue;
}
ll res=solve(a,p);
if(res==-1){
printf("-1 -1\n");
continue;
}
ll inv2=qpow(2,p-2,p);
ll f=p-res;
ll x=(res+b+p)%p*inv2%p;
ll y=(b-x+p)%p;
printf("%lld %lld\n",min(x,y),max(x,y));
}
return 0;
}


## Knapsack Cryptosystem

64bit IO Format: %lld

## 题目描述

Amy asks Mr. B  problem D. Please help Mr. B to solve the following problem.

Amy wants to crack Merkle–Hellman knapsack cryptosystem. Please help it.

Given an array {ai} with length n, and the sum s. Please find a subset of {ai}, such that the sum of the subset is s.
For more details about Merkle–Hellman knapsack cryptosystem Please read https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem https://blog.nowcoder.net/n/66ec16042de7421ea87619a72683f807
Because of some reason, you might not be able to open Wikipedia.
Whether you read it or not, this problem is solvable.

## 输入描述:

The first line contains two integers, which are n(1 <= n <= 36) and s(0 <= s < 9 * 1018)The second line contains n integers, which are {ai}(0 < ai < 2 * 1017).{ai} is generated like in the Merkle–Hellman knapsack cryptosystem, so there exists a solution and the solution is unique.Also, according to the algorithm,  for any subset sum s, if there exists a solution, then the solution is unique.

## 输出描述:

Output a 01 sequence.If the i-th digit is 1, then ai is in the subset.If the i-th digit is 0, then ai is not in the subset.

## 输入

8 1129
295 592 301 14 28 353 120 236

## 输出

01100001

## 说明

This is the example in Wikipedia.

## 输入

36 68719476735
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 2147483648 4294967296 8589934592 17179869184 34359738368

## 输出

111111111111111111111111111111111111

#### 折半搜索模版题，签到

#include <bits/stdc++.h>
using namespace std;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand()%x;}
typedef long long ll;
int n;ll su;
ll a[40];
vector<ll> v;map<ll,string> mp;
vector<string> vv;
void gao(int pos,int lim,ll tmp,string s){
if(pos>lim){
v.push_back(tmp);
vv.push_back(s);
return;
}
gao(pos+1,lim,tmp,s+"0");
gao(pos+1,lim,tmp+a[pos],s+"1");
return;
}
void dfs(int pos,int lim,ll tmp,string s){
if(pos>lim){
mp[tmp]=s;
return;
}
dfs(pos+1,lim,tmp,s+"0");
dfs(pos+1,lim,tmp+a[pos],s+"1");
return;
}
int main(){
scanf("%d%lld",&n,&su);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
gao(1,n/2,0,"");
dfs(n/2+1,n,0,"");
int fg=0;
for(int i=0;i<(int)v.size();i++){
if(mp.count(su-v[i])){
cout<<vv[i]+mp[su-v[i]]<<'\n';
fg=1;
break;
}
}
return 0;
}


## All men are brothers

64bit IO Format: %lld

## 题目描述

Amy asks Mr. B  problem E. Please help Mr. B to solve the following problem.

There are n people, who don't know each other at the beginning. There are m turns. In each turn, 2 of them will make friends with each other. The friend relation is mutual and transitive.
If A is a friend of B, then B is also a friend of A.
For example, if A is a friend of B, B is a friend of C, then A and C are friends.
At the beginning and after each turn, please calculate the number of ways to select four people from, such that any two of these four are not friends.

## 输入描述:

The first line contains two integers, n and m (n <= 100000, m <= 200000), which are the number of people, and the number of turns.In the following m lines, the i-th line contains two integers x and y ( 1 <= x <= n, 1 <= y <= n, x ≠ y), which means the x-th person and the y-th person make friends in the i-th turn.The x-th person and y-th person might make friends in several turns.

## 输出描述:

Output m+1 lines, each line contains an integer, which is the number of quadruples.Output at the beginning and after each turn, so there are m+1 lines.

## 输入

6 6
1 2
3 4
4 5
3 5
3 6
2 4

## 输出

15
9
4
0
0
0
0


## 输入

100000 0

## 输出

4166416671249975000

## 说明

Don't use int.

#### 其实这道题的核心就是每次合并考虑减少了多少。减少的数量等于合并的两个集合大小相乘，再乘以从其他集合中选出2个不在一个集合内的方案数。从其他集合中选出2个不在一个集合内的方案数可以先计算任选2个的方案数，再减去来自同一个集合的方案数。

#include <bits/stdc++.h>
using namespace std;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand()%x;}
typedef long long ll;
int djs[100100],num[100100];
ll cal[100100];ll sc;
int fi(int x){
return x==djs[x]?x:djs[x]=fi(djs[x]);
}
void uni(int x,int y){
int fx=fi(x),fy=fi(y);
if(fx!=fy){
num[fx]+=num[fy];
djs[fy]=fx;
sc-=cal[fx]+cal[fy];
sc+=1ll*num[fx]*(num[fx]-1)/2;
cal[fx]=1ll*num[fx]*(num[fx]-1)/2;
}
return;
}
int f2=1,f3=1,f4=1;
void gao(ll& x){
if(x%4==0 && f4) x/=4,f4=0;
if(x%3==0 && f3) x/=3,f3=0;
if(x%2==0 && f2) x/=2,f2=0;
return;
}
int main(){
int n,m;sc=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) djs[i]=i,num[i]=1;
ll ans=1ll*n;gao(ans);ans*=1ll*(n-1);gao(ans);ans*=1ll*(n-2);gao(ans);ans*=1ll*(n-3);gao(ans);
printf("%lld\n",ans);
while(m--){
int a,b;
scanf("%d%d",&a,&b);
int fa=fi(a),fb=fi(b);
if(fa!=fb){
ans-=1ll*num[fa]*num[fb]*(1ll*(n-num[fa]-num[fb])*(n-num[fa]-num[fb]-1)/2-(sc-cal[fa]-cal[fb]));
uni(a,b);
}
printf("%lld\n",ans);
}
return 0;
}


## Cutting Bamboos

Special Judge, 64bit IO Format: %lld

## 题目描述

There are n bamboos arranged in a line. The i-th bamboo from the left has height hih_{i}hi​.

You are given q queries of the type (l, r, x, y). For each query (l, r, x, y) we consider only the l-th to r-th bamboo inclusive. We want to make y horizontal cuts through these bamboos, such that after each cut, the total length of bamboo cut is the same, and after all y cuts there is no bamboo left. For example, if there are 3 bamboos of height 3, 4, 5 respectively and y = 4. The first cut should be at height 3, after which the heights of the bamboos are 3, 3, 3 respectively and the total amount of bamboo cut is 0 + 1 + 2 = 3. Then, the next 3 cuts should be at height 2, 1, 0 respectively. You want to find out what is the height the x-th cut is performed.

Note that after each query, the bamboos are not actually cut, so the heights of the bamboos remain constant after each query.

## 输入描述:

The first line of input contains two space-separated integers n, q (1 <= n <= 200000, 1 <= q <= 100000).The next line of input contains n space-separated integers, the i-th of which denotes hi, the height of the i-th bamboo (1 <= hi <= 100000).The next q lines of input contains 4 space-separated integers each, denoting l, r, x, y (1 <= l <= r <= n, 1 <= x <= y <= 109).

## 输出描述:

Output q lines of real numbers, the i-th line contains the answer to the i-th query. Your answer will be accepted if its absolute or relative error is less than 10-6.

## 输入

5 4
3 5 1 7 4
2 4 3 5
1 4 4 9
1 3 1999 101111
2 2 1 1

## 输出

2.100000005215406
2.629629638046026
4.822066854685545
0.000000026077032

## 说明

For the first query, we only consider the bamboos of height 5, 1, 7.The first cut should be at height 4.7, the total amount of bamboo obtained is 0.3 + 0 + 2.3 = 2.6.The second cut should be at height 3.4, the total amount of bamboo obtained is 1.3 + 0 + 1.3 = 2.6.The third cut should be at height 2.1, the total amount of bamboo obtained is 1.3 + 0 + 1.3 = 2.6.The fourth cut should be at height 13/15, the total amount of bamboo obtained is 37/30 + 2/15 + 37/30 = 2.6.The fifth cut should be at height 0, the total amount of bamboo obtained is 13/15 + 13/15 + 13/15 = 2.6.Note that the output values are not exact, but are within the precision requirements.

#### 数组区间[l, r]内所有数字和t取最小值然后求和，这个问题可以用可持久化线段树解决，然后每次询问再做一个二分就可以了，主席树模版题

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
#define delf int mid=(l+r)>>1
typedef long long ll;
const int maxn=2e5+5;
int a[maxn],n,q,lim;ll pre[maxn];
struct tree{int l,r,num;ll sum;}tree[maxn*80];
int rt[maxn],sz;
void update(int l,int r,int &x,int y,int n){
tree[x=(++sz)]=tree[y];
if(l==r){++tree[sz].num,tree[sz].sum+=l;return;}
delf;
if(n<=mid) update(l,mid,tree[x].l,tree[y].l,n);
else update(mid+1,r,tree[x].r,tree[y].r,n);
tree[x].num=tree[tree[x].l].num+tree[tree[x].r].num;
tree[x].sum=tree[tree[x].l].sum+tree[tree[x].r].sum;
}
int qnum(int cl,int cr,int l,int r,int x,int y){
if(cl<=l&&r<=cr) return tree[y].num-tree[x].num;
delf;int ans=0;
if(cl<=mid) ans+=qnum(cl,cr,l,mid,tree[x].l,tree[y].l);
if(cr>mid) ans+=qnum(cl,cr,mid+1,r,tree[x].r,tree[y].r);
return ans;
}
ll qsum(int cl,int cr,int l,int r,int x,int y){
if(cr<cl) return 0;
if(cl<=l&&r<=cr) return tree[y].sum-tree[x].sum;
delf;
ll ans=0;
if(cl<=mid) ans+=qsum(cl,cr,l,mid,tree[x].l,tree[y].l);
if(cr>mid) ans+=qsum(cl,cr,mid+1,r,tree[x].r,tree[y].r);
return ans;
}
void solve(){
scanf("%d%d",&n,&q);lim=0;sz=0;
rep(i,1,n) scanf("%d",&a[i]),pre[i]=pre[i-1]+a[i],lim=max(lim,a[i]);
rep(i,1,n) update(1,lim,rt[i],rt[i-1],a[i]);
while(q--){
int l,r,x,y;scanf("%d%d%d%d",&l,&r,&x,&y);
double cnt=(double)(pre[r]-pre[l-1])/y*(y-x); //需要的总和
int L=0,R=lim-1,mid=0;
while(L<=R){
mid=(L+R)>>1;
ll sum=qsum(1,mid,1,lim,rt[l-1],rt[r]);
int num=qnum(mid+1,lim,1,lim,rt[l-1],rt[r]);
if((double)(sum+(ll)num*(mid+1))<cnt) L=mid+1;
else if((double)(sum+(ll)num*mid)>cnt) R=mid-1;
else{
printf("%.15f\n",(double)(cnt-sum)/num);
break;
}
}
}
}
int main(){
solve();
}


## Symmetrical Painting

64bit IO Format: %lld

## 题目描述

Initially, the entire coordinate plane is colored white. N rectangles were painted black. The i-th rectangle has bottom-left corner (i−1,Li)(i-1, L_i)(i−1,Li​)and top-right corner (i,Ri)(i,R_i)(i,Ri​) for 1≤i≤n1 \le i \le n1≤i≤n. You want to paint some of the black area white so that the remaining black part has a horizontal axis of symmetry. Find the maximum possible area of the remaining black part.

## 输入描述:

The first line of input contains a single integer N (1 <= N <= 300000), denoting the number of rectangles.The next N lines of input contain two space-separated integers each, denoting Li, Ri (1 <= Li < Ri <= 109).

## 输出描述:

Output a single integer, the answer to the problem.

## 输入

3
1 5
4 7
2 3

## 输出

4

## 说明

It is optimal to paint second rectangle entirely white and a rectangle with bottom-left corner (0, 4) and top-right corner (1, 5) white. Then, the remaining black figure has axis of symmetry at y = 2.5. The remaining black area is 4.

#### 最优解的斜率只会在L2, L+R,2变化预处理出来这些位置，排序，求分段函数最小值就可以了。

#include <bits/stdc++.h>
using namespace std;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand()%x;}
typedef long long ll;
struct node{
ll a,b;
bool operator < (const node& y){
return a<y.a;
}
};
node a[1001000];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
ll x,y;
scanf("%lld%lld",&x,&y);
a[i*3-2]=(node){x*2,1};
a[i*3-1]=(node){x+y,-2};
a[i*3]=(node){y*2,1};
}
sort(a+1,a+3*n+1);
ll cnt=0,pre=0;ll rk=0;
ll ans=0;
for(int i=1;i<=3*n;i++){
cnt+=(a[i].a-pre)*rk;
ans=max(ans,cnt);
rk+=a[i].b;
pre=a[i].a;
}
printf("%lld\n",ans);
return 0;
}


0 评论