tqyaaaaang's Blog

Anniversary Cup #1 Day 1(LibreOJ Round #9)

Anniversary Cup #1 Day 1(LibreOJ Round #9)

A. ZQC 的迷宫 ( LOJ 559 )

题目链接:https://loj.ac/problem/559

常识题,不说了,沿着墙一定能走出迷宫

代码

#include <bits/stdc++.h>
using namespace std;

#define LL long long
#define LD long double
#define SC(t,x) static_cast<t>(x)
#define AR(t) vector < t >
#define PII pair < int, int >
#define PLL pair < LL, LL >
#define PIL pair < int, LL >
#define PLI pair < LL, int >
#define PQ priority_queue
#define GT(type) greater < type >
#define MP make_pair
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define PRF first
#define PRS second
#define INIT(ar,val) memset ( ar, val, sizeof ( ar ) )
#define lp(loop,start,end) for ( int loop = start; loop < end; ++loop )
#define lpd(loop,start,end) for ( int loop = start; loop > end; --loop )
#define lpi(loop,start,end) for ( int loop = start; loop <= end; ++loop )
#define lpdi(loop,start,end) for ( int loop = start; loop >= end; --loop )
#define qmax(a,b) (((a)>(b))?(a):(b))
#define qmin(a,b) (((a)<(b))?(a):(b))
#define qabs(a) (((a)>=0)?(a):(-(a)))

const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 507;

int n, m, l, d;

void init ();
void input ();
void work ();

int operate ( const char s[] )
{
	printf ( "%s\n", s );
	fflush ( stdout );
	int ret = 0;
	if ( !( s[0] == 'r' && s[2] == 'v' ) ) scanf ( "%d", &ret );
	return ret;
}



int main ()
{
	init ();
	input ();
	work ();
}



void init ()
{
	// Init Everything Here

	ios::sync_with_stdio ( false );
}

void input ()
{
	// input method

	scanf ( "%d%d%d%d", &n, &m, &l, &d );
}

void work ()
{
	// main work

	int ret;
	while ( 1 ) {
		ret = operate ( "move_left" );
		ret = operate ( "reach_dest" );
		if ( ret == 1 ) break;
	}
}

B. 「LibreOJ Round #9」Menci 的序列 ( LOJ 560 )

题目链接:https://loj.ac/problem/560

考虑每个+写出 \(2^k\),这里 \(k\) 是+右边的*的个数。也就是说这个+最多能对答案产生 \(2^k\) 的贡献。记下每个 \(k\) 有几个+满足,可以发现如果有大于等于3个,我们可以把2个合在一起变成一个 \(2^{k+1}\)。我们记第 \(i\) 位上有 \(a[i]\) 个1。那么有 \(a[i] \le 2\)

我们 \(i\) 从高往低考虑。设当前的答案填到了第 \(j\) 位,如果 \(i \ge j\),那么我们可以贪心的填1。这应该是答案的第一部分,这一部分全部是1,也就是说这一部分的 \(i\) 上 \(\ge 1\) 的位置越多越好。于是并且通过把大于等于3个的进位,我们保证这一段的1尽可能的多。如果 \(i < j\) 了,这时候我们发现我们需要直接把剩下的 \(a\) 直接变成答案。这时候我们发现让 \(\ge 1\) 的位置越靠前越好,于是我们再把所有 \([0,i]\) 上 \(a[i]=2\) 的位置也进位,再填到答案上就行了。

代码

#include <bits/stdc++.h>
using namespace std;

#define LL long long
#define LD long double
#define SC(t,x) static_cast<t>(x)
#define AR(t) vector < t >
#define PII pair < int, int >
#define PLL pair < LL, LL >
#define PIL pair < int, LL >
#define PLI pair < LL, int >
#define PQ priority_queue
#define GT(type) greater < type >
#define MP make_pair
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define PRF first
#define PRS second
#define INIT(ar,val) memset ( ar, val, sizeof ( ar ) )
#define lp(loop,start,end) for ( int loop = start; loop < end; ++loop )
#define lpd(loop,start,end) for ( int loop = start; loop > end; --loop )
#define lpi(loop,start,end) for ( int loop = start; loop <= end; ++loop )
#define lpdi(loop,start,end) for ( int loop = start; loop >= end; --loop )
#define qmax(a,b) (((a)>(b))?(a):(b))
#define qmin(a,b) (((a)<(b))?(a):(b))
#define qabs(a) (((a)>=0)?(a):(-(a)))

