| Solved | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|
| 7/10 | Ø | O | . | O | O | . | . | O | Ø | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
题目来源：2019牛客暑期多校训练营第九场
A
题目描述
设斐波那契数列为$f[i]$，求$\sum_{i=1}^{n}f[i]^m% 10^9$。
解题思路
求出$\sum_{i=1}^{n}f[i]^m% 2^9,\sum_{i=1}^{n}f[i]^m% 5^9$的循环节，乘出来再中国剩余定理合并即可。
AC代码 - by qxforever
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
using namespace std;
typedef long long ll;
const int maxn = 5e7;
const int mod1 = pow(2,9);
const int mod2 = pow(5,9);
const int len1=768;
const int len2=7812500;
int f1[len1+3],f2[len2+3];
int g1[len1+3],g2[len2+3];
ll n,ans1,ans2;int m;
int qpow(int a,int b,int mod)
{
int ans=1;
int base=a;
while(b!=0){
if(b&1) ans=(1LL*ans*base)%mod;
base=(1LL*base*base)%mod;
b>>=1;
}
return ans;
}
void getf()
{
f[0]=0,f[1]=1;g1[1]=1;
for(int i=2;i<=len1;i++){
f[i]=f[i-1]+f[i-2];if(f[i]>=mod1) f[i]-=mod1;
g1[i]=qpow(f[i],m,mod1)+g1[i-1];
if(g1[i]>=mod1) g1[i]-=mod1;
}
f[0]=0,f[1]=1;g2[1]=1;
for(int i=2;i<=len2;i++){
f[i]=f[i-1]+f[i-2];if(f[i]>=mod2) f[i]-=mod2;
g2[i]=g2[i-1]+qpow(f[i],m,mod2);
if(g2[i]>=mod2) g2[i]-=mod2;
}
}
void calc(ll tmp1,ll tmp2)
{
ll d;
d=n/len1;ans1+=(d%mod1)*tmp1%mod1;
d=n/len2;ans2+=(d%mod2)*tmp2%mod2;
d=n%len1;
//printf("%lld\n",ans1);
ans1+=g1[d];if(ans1>=mod1) ans1-=mod1;
d=n%len2;
ans2+=g2[d];if(ans2>=mod2) ans2-=mod2;
}
int exgcd(int a,int b,int &x,int &y)
{
if(b==0){
x=1,y=0;
return a;
}
int gcd=exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
return gcd;
}
int china()
{
int w[]={512,1953125},b[]={ans1,ans2},k=2;
int x,y,a,m,n;
a=0,n=1000000000;
for(int i=0;i<k;i++){
m=n/w[i];
exgcd(w[i],m,x,y);
a=(1LL*a+1LL*y*m*b[i])%n;
}
return a>0 ? a : a+n;
}
int main()
{
cin >> n >> m;
getf();
int tmp1=0,tmp2=0;
tmp1=g1[len1-1];
tmp2=g2[len2-1];
calc(tmp1,tmp2);
//printf("%lld %lld\n",tmp1,tmp2);
printf("%d\n",china());
}
B
题目描述
$(x+y)\space mod \space p=b$
$(x\times y)\space mod \space p=c$
求$x,y$。
解题思路
很容易化成一个二次剩余的式子。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
typedef long long ll;
template<class T>il T read(){
rg T data=0,w=1;
rg char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') w=-1;
ch=getchar();
}
while(isdigit(ch))
data=data*10+ch-'0',ch=getchar();
return data*w;
}
template<class T>il T read(rg T&x){
return x=read<T>();
}
ll b,c,n,mod=1000000007;
ll add(ll x,ll y){
return (x+y)%mod;
}
ll mul(ll x,ll y){
return x*y%mod;
}
ll pow(ll x,ll k){
x%=mod,k%=(mod-1);
ll re=1;
for(;k;k>>=1,x=mul(x,x))
if(k&1) re=mul(re,x);
return re;
}
ll omega;
struct complex{ll a,b;};
complex operator*(co complex&x,co complex&y){
return (complex){add(mul(x.a,y.a),mul(x.b,mul(y.b,omega))),add(mul(x.a,y.b),mul(x.b,y.a))};
}
complex operator^(complex x,ll k){
complex re=(complex){1,0};
for(;k;k>>=1,x=x*x)
if(k&1) re=re*x;
return re;
}
ll sqrt(ll n){
n%=mod;
if(!n) return 0;
ll a=rand()%mod;
while(pow(add(mul(a,a),mod-n),(mod-1)/2)!=mod-1) a=rand()%mod;
omega=add(mul(a,a),mod-n);
return ((complex){a,1}^(mod+1)/2).a;
}
int main(){
int kase=read<int>();
while(kase--){
read(b);read(c);
n=(b*b-4*c%mod+mod)%mod;
if(!n){
ll tmp=b;
if(b%2)b+=mod;
printf("%lld %lld\n",b/2,b/2);
continue;
}
if(pow(n,(mod-1)/2)!=1){puts("-1 -1");continue;}
ll ans1=sqrt(n),ans2=mod-ans1;
if(ans1>ans2) std::swap(ans1,ans2);
ll tmp=b+ans1;
if(tmp%2)ans1+=mod;
tmp=ans1+b;
ll x=tmp/2%mod;
ll y=(b-ans1)/2%mod;
if(y<0)y+=mod;
if(x>y)std::swap(x,y);
printf("%lld %lld\n",x,y);
}
return 0;
}
C
题目描述
解题思路
AC代码
2
D
题目描述
从$n$个元素中选，问能否组成$s$。
解题思路
中途相遇法板子题。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
typedef long long ll;
using namespace std;
ll a[40],sum[(1<<18)+10];
map<ll,int>mp;
int main(){
int i,j,n;
ll s;
scanf("%d%lld",&n,&s);
for(i=0;i<n;i++)scanf("%lld",&a[i]);
for(i=0;i<(1<<(n/2));i++){
ll tmp=0;
for(j=0;j<n/2;j++)if(i&(1<<j))tmp+=a[j];
mp[s-tmp]=i;
}
ll left,right;
for(i=0;i<(1<<(n-n/2));i++){
ll tmp=0;
for(j=n/2;j<n;j++)if(i&(1<<(j-n/2)))tmp+=a[j];
if(mp.count(tmp)!=0){
left=mp[tmp];
right=i;
break;
}
}
for(i=0;i<n/2;i++){
if(left&(1<<i))printf("1");
else printf("0");
}
for(i=0;i<(n-n/2);i++){
if(right&(1<<i))printf("1");
else printf("0");
}
return 0;
}
E
题目描述
问从$n$个人中选择$4$个互不认识的人的方法数，有$m$次操作每次添加一条边$u,v$，使得$u$的朋友和$v$的朋友互相认识。
解题思路
并查集，分别维护两个人、四个人的种数即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
using namespace std;
typedef unsigned long long ull;
int T;
const int maxn = 1e5+23;
int f[maxn];
ull sz[maxn];
int n,m;
int find(int x)
{
return x==f[x] ? x : f[x]=find(f[x]);
}
void init()
{
for(int i=0;i<=n;i++) f[i]=i;
for(int i=1;i<=n;i++) sz[i]=1;
}
int main()
{
cin >> n >> m ;
init();
ull ans=0,last=0;
ans=(ull)n*(n-1)/2*(n-2)/3*(n-3)/4;
last=(ull)n*(n-1)/2;
printf("%llu\n",ans);
for(int i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
int x=find(u),y=find(v);
if(x!=y){
ull t=n-sz[x]-sz[y];
ans=ans-sz[x]*sz[y]*(last-sz[x]*sz[y]-sz[x]*t-sz[y]*t);
last-=sz[x]*sz[y];
f[x]=y;
sz[y]+=sz[x];
}
printf("%llu\n",ans);
}
}
F
题目描述
解题思路
AC代码
2
G
题目描述
解题思路
AC代码
2
H
题目描述
砍树，区间砍$y$次，问第$x$次砍到多高。
解题思路
主席树
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
using namespace std;
typedef long long ll;
const int N=800010;
int a[N],b[N];
int n,m,tot;
int root[N],L[N<<3],R[N<<3];
ll sum[N<<3],cnt[N<<3];
int size;
int build(int l,int r){
int now=++tot;
if(l<r){
L[now]=build(l,mid);
R[now]=build(mid+1,r);
}
return now;
}
int update(int root,int l,int r,int x){
int now=++tot;
L[now]=L[root];
R[now]=R[root];
cnt[now]=cnt[root]+1;
if(l<r){
if(x<=mid)L[now]=update(L[root],l,mid,x);
else R[now]=update(R[root],mid+1,r,x);
sum[now]=sum[L[now]]+sum[R[now]];
cnt[now]=cnt[L[now]]+cnt[R[now]];
}else{
sum[now]=sum[root]+b[l];
}
return now;
}
double query(int lt,int rt,int l,int r,double x,double rightremain,double leftsum){
if(l>=r){
rightremain+=cnt[rt]-cnt[lt];
return (x-leftsum)/rightremain;
}
ll t=leftsum+rightremain*b[mid];//左区间最靠右的
t+=cnt[R[rt]]*b[mid]+sum[L[rt]];
t-=cnt[R[lt]]*b[mid]+sum[L[lt]];
if(t>=x)return query(L[lt],L[rt],l,mid,x,rightremain+cnt[R[rt]]-cnt[R[lt]],leftsum);
return query(R[lt],R[rt],mid+1,r,x,rightremain,leftsum+sum[L[rt]]-sum[L[lt]]);
}
double solve(int l,int r,int x,int y){
double s=sum[root[r]]-sum[root[l-1]];
double remain=s-s/y*x;
double res=query(root[l-1],root[r],1,size,remain,0,0);
return res;
}
int main(){
int i,x,y,z;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
sort(b+1,b+1+n);
size=unique(b+1,b+1+n)-b-1;
root[0]=build(1,size);
for(i=1;i<=n;i++)root[i]=update(root[i-1],1,size,lower_bound(b+1,b+1+size,a[i])-b);
while(m--){
int l,r,x,y;
scanf("%d%d%d%d",&l,&r,&x,&y);
printf("%.8f\n",solve(l,r,x,y));
}
return 0;
}
I
题目描述
求$\sum_{k=1}^n(kM)\ &M$。
解题思路
对于$M$二进制的每一位$j$，对答案的贡献显然为$2^{\sum_{i=1}^{n}\frac {i\times M}{2^j}-\frac{i\times M}{2^{j+1}}\times 2}$，这可以用类欧几里得算法算出。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef long long ll;
using namespace std;
ll mod=1000000007;
__int128 f(__int128 a,__int128 b,__int128 c,__int128 n){
__int128 m=(a*n+b)/c;
if(!m||!a)return 0;
if(a>=c||b>=c)return (n*(n+1)/2%mod*(a/c)%mod+(b/c)*(n+1)%mod+f(a%c,b%c,c,n))%mod;
else return (m*n%mod-f(c,c-b-1,a,m-1)+mod)%mod;
}
int main(){
int i;
ll n,m,ans=0;
scanf("%lld%lld",&n,&m);
for(i=0;i<60;i++)
if((1LL<<i)&m)
(ans+=(((f(m,0,1ll<<i,n)-f(m,0,1ll<<(i+1),n)*2%mod+mod)%mod)<<i)%mod)%=mod;
printf("%lld",ans);
return 0;
}
J
题目描述
有一堆矩形，找到某条线，每个矩形贡献为关于这条线对称的面积，求最大答案。
解题思路
就三种情况，离散化之后算一算就行。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
using namespace std;
typedef long long ll;
const int maxn = 3e5+23;
struct E
{
unsigned int s;
bool si;
};
E e[maxn*3];
bool cmp(E a,E b)
{
return a.s<b.s;
}
int n;
int cnt=0;
int main()
{
cin >> n ;
for(int i=0;i<n;i++){
scanf("%u%u",&e[cnt].s,&e[cnt+1].s);
e[cnt].s*=2;
e[cnt+1].s*=2;
e[cnt+2].s=(e[cnt].s+e[cnt+1].s)/2;
e[cnt].si=true,e[cnt+1].si=true,e[cnt+2].si=false;
cnt+=3;
}
sort(e,e+cnt,cmp);
int now=0;ll ans=0,mx=0;
if(e[0].si) now=1;
for(int i=1;i<cnt;i++){
//printf("? %d %lld\n",now,ans);
ans+=(1LL*now*(e[i].s-e[i-1].s));
mx=max(ans,mx);
if(e[i].si) now+=1;
else now-=2;
}
cout << mx ;
}