# 2019 牛客多校第九场

## The power of Fibonacci

64bit IO Format: %lld

## 题目描述

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

## 题目描述

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

## 题目描述

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.
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

## 题目描述

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 评论