const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 1000107;

int n, k;
char s[MAXN];
int a[MAXN];
int ans[MAXN];

void init ();
void input ();
void work ();



int main ()
{
	init ();
	input ();
	work ();
}



void init ()
{
	// Init Everything Here

	ios::sync_with_stdio ( false );
}

void input ()
{
	// input method

	scanf ( "%d%d", &n, &k );
	scanf ( "%s", s );
}

void work ()
{
	// main work

	int nc = 0;
	lpdi ( i, n - 1, 0 ) {
		if ( s[i] == '*' ) ++nc;
		else ++a[nc];
	}

	n += 50;
	lp ( i, 0, n ) {
		if ( a[i] > 2 ) {
			a[i + 1] += ( a[i] - 1 ) >> 1;
			a[i] -= ( a[i] - 1 ) >> 1 << 1;
		}
	}

	int rem = k - 1, now = n;
	while ( 1 ) {
		while ( now >= 0 && !a[now] ) --now;
		if ( now < 0 ) break;
		if ( now < rem ) {
			lp ( i, 0, rem ) a[i + 1] += a[i] >> 1, a[i] &= 1;
			lpdi ( i, rem, 0 ) ans[i] = a[i] > 0;
			break;
		}else ans[rem--] = 1;
		if ( rem < 0 ) break;
		--now;
	}

	int ub = n;
	while ( ub >= 0 && !ans[ub] ) --ub;

	if ( ub < 0 ) printf ( "0\n" );
	else {
		lpdi ( i, ub, 0 ) putchar ( ans[i] + '0' );
		putchar ( '\n' );
	}
}

C. CommonAnts 的调和数 ( LOJ 561 )

题目链接:https://loj.ac/problem/561

直接做是 \(O(n \log n)\) 的。

考虑我们可以把每个数只考虑它的质因子,把每个数写成以每个质因子为一维指数为坐标的点,于是变成了一个类似高位前缀和的东西,依次枚举每个质因子转移即可。这样做是 \(O(n \log \log n)\) 的。

题目保证涉及的质因子个数不超过10,于是只考虑只包含这些质因子的数,这样的数不会超过193571个,设这个集合为 \(S\)。这样子高位前缀和其实就是最多就10维的一个子空间。但是还会有一些包含不是这些质因子的数有贡献。对于这样的数 \(v\),我们找到一个数 \(x \in S\),满足\(\frac{v}{x} \notin S\),把它的贡献加到 \(x\) 上去。其实 \(v\) 的贡献就是 \(x\) 的贡献乘上 \(\left(\frac{v}{x}\right)^2\)。于是 \(x\) 的贡献就需要乘上 \(\sum_{1 \le i \le \lfloor \frac{n}{x} \rfloor, i \notin S} i^2\)。考虑DP这个系数。设 \(dp[i][j]\) 为与前 \(i\) 个质数互质且小于等于 \(j\) 的数的平方和,则有转移 \(dp[i][j]=dp[i-1][j] + dp[i-1][\lfloor \frac{j}{prime[i]} \rfloor] * prime[i]^2\)。由于 \(j\) 只涉及 \(\lfloor \frac{n}{x} \rfloor\) 这些项,\(j\) 是 \(O(\sqrt{n})\) 级别的。于是总复杂度就是 \(O((\sqrt{n} + 193571) * 10)\)。

代码

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;

#define LL long long
#define LD long double
#define SC(t,x) static_cast<t>(x)
#define AR(t) vector < t >
#define PII pair < int, int >
#define PLL pair < LL, LL >
#define PIL pair < int, LL >
#define PLI pair < LL, int >
#define PQ priority_queue
#define GT(type) greater < type >
#define MP make_pair
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define PRF first
#define PRS second
#define INIT(ar,val) memset ( ar, val, sizeof ( ar ) )
#define lp(loop,start,end) for ( int loop = start; loop < end; ++loop )
#define lpd(loop,start,end) for ( int loop = start; loop > end; --loop )
#define lpi(loop,start,end) for ( int loop = start; loop <= end; ++loop )
#define lpdi(loop,start,end) for ( int loop = start; loop >= end; --loop )
#define qmax(a,b) (((a)>(b))?(a):(b))
#define qmin(a,b) (((a)<(b))?(a):(b))
#define qabs(a) (((a)>=0)?(a):(-(a)))

