问题虫洞——A：https://ac.nowcoder.com/acm/contest/889/A
黑洞内窥：
即求斐波那契各项的m次幂的和mod10^9的结果
思维光年：
大佬的做法：
将10^9 拆解为 2^9 和 5^9, 然后可以分别求出Fibonacci在2^9和5^9下的循环节为768 和 7812500
设Ai 为 
%2^9的前缀和数组，，设Bi为%5^9的前缀和数组，设C = 
%10^9,
而我们可以预处理出Ai，和Bi， 然后用CRT(中国剩余定理)合并一下：
题解的做法：
ACcode：
//#include<bits/stdc++.h>
#include <stdio.h>
#include <iostream>
#include<algorithm>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <stdlib.h>
#include <cstring>
#include <string.h>
#include <string>
#include <math.h>
#include <sstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MAXN 50000000
#define INF 0x3f3f3f3f//将近ll类型最大数的一半，而且乘2不会爆ll
const ll mod = 1000000007;
const double eps = 0.0000001;
const double pi = acos(-1);
ll f[MAXN];
ll ans1, ans2, n, m;
ll qpow(ll a, ll b, ll m)
{
ll ans = 1;
while(b)
{
if(b&1)
ans = a*ans%m;
a = a*a%m;
b >>= 1;
}
return ans;
}
///Fibonacci % 2^9的循环节为768
///Fibonacci % 5^9的循环节为7812500
ll solve(int p)
{
f[0]=0, f[1]=1;
ll tot=1, ans=0;
do
{
++tot;
f[tot] = (f[tot-1] + f[tot-2])%p;
}while(f[tot]!=0 || f[tot-1]!=1); ///求循环节
for(int i=0; i<tot; ++i)
{
int k = n/tot;
if(n%tot >= i)
++k;
ans = (ans+qpow(f[i], m, p)*k)%p;
}
return ans;
}
int main()
{
cin >> n >> m;
ans1 = solve(512); //2^9;
ans2 = solve(1953125);//5^9
while(ans1%1953125 != ans2)
ans1+=512;
cout << ans1 << '\n';
return 0;
}
问题虫洞——B：https://ac.nowcoder.com/acm/contest/889/B
黑洞内窥：
p = 1000000007
Given two integers b and c, please find two integers x and y(0≤x≤y<p), such that
(x+y)%p=b
(x×y)%p=c
给出上面的组合式，并给出取模后的结果b和c，
求一组解（x， y）
思维光年：
唯一少的一点就是中间那个知识点，不过，即使不用中间那个知识点，自己枚举
应该也可以求解，，，
ACcode：
#include<stdio.h>
#include<iostream>
#include<map>
#include<algorithm>
#include<cstring>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
#define MAXN 1000005
#define INF 0x3f3f3f3f//将近int类型最大数的一半，而且乘2不会爆int
#define MOD 1000000007 // MOD%4 = 3
ll qpow(ll a, ll b)
{
ll ans = 1;
while(b)
{
if(b&1)
ans = ans*a%MOD;
a = a*a%MOD;
b >>= 1;
}
return ans;
}
int main()
{
ll t, x, y, b, c;
cin >> t;
while(t--)
{
scanf("%lld %lld", &b, &c);
ll ans = (b*b - 4*c +MOD)%MOD;
ll a = qpow(ans, (MOD+1)/4);
if((ll)a*a%MOD != ans) //不能二次剩余，即无整数解
puts("-1 -1");
else
{
x = (b+a)*(MOD+1)/2%MOD; //乘(MOD+!)是为了防止/2溢出
y = (b-x+MOD)%MOD;
if(x>y) swap(x, y);
cout << x << ' ' << y << '\n';
}
}
return 0;
}
问题虫洞——E：https://ac.nowcoder.com/acm/contest/889/E
黑洞内窥：
一开始有N个人不认识。有M次机会吧，他们中的两个轮流交朋友。
朋友关系是相互的、可传递的。
如果A是B的朋友，那么B也是A的朋友。
例如，如果A是B的朋友，B是C的朋友，那么A和C是朋友。
在开始和每个回合之后，请计算从中选择四个人的方法的数量，这样这四个人中的任何两个都不是朋友。
朋友关系是相互的、可传递的。
如果A是B的朋友，那么B也是A的朋友。
例如，如果A是B的朋友，B是C的朋友，那么A和C是朋友。
在开始和每个回合之后，请计算从中选择四个人的方法的数量，这样这四个人中的任何两个都不是朋友。
思维光年：
题解很简单，我感觉好像在哪里做过这种题。。。。。
我不知道为什么，压缩版的tofind和递归版的tofind的速度是相同的，而你用普通的tofind就会T，。，，，
ACcode：
//#include<bits/stdc++.h>
#include <stdio.h>
#include <iostream>
#include<algorithm>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <stdlib.h>
#include <cstring>
#include <string.h>
#include <string>
#include <math.h>
#include <sstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//typedef using long long ull;
#define MAXN 200005
#define INF 0x3f3f3f3f//将近ll类型最大数的一半，而且乘2不会爆ll
const ll mod = 1000000007;
const double eps = 0.0000001;
const double pi = acos(-1);
int pre[MAXN];
ull s[MAXN];
//int tofind(int x){return pre[x]!=x?pre[x]=tofind(pre[x]):x;}
int tofind(int x)
{
int r = x;
while(r != pre[r])
r = pre[r];
int i=x, j;
while(i!=r)
{
j = pre[i];
pre[i] = r;
i = j;
}
return r;
}
int main()
{
int n, m, a, b;
ull c=0, c1=0, c2=0;
scanf("%d %d", &n, &m);
c = (ull)n*(n-1)/2*(n-2)/3*(n-3)/4; //总方案数
cout << c << '\n';
for(int i=1; i<=n; ++i)
{
pre[i] = i;
s[i] = 1;
c1+=s[i];
c2+=s[i]*s[i];
}
for(int i=0; i<m; ++i)
{
scanf("%d %d", &a, &b);
int fx = tofind(a);
int fy = tofind(b);
if(fx != fy)
{
c1-=s[fx]+s[fy];
c2-=s[fx]*s[fx]+s[fy]*s[fy];
c-=(c1*c1 - c2)/2 * s[fx]*s[fy];
s[fy]+=s[fx]; //合并集合数量
c1+=s[fy];
c2+=s[fy]*s[fy];
pre[fx] = fy;
}
cout << c << '\n';
}
return 0;
}
问题虫洞——J：https://ac.nowcoder.com/acm/contest/889#question
黑洞内窥：
最初，整个坐标平面为白色。n个长方形被漆成黑色。
第i个矩形的左下角（i-1，li）和右上角（i，ri）表示1≤i≤n。
要将一些黑***域漆成白色，以便剩余的黑色部分具有水平对称轴。
找到剩余黑色部分的最大可能区域。
思维光年：
然而这个过程我仍然模拟不出来。。。。
ACcode：
#include<stdio.h>
#include<iostream>
#include<map>
#include<algorithm>
#include<cstring>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
#define MAXN 1000005
#define INF 0x3f3f3f3f//将近int类型最大数的一半，而且乘2不会爆int
#define MOD 1000000000
struct node
{
ll x, y;
}stu[MAXN];
int cmp(node a, node b) {return a.x < b.x;}
int main()
{
int t, tot=0;
ll l, r;
cin >> t;
while(t--)
{
scanf("%lld %lld", &l, &r);
l<<=1, r<<=1;
stu[++tot] = {l, 1};
stu[++tot] = {(l+r)>>1, -2};
stu[++tot] = {r, 1};
}
sort(stu+1, stu+tot+1, cmp);//按点的大小排序
ll ans=0, p=0, q=0, tem=0; //这里有点迷~~~
for(int i=1; i<tot; ++i)
{
p += stu[i].y;
q = stu[i+1].x - stu[i].x;
tem += p*q;
ans = max(ans, tem);
}
cout << ans << '\n';
return 0;
}
京公网安备 11010502036488号