The power of Fibonacci
时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
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.
示例1
输入
5 5
输出
3402
说明
05 + 15 + 15 + 25 + 35 + 55 = 3402
示例2
输入
10 10
输出
696237975
说明
Don't forget to mod 1000000000
示例3
输入
1000000000 1000
输出
641796875
说明
Time is precious.
F[i] – F[i-1] – F[i-2] = 0
F[i]^2 – 2 F[i-1]^2 – 2 F[i-2]^2 + F[i-3] = 0
F[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;
}
Quadratic equation
时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
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
示例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
时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
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.
示例1
输入
8 1129 295 592 301 14 28 353 120 236
输出
01100001
说明
This is the example in Wikipedia.
示例2
输入
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
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
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.
示例1
输入
6 6 1 2 3 4 4 5 3 5 3 6 2 4
输出
15 9 4 0 0 0 0
示例2
输入
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
时间限制：C/C++ 5秒，其他语言10秒
空间限制：C/C++ 262144K，其他语言524288K
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.
示例1
输入
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
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
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.
示例1
输入
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;
}