const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 200007;
const int MAXP = 13;
const int MOD = 998244353;
int REV6;

struct arT
{
	void init ( int _n )
	{
		n = _n;
		S = SC ( int, ceil ( sqrt ( SC ( LD, n ) ) ) );
	}
	
	int operator [] ( int i ) const
	{
		return ( i <= S ) ? ar1[i] : ar2[n/i];
	}
	
	int & operator [] ( int i )
	{
		return ( i <= S ) ? ar1[i] : ar2[n/i];
	}
	
	int n, S;
	int ar1[MAXN], ar2[MAXN];
}dp[MAXP];

unordered_map < int, int > id;

int n, m, q;
int qp[MAXN], qx[MAXN], qk[MAXN];
int prm[MAXN], kp;
bool isp[MAXN];
int cp[MAXP], kc;
int ar[MAXN], ka;
int v[MAXN], ans[MAXN];

void init ();
void input ();
void work ();

void addprm ( int x );

void srch ( int ni, int x );



int add ( int x, int y )
{
	x += y;
	return ( x < MOD ) ? x : ( x - MOD );
}

void addv ( int &x, int y )
{
	x += y;
	( x < MOD ) ? x : ( x -= MOD );
}

int sub ( int x, int y )
{
	x -= y;
	return ( x >= 0 ) ? x : ( x + MOD );
}

void subv ( int &x, int y )
{
	x -= y;
	( x >= 0 ) ? x : ( x += MOD );
}

int qpow ( int a, int b )
{
	LL base = a, ans = 1;
	while ( b ){
		if ( b & 1 ) ( ans *= base ) %= MOD;
		( base *= base ) %= MOD;
		b >>= 1;
	}
	return SC ( int, ans );
}



int main()
{
	init();
	input();
	work();
}



void init ()
{
	// Init Everything Here
	
	ios::sync_with_stdio ( false );
	
	REV6 = qpow ( 6, MOD-2 );
	
	INIT ( isp, true );
	isp[0] = isp[1] = false;
	lp ( i, 2, MAXN ){
		if ( isp[i] ) prm[++kp] = i;
		for ( int j = 1; j <= kp && prm[j] * i < MAXN; ++j ){
			isp[prm[j]*i] = false;
			if ( i % prm[j] == 0 ) break;
		}
	}
}

void input ()
{
	// input method
	
	scanf ( "%d%d%d", &n, &m, &q );
	lpi ( i, 1, m ) scanf ( "%d%d", &qp[i], &qx[i] );
	lpi ( i, 1, q ) scanf ( "%d", &qk[i] );
}

