【清北学堂国庆刷题班】Day6

T1 math

题目描述

请求出
gcd(qa−1,qb−1) gcd(q^a-1,q^b-1)
模p的结果。

输入格式

第一行一个整数T，表示数据组数。

接下来T行，每行四个整数q,a,b,p。

输出格式

T行，每行一个整数表示答案。

样例输入

1
2
1
3 1 2 11

样例输出

1
2

数据范围

对于30%的数据，a,b≤500,T≤100

对于另外30%的数据，p为素数

对于所有数据，满足1<=q,a,b,p<=109,T<=104,q>11<=q,a,b,p<=10^9,T<=10^4,q>1

思路

式子变形

gcd(qa−1,qb−1)=gcd(qb−1,qa−1−qb+1)=gcd(qb−1,qa−qb) gcd(q^a-1,q^b-1) =gcd(q^b-1,q^a-1-q^b+1) =gcd(q^b-1,q^a-q^b)

=gcd(qb−1,qb(qa−b−1)) =gcd(q^b-1,q^b(q^{a-b}-1))

不难看出是这个实质上是对于指数的更相减损法

因此
gcd(qa−1,qb−1)=qgcd(a−b)−1 gcd(q^a-1,q^b-1)=q^{gcd(a-b)}-1
再用一个位运算的快速幂加速就好了

代码

1
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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#define re register
#define ll long long
using namespace std;
int T;
ll qpow(ll a,ll b,ll p)
{
	ll ans=1%p;
	for( ;b;b>>=1)
	{
		if(b&1) ans=(ll)ans*a%p;
		a=(ll)a*a%p;
	}
	return ans;
}
ll gcd(ll a,ll b)
{
	return b? gcd(b,a%b):a;
}
int main()
{
	//freopen("data.in","r",stdin);
	//freopen("math.out","w",stdout);
	cin>>T;
	while(T--)
	{
		ll q,a,b,p;
		cin>>q>>a>>b>>p;
		cout<<(qpow(q,gcd(a,b),p)-1+p)%p<<endl;
	}
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

T2 candy

题目描述

有nn袋糖果，第ii袋糖果有B**iBi颗糖。

小Y想吃糖，共有mm天，每天她会拿走糖果数(即B**jBj)是A**iAi的倍数的一袋糖果，满足B**jBj最小。

当然如果B**jBj不存在，她就没得吃了，因此她会很生气，从此不再吃糖，游戏也就结束了。

你可以帮小Y算出她能吃几天，以及每天吃了几颗吗？

输入格式

第一行，一个整数n。接下来一个n个整数BiB_i。

下一行，一个整数m。接下来一个m个整数AiA_i

输出格式

第一行一个整数k表示天数。

接下来一行k个整数，表示前k天每天吃的糖果数量。

样例输入

1
2
3
4
4
1 6 8 16
4
4 2 4 5

样例输出

1
2
3
8 6 16

数据范围

对于30%的数据，Ai<=10A_i<=10

对于另外30%的数据，n,m<=5000n,m<=5000

对于所有数据，1<=n,m,Ai,Bi<=1061<=n,m,A_i,B_i<=10^6

思路

目前不知道但是老师是这么讲的

“直接模拟就是平方的算法，随便加点剪枝说不定能过2333，标算是一个当前弧优化的思想，对于一个 ，它找到的 是单调的，所以不需要重新扫描，这样复杂度是调和级数的O(nlogn)O(nlogn) ”

代码

1
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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
#define pb push_back
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,b) for (int i=a; i<=b; i++)
#define per(i,a,b) for (int i=a; i>=b; i--)
#define L(i,u) for (int i=head[u]; i!=0; i=edge[i].nxt)
#define abs(a) ((a)>0 ? (a) : -(a))
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int> Pii;
typedef long long ll;
const int N = 1000005;
int n,m,cnt[N],cur[N],ans[N];
inline void read(int &x) {
	x=0; char c=getchar(); int f=1;
	while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();}
	while (c>='0'&&c<='9') {x=10*x+c-'0'; c=getchar();} x*=f;
}
inline void print(int n) {
	printf("%d\n",n);
	rep(i,1,n) printf("%d ",ans[i]);
}
int main() {
	read(n);
	rep(i,1,n){int x;read(x);cnt[x]++;}
	read(m);
	rep(i,1,m) {
		int x; read(x);
		int p=cur[x];
		while (p<=1e6&&!cnt[p]) p+=x;
		if (p>1e6) {print(i-1);return 0;}
		cnt[p]--; cur[x]=p; ans[i]=p;
	}
	print(m);
	return 0;
}

T3 lagrange

题目描述

你可能会很好奇题目名称有什么含义。不管怎样，考试结束之前，我是不会告诉你的。

你有2个长为n的序列，需要支持2种操作，总共进行次

  • 查询区间∑l≤i<j≤r(AiBj−AjBi)2\sum_{l\leq i<j\leq r}(A_iB_j-A_jB_i)^2的值，对998244353取模。
  • 修改(Ai,Bi)(A_i,B_i)为(x,y)(x,y)

输入格式

第一行两个整数n,q

接下来一行n个整数AiA_i

接下来一行n个整数BiB_i

接下来q行描述操作，操作有两种：

1 l r 为操作1

2 i x y 为操作2

输出格式

对于每次操作1，一行一个整数表示答案。

样例输入

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

样例输出

1
2
96
362

数据范围

对于20%的数据，n,q≤200

对于40%的数据，n,q≤2000

对于另外30%3的数据，只有操作1。

对于所有数据n,q≤500000,1≤Ai,Bi,x,y≤109n,q\leq 500000,1\leq A_i,B_i,x,y\leq 10^9，满足，其中x,y为操作2的参数。