void work ()
{
	// main work
	
	lpi ( i, 1, m ) addprm ( qp[i] );
	lpi ( i, 1, q ) addprm ( qk[i] );
	
	srch ( 1, 1 );
	sort ( ar+1, ar+1+ka );
	lpi ( i, 1, ka ) id[ar[i]] = i;
	
//	lpi ( i, 1, ka ) cerr << ar[i] << " "; cerr << endl;
	
	lpi ( i, 1, m ) addv ( v[id[qp[i]]], qx[i] );
	int ti, nt;
	lpi ( i, 1, kc ){
		ti = 1;
		lpi ( j, 1, ka ){
			if ( SC ( LL, ar[j] ) * cp[i] > n ) break;
			nt = ar[j] * cp[i];
			while ( ar[ti] < nt ) ++ti;
			addv ( v[ti], SC ( LL, v[j] ) * cp[i] % MOD );
		}
	}
	
//	lpi ( i, 1, ka ) cerr << v[i] << " "; cerr << endl;
	
	lpi ( i, 0, kc ) dp[i].init ( n );
	int now = n, nv;
	while ( now ){
		nv = n / now;
		dp[0][nv] = SC ( LL, nv ) * ( nv + 1 ) % MOD * ( nv * 2 + 1 ) % MOD * REV6 % MOD;
//		cerr << 0 << " " << nv << " : " << dp[0][nv] << endl;
		now = n / ( nv + 1 );
	}
	lpi ( i, 1, kc ){
		now = n;
		while ( now ){
			nv = n / now;
			dp[i][nv] = sub ( dp[i-1][nv], SC ( LL, dp[i-1][nv/cp[i]] ) * cp[i] % MOD * cp[i] % MOD );
//			cerr << i << " " << nv << " : " << dp[i][nv] << endl;
			now = n / ( nv + 1 );
		}
	}
	
	lpi ( i, 1, ka ) v[i] = SC ( LL, v[i] ) * dp[kc][n/ar[i]] % MOD;
	
//	lpi ( i, 1, ka ) cerr << v[i] << " "; cerr << endl;
	
	lpi ( i, 1, ka ) ans[i] = v[i];
	lpi ( i, 1, kc ){
		ti = ka;
		lpd ( j, ka, 0 ){
			if ( SC ( LL, ar[j] ) * cp[i] <= n ){
				nt = ar[j] * cp[i];
				while ( ar[ti] > nt ) --ti;
				if ( ar[ti] == nt ) addv ( ans[j], SC ( LL, ans[ti] ) * cp[i] % MOD );
			}
		}
	}
	
//	lpi ( i, 1, ka ) cerr << ans[i] << endl;
	
	lpi ( i, 1, q ) printf ( "%d\n", ans[id[qk[i]]] );
}



void addprm ( int x )
{
	int t = x;
	lpi ( i, 1, kc ){
		while ( t % cp[i] == 0 ) t /= cp[i];
	}
	if ( t ^ 1 ){
		for ( int i = 1; i <= kp && prm[i] * prm[i] <= x; ++i ){
			if ( t % prm[i] == 0 ){
				cp[++kc] = prm[i];
				while ( t % prm[i] == 0 ) t /= prm[i];
			}
		}
		if ( t ^ 1 ) cp[++kc] = t;
	}
}



void srch ( int ni, int x )
{
	if ( ni > kc ){
		ar[++ka] = x;
		return;
	}
	
	for ( LL t = x; t <= n; t *= cp[ni] ) srch ( ni+1, t );
}

D. Tangjz 的背包 ( LOJ 562 )

题目链接:https://loj.ac/problem/562