思路

(∑ai2)(∑bi2)=(∑aibi)2+∑1≤i<j≤n(aibj−ajbi)2 (\sum a_i^2)(\sum b_i^2)=(\sum a_ib_i)^2+\sum_{1\leq i<j\le n}(a_ib_j-a_jb_i)^2

这是拉格朗日恒等式，分三个部分用树状数组维护就好了

代码

1
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
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> T gcd(T a, T b){return !b?a:gcd(b,a%b);}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 1e6+11,mo=998244353;
int n,q,a[N],b[N],v[3][N];
int Sqr(int x){return 1ll*x*x%mo;}
inline void add(int &x, int y){x=x+y<mo?x+y:x+y-mo;}
inline void mdy(int *a, int p, int x){x=(x+mo)%mo;while(p<=n)add(a[p],x),p+=p&-p;}
inline int qry(int *a, int p){int r=0;while(p)add(r,a[p]),p-=p&-p;return r;}
inline int qry(int *a, int l, int r){return qry(a,r)-qry(a,l-1);}
int main() {
	read(n);read(q);
	rep(i,1,n)read(a[i]);
	rep(i,1,n)read(b[i]);
	rep(i,1,n)mdy(v[0],i,1ll*a[i]*a[i]%mo),mdy(v[1],i,1ll*b[i]*b[i]%mo),mdy(v[2],i,1ll*a[i]*b[i]%mo);
	while(q--){
		int op;read(op);
		if(op==1){
			int l,r;read(l);read(r);
			int res=((1ll*qry(v[0],l,r)*qry(v[1],l,r)-Sqr(qry(v[2],l,r)))%mo+mo)%mo;
			printf("%d\n",res);
		}
		else{
			int i,x,y;read(i);read(x);read(y);
			mdy(v[0],i,(1ll*x*x-1ll*a[i]*a[i])%mo),
			mdy(v[1],i,(1ll*y*y-1ll*b[i]*b[i])%mo),
			mdy(v[2],i,(1ll*x*y-1ll*a[i]*b[i])%mo);
			a[i]=x;b[i]=y;
		}
	}
	return 0;
}

T4 loop

题目描述

你有m个集合Pi,QiP_i,Q_i，满足∀j ∈Pi∪Qi,j<i\forall j\ \in P_i\cup Q_i,j<i

现在你有一个m重循环，记第ii重循环的变量为xix_i，则xix_i从max(xpi)max(x_{p_i}) 到min(xQi)min(x_{Q_i})特别地，P为空集则max(xPi)=1max(x_{P_i})=1，Q为空集则min(xQi)=nmin(x_{Q_i})=n（什么意思呢？就是说∀j∈Pi,xi>xj\forall j \in P_i ,x_i>x_j，集合Q的意义同理可知）

你需要求出循环最内层里面的语句执行的次数，对p取模的结果。

输入格式

第一行三个正整数m,n,p

接下来m行，每行输入了两个集合，每个集合的格式为：先输入一个数l表示集合大小，接下来输入l个元素。

输出格式

一行一个整数表示答案。

样例输入

1
2
3
2 10 13
0 0
1 1 0

样例输出

1
3

数据范围

对于10%的数据，m≤6,n≤10

对于30%的数据，m≤8

对于另外30%的数据，∣Pi∣,∣Qi∣≤1|P_i|,|Q_i|\le 1

对于所有数据，满足m≤15,n,p≤109m\le 15,n,p\le 10^9，且Pi,QiP_i,Q_i中所有元素在[1,i−1][1,i-1]中

思路

我们只关心这m个变量的相对大小关系。
状压，从小到大加入值相同的一些数，同时可以判定是否合法。
dpi,sdp_{i,s}表示目前从小到大加入了 种不同的数值，填了集合 的方案数。
dp结束后用组合数算答案即可。
复杂度 O(n3n)O(n3^n)

代码

1
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
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> T gcd(T a, T b){return !b?a:gcd(b,a%b);}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 1<<15|3;
int zuo[N],you[N],n,m,all,dp[N][17],mo;
void Get(int &res){int l,x;read(l);while(l--)read(x),res|=1<<x-1;}
inline void add(int &x, int y){x=x+y<mo?x+y:x+y-mo;}
int main() {
	read(n);read(m);read(mo);all=(1<<n)-1;
	rep(i,1,n)Get(zuo[1<<i-1]),Get(you[1<<i-1]);
	rep(s,0,all)rep(i,1,n)if(s>>i-1&1)zuo[s]|=zuo[1<<i-1],you[s]|=you[1<<i-1];
	dp[0][0]=1;
	rep(s,1,all)for(int t=(s-1)&s;;t=(t-1)&s){
		if((zuo[s^t]&s)==zuo[s^t]&&(you[s^t]&t)==0)
			rep(i,0,n-1)add(dp[s][i+1],dp[t][i]);
		if(!t)break;
	}
//	rep(s,0,all)rep(i,0,n)if(dp[s][i])printf("%d %d:%d\n",s,i,dp[s][i]);
	int res=0,cur=1;
	static int sta[233];int sz=0;
	rep(i,0,n){
		cur=1;rep(j,1,sz)cur=1ll*cur*sta[j]%mo;
		add(res,1ll*dp[all][i]*cur%mo);
		sta[++sz]=m-i;
		int tmp=i+1;rep(j,1,sz){int g=gcd(tmp,sta[j]);tmp/=g;sta[j]/=g;}
		assert(tmp==1);
	//	cur=1ll*cur*(m-i)%mo*inv[i+1]%mo;
	}
	cout<<res<<endl;
	return 0;
}