orz 天下第一 wxh 大爷教会我这道题。。。(丢下wxh的博客链接跑:https://blog.csdn.net/wxh010910/article/details/80736601)

首先我们设 \(C=19190506, R=\frac{1}{C}\),于是答案就是 \(C^p*\left( [x^m]\sum_{i=1}^n (1+R^i x) \right)\),稍加转化就变成了 \(C^{p-m}* \left([x^m]\sum_{i=0}^{n-1} (1+R^i x) \right)\)。

然后有样东西叫做Gaussian binomial coefficient,有这么一个性质:\(\prod_{i=0}^{n-1}(1+q^i t)=\sum_{i=0}^n q^{\frac{k*(k-1)}{2}} \binom{n}{k}_q t^k\)。

如果我们令 \(f(q,k)=\prod_{i=1}^n (1-q^i)\) 的话,就可以把我们的式子变成 \(C^{p-m} * R^{\frac{k*(k-1)}{2}} * \frac{f(R,n)}{f(R,m)f(R,n-m)}\)。把 \(C\) 和 \(R\) 合并一下,就变成了\(C^{(n-m) * m}\)。

考虑 \(f(q,n)\) 如何计算。我们有 \(f(q,n)=\prod_{i=1}^n (1-q^i)\),考虑 \(q\) 在模意义下的阶,令为 \(P\),\(P\) 大概在 \(10^6\),于是所有 \(P \nmid i\),可以预处理前缀和,考虑处理 \(P \mid i\),则可以写成 \(\prod_{i=1}^{\lfloor \frac{n}{P} \rfloor} (1-q^{ai})=\prod_{i=1}^{\lfloor \frac{n}{P} \rfloor} (1-q^a)(\sum_{j=0}^{i-1}q^{aj})=\prod_{i=1}^{\lfloor \frac{n}{P} \rfloor} (1-q^a) * i = i! * (1-q^a)^{\lfloor \frac{n}{P} \rfloor}\),于是计算 \(\frac{f(R,n)}{f(R,m)f(R,n-m)}\) 的话比较一下 \(\lfloor \frac{n}{P} \rfloor\) 和 \(\lfloor \frac{m}{P} \rfloor + \lfloor \frac{n-m}{P} \rfloor\) 就行了。

代码

#include <bits/stdc++.h>
using namespace std;

#define LL long long
#define LD long double
#define SC(t,x) static_cast<t>(x)
#define AR(t) vector < t >
#define PII pair < int, int >
#define PLL pair < LL, LL >
#define PIL pair < int, LL >
#define PLI pair < LL, int >
#define PQ priority_queue
#define GT(type) greater < type >
#define MP make_pair
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define PRF first
#define PRS second
#define INIT(ar,val) memset ( ar, val, sizeof ( ar ) )
#define lp(loop,start,end) for ( int loop = start; loop < end; ++loop )
#define lpd(loop,start,end) for ( int loop = start; loop > end; --loop )
#define lpi(loop,start,end) for ( int loop = start; loop <= end; ++loop )
#define lpdi(loop,start,end) for ( int loop = start; loop >= end; --loop )
#define qmax(a,b) (((a)>(b))?(a):(b))
#define qmin(a,b) (((a)<(b))?(a):(b))
#define qabs(a) (((a)>=0)?(a):(-(a)))

const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MOD = 998244353;
const int MUL = 19190506;
const int RM = 768906335;
const int MAXN = 1300007;
const int P = 917504;

LL n, m;
LL pm[MAXN];
LL frac[MAXN], rf[MAXN];



void init ();
void input ();
void work ();



int add ( int x, int y )
{
	x += y;
	return ( x < MOD ) ? x : ( x - MOD );
}

void addv ( int &x, int y )
{
	x += y;
	( x < MOD ) ? x : ( x -= MOD );
}

int sub ( int x, int y )
{
	x -= y;
	return ( x >= 0 ) ? x : ( x +  MOD );
}

void subv ( int &x, int y )
{
	x -= y;
	( x >= 0 ) ? x : ( x += MOD );
}

int qpow ( int a, int b )
{
	LL base = a, ans = 1;
	while ( b ){
		if ( b & 1 ) ( ans *= base ) %= MOD;
		( base *= base ) %= MOD;
		b >>= 1;
	}
	return SC ( int, ans );
}

int C ( int n, int m )
{
	return SC ( int, frac[n] * rf[m] % MOD * rf[n-m] % MOD );
}

int getpm ( LL n )
{
	return qpow ( pm[P-1], n/P ) * SC ( LL, pm[n%P] ) % MOD;
}



int main()
{
	init();
	
	int T;
	scanf ( "%d", &T );
	while ( T-- ){
		input();
		work();
	}
}



void init ()
{
	// Init Everything Here
	
	ios::sync_with_stdio ( false );
	
	frac[0] = 1;
	lp ( i, 1, MAXN ) frac[i] = frac[i-1] * i % MOD;
	rf[MAXN-1] = qpow ( frac[MAXN-1], MOD-2 );
	lpdi ( i, MAXN-2, 0 ) rf[i] = rf[i+1] * ( i + 1 ) % MOD;
	
	pm[0] = 1;
	int np = 1;
	lp ( i, 1, P ){
		np = SC ( LL, np ) * RM % MOD;
		pm[i] = SC ( LL, pm[i-1] ) * sub ( 1, np ) % MOD;
	}
}

void input ()
{
	// input method
	
	scanf ( "%lld%lld", &n, &m );
}

void work ()
{
	// main work
	
	if ( ( n / P ) ^ ( m / P + ( n - m ) / P ) ){
		printf ( "0\n" );
		return;
	}
	
	printf ( "%d\n", SC ( int, SC ( LL, C ( n/P, m/P ) ) * getpm ( n ) % MOD * qpow ( SC ( LL, getpm ( m ) ) * getpm ( n-m ) % MOD, MOD-2 ) % MOD * qpow ( MUL, ( ( n - m ) % P ) * ( m % P ) % P ) % MOD ) );
}

Tianqi Yang

View Comments
Navigation