2024年实验班选拔考试（正式赛）

2,4(1H,3H)-PD are mine 2024-09-09 15:35:01 阅读 92

比赛传送门

邀请码：24wksyb

PS:

经过 0_binary_beast_1 同学的允许，把她的 java 解题代码一起放这里了，供 java 选手参考。

0_binary_beast_1帖子传送门

c++ 代码框架

<code>#include<bits/stdc++.h>

#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 se second

#define fi first

#define endl '\n'

#define all(x) (x).begin(),(x).end()

#define pii pair<int,int>

#define pli pair<LL,int>

#define pll pair<LL,LL>

#define MEM(a,x) memset(a,x,sizeof(a))

#define OJBK {cout<<"ok"<<endl;return;}

inline int Ls(int p){return p<<1;}

inline int Rs(int p){return p<<1|1;}

typedef long long LL;

typedef unsigned long long ULL;

const int MOD=1e9+7;

const int N=1e7+10,M=9999973;

using namespace std;

inline void Solve()

{

}

int main()

{

ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

//INIT();

int _=1;

cin>>_;

while(_--){

Solve();

}

return 0;

}

A. 不会写就伪造

直接打印就行，Ged_id 函数的变量都要用 long long。

c++

LL Get_id(LL n)

{

LL seed=0x5DEECE66D,mask=(1ll<<48)-1;

LL state=(n^seed)&mask;

rep(_,0,5){

state=(state*seed+0xB)&mask;

state^=(state>>17);

state=(state<<31)|(state>>17);

state&=mask;

}

return (state>>16)&((1ll<<32)-1);

}

inline void Solve()

{

int n;cin>>n;

LL x=Get_id(n);

cout<<"Start Running Processes"<<endl<<"------------------------------"<<endl;

rep(i,0,3) cout<<"process "<<i<<" is running, id: "<<x+i<<endl;

cout<<"process 2 finished."<<endl;

cout<<"process 3 is running, id: "<<x+2<<endl;

cout<<"process 1 finished."<<endl;

cout<<"process 4 is running, id: "<<x+1<<endl;

cout<<"process 0 finished."<<endl;

cout<<"process 3 finished."<<endl;

cout<<"process 4 finished."<<endl;

cout<<"------------------------------"<<endl;

cout<<"Processes Finished"<<endl;

}

python

def Get_id(n):

seed=0x5DEECE66D

mask=(1<<48)-1

state=(n^seed)&mask

for _ in range(5):

state=(state*seed+0xB)&mask

state^=(state>>17)

state=(state<<31)|(state >> 17)

state&=mask

result=(state>>16)&((1<<32)-1)

return result

def Solve():

n=int(input())

x=Get_id(n)

print('Start Running Processes')

print('------------------------------')

for i in range(3): print('process {} is running, id: {}'.format(i,x+i))

print('process 2 finished.')

print('process 3 is running, id: {}'.format(x+2))

print('process 1 finished.')

print('process 4 is running, id: {}'.format(x+1))

print('process 0 finished.')

print('process 3 finished.')

print('process 4 finished.')

print('------------------------------')

print('Processes Finished')

if __name__ == '__main__':

t=1

t=int(input())

while t:

Solve()

t-=1

java

import java.io.*;

import java.math.BigDecimal;

import java.math.BigInteger;

import java.util.StringTokenizer;

public class Main {

static InputReader in = new InputReader();

static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

public static void main(String[] args) throws Exception {

int t = 1;

t = in.nextInt();

while (t-- > 0) {

solve();

}

out.close();

}

public static long getId(int n) {

long seed = 0x5DEECE66DL;

long mask = (1L << 48) - 1;

long state = (n ^ seed) & mask;

for (int i = 0; i < 5; i++) {

state = (state * seed + 0xBL) & mask;

state ^= (state >> 17);

state = (state << 31) | (state >> 17);

state &= mask;

}

return ((state >> 16) & ((1L << 32) - 1));

}

public static void solve() throws IOException {

int n = in.nextInt();

long x = getId(n);

out.println("Start Running Processes");

out.println("------------------------------");

for (int i = 0; i < 3; i++) {

out.println(String.format("process %d is running, id: %d", i, x + i));

}

out.println("process 2 finished.");

out.println(String.format("process 3 is running, id: %d", x + 2));

out.println("process 1 finished.");

out.println(String.format("process 4 is running, id: %d", x + 1));

out.println("process 0 finished.");

out.println("process 3 finished.");

out.println("process 4 finished.");

out.println("------------------------------");

out.println("Processes Finished");

}

static class InputReader{

private StringTokenizer st;

private BufferedReader bf;

public InputReader() {

bf = new BufferedReader(new InputStreamReader(System.in));

st = null;

}

public String next() throws IOException{

while(st == null || !st.hasMoreTokens()) {

st = new StringTokenizer(bf.readLine());

}

return st.nextToken();

}

public String nextLine() throws IOException{

return bf.readLine();

}

public int nextInt() throws IOException{

return Integer.parseInt(next());

}

public long nextLong() throws IOException{

return Long.parseLong(next());

}

public double nextDouble() throws IOException{

return Double.parseDouble(next());

}

public BigInteger nextBigInteger() throws IOException{

return new BigInteger(next());

}

public BigDecimal nextBigDecimal() throws IOException{

return new BigDecimal(next());

}

B. 美味生日茶

把加密函数倒过来写就行了，注意原来函数中类型是 unsigned int，运算中产生溢出相当于对

$2^{32}$

取模，如果用其他类型变量需要考虑取模。

c++

<code>void De(unsigned int* v)

{

unsigned int v0 = v[0], v1 = v[1];

unsigned int delta = 1312;

unsigned int sum = delta*32;

unsigned int k0 = 1, k1 = 3, k2 = 1, k3 = 4;

for(int i=0;i<32;i++)

{

v1 -= ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);

v0 -= ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);

sum -= delta;

}

v[0] = v0, v[1] = v1;

}

inline void Solve()

{

unsigned int v[4];

cin>>v[0]>>v[1];

De(v);

cout<<v[0]<<" "<<v[1]<<endl;

}

java

import java.io.*;

import java.math.BigDecimal;

import java.math.BigInteger;

import java.util.StringTokenizer;

public class Main {

static InputReader in = new InputReader();

static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

public static void main(String[] args) throws Exception {

long[] v = new long[2];

v[0] = in.nextLong();

v[1] = in.nextLong();

decrypt(v);

out.printf("%d %d\n", v[0], v[1]);

out.close();

}

public static void decrypt(long[] v) {

long MOD = (1L<<32);

long v0 = v[0], v1 = v[1];

int delta = 1312;

int sum = delta * 32;

int k0 = 1, k1 = 3, k2 = 1, k3 = 4;

for (int i = 0; i < 32; i++) {

v1 -= ((v0 << 4)%MOD + k2) ^ (v0 + sum) ^ ((v0 >> 5) + k3) %MOD;

v1 = (v1%MOD + MOD)%MOD;

v0 -= ((v1 << 4)%MOD + k0) ^ (v1 + sum) ^ ((v1 >> 5) + k1) %MOD;

v0 = (v0%MOD + MOD)%MOD;

sum -= delta;

}

v[0] = v0; v[1] = v1;

}

static class InputReader{

private StringTokenizer st;

private BufferedReader bf;

public InputReader() {

bf = new BufferedReader(new InputStreamReader(System.in));

st = null;

}

public String next() throws IOException{

while(st == null || !st.hasMoreTokens()) {

st = new StringTokenizer(bf.readLine());

}

return st.nextToken();

}

public String nextLine() throws IOException{

return bf.readLine();

}

public int nextInt() throws IOException{

return Integer.parseInt(next());

}

public long nextLong() throws IOException{

return Long.parseLong(next());

}

public double nextDouble() throws IOException{

return Double.parseDouble(next());

}

public BigInteger nextBigInteger() throws IOException{

return new BigInteger(next());

}

public BigDecimal nextBigDecimal() throws IOException{

return new BigDecimal(next());

}

C. 114514,1919810

数

在序列中的最后一个位置是

$\frac{i(i+1)}{2}$

，很容易想到二分答案，找到

$\frac{i(i+1)}{2} \ge n$

的最小

就是答案。（或者找到

$\frac{i(i+1)}{2} \le n$

的最大

，最后判断

$\frac{i(i+1)}{2} \ne n$

就加1。）

c++

<code>inline void Solve()

{

int n;

cin>>n;

int l=1,r=n;

while(l<r){

int m=l+r>>1;

if(1ll*m*(m+1)/2>=n) r=m;

else l=m+1;

}

cout<<l<<endl;

}

python

def Solve():

n=int(input())

l,r=1,n

while l<r:

m=(l+r+1)//2

if m*(m+1)//2<=n: l=m

else:r=m-1

if n==l*(l+1)//2: print(l)

else: print(l+1)

if __name__ == '__main__':

t=1

t=int(input())

while t:

Solve()

t-=1

java

import java.io.*;

import java.math.BigDecimal;

import java.math.BigInteger;

import java.util.*;

public class Main {

static InputReader in = new InputReader();

static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

public static void main(String[] args) throws Exception {

int t = 1;

t = in.nextInt();

while (t-- > 0) {

solve();

}

out.close();

}

public static void solve() throws IOException {

int n = in.nextInt();

int l = 1, r = n;

while (l < r) {

int mid = (l + r) / 2;

long sum = (1L * mid * (mid + 1) )/ 2;

if (sum < n) l = mid + 1; else r = mid;

}

out.println(l);

}

static class InputReader {

private StringTokenizer st;

private BufferedReader bf;

public InputReader() {

bf = new BufferedReader(new InputStreamReader(System.in));

st = null;

}

public String next() throws IOException {

while (st == null || !st.hasMoreTokens()) {

st = new StringTokenizer(bf.readLine());

}

return st.nextToken();

}

public String nextLine() throws IOException {

return bf.readLine();

}

public int nextInt() throws IOException {

return Integer.parseInt(next());

}

public long nextLong() throws IOException {

return Long.parseLong(next());

}

public double nextDouble() throws IOException {

return Double.parseDouble(next());

}

public BigInteger nextBigInteger() throws IOException {

return new BigInteger(next());

}

public BigDecimal nextBigDecimal() throws IOException {

return new BigDecimal(next());

}

D. IP黑名单

简单模拟，日志中含有 "Invalid" 直接封 IP，含有 "Failded" 的提取 IP 计算一下出现的次数，超过 m 才禁封。c++ 中可以使用正则匹配提取 IP，哈希表计算 IP 出现的次数，禁封过的 IP 加入集合中，每次要禁封前判断一下即可。

c++

void Solve()

{

int n,m;cin>>n>>m;

unordered_set<string>st;

unordered_map<string,int>mp;

regex ip_re(R"(\b\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3}\b)");

smatch ip;

rep(_,0,n){

string s;

while(getline(cin,s)&&s=="");

if(s.find("Invalid")!=string::npos){

regex_search(s,ip,ip_re);

if(st.find(ip[0])!=st.end()) continue;

st.insert(ip[0]);

cout<<"sshd:"<<ip[0]<<endl;

continue;

}

if(s.find("Failed")!=string::npos){

regex_search(s,ip,ip_re);

if(st.find(ip[0])!=st.end()) continue;

mp[ip[0]]+=1;

if(mp[ip[0]]>m){

st.insert(ip[0]);

cout<<"sshd:"<<ip[0]<<endl;

}

python

import re

def Solve():

n,m=map(int,input().split())

ban={}

ctip={}

for _ in range(n):

line=input()

gp=re.search(r'Invalid user \w+ from (\d+\.\d+\.\d+\.\d+)',line)

if gp and not ban.get(gp[1]):

ban[gp[1]]=1

print('sshd:{}'.format(gp[1]))

gp=re.search(r'Failed password for \w+ from (\d+\.\d+\.\d+\.\d+)',line)

if gp and not ban.get(gp[1]):

ip=gp[1]

ctip[ip]=ctip.get(ip,0)+1

if ctip[ip]>m:

del ctip[ip]

ban[ip]=1

print('sshd:{}'.format(ip))

if __name__ == '__main__':

t=1

#t=int(input())

while t:

Solve()

t-=1

java

import java.io.*;

import java.math.BigDecimal;

import java.math.BigInteger;

import java.util.*;

import java.util.regex.*;

public class Main {

static InputReader in = new InputReader();

static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

public static void main(String[] args) throws Exception {

int t = 1;

// t = in.nextInt();

while (t-- > 0) {

solve();

}

out.close();

}

public static void solve() throws IOException {

int n = in.nextInt();

int m = in.nextInt();

Set<String> st = new HashSet<>();

Map<String, Integer> hs = new HashMap<>();

Pattern ipRe = Pattern.compile("\\b\\d{1,3}\\.\\d{1,3}\\.\\d{1,3}\\.\\d{1,3}\\b");

for (int i = 0; i < n; i++) {

String s;

while ((s = in.nextLine()) != null && s.equals(""));

if (s.contains("Accepted")) continue;

Matcher ma = ipRe.matcher(s);

if (s.contains("Invalid")) {

if (ma.find()) {

String ip = ma.group();

if (st.contains(ip)) continue;

st.add(ip);

out.println("sshd:" + ip);

}

else if (s.contains("Failed")) {

if (ma.find()) {

String ip = ma.group();

if (st.contains(ip)) continue;

hs.put(ip, hs.getOrDefault(ip, 0) + 1);

if (hs.get(ip) > m) {

st.add(ip);

out.println("sshd:" + ip);

}

static class InputReader {

private StringTokenizer st;

private BufferedReader bf;

public InputReader() {

bf = new BufferedReader(new InputStreamReader(System.in));

st = null;

}

public String next() throws IOException {

while (st == null || !st.hasMoreTokens()) {

st = new StringTokenizer(bf.readLine());

}

return st.nextToken();

}

public String nextLine() throws IOException {

return bf.readLine();

}

public int nextInt() throws IOException {

return Integer.parseInt(next());

}

public long nextLong() throws IOException {

return Long.parseLong(next());

}

public double nextDouble() throws IOException {

return Double.parseDouble(next());

}

public BigInteger nextBigInteger() throws IOException {

return new BigInteger(next());

}

public BigDecimal nextBigDecimal() throws IOException {

return new BigDecimal(next());

}

E. 桨声灯影

当 n 为素数时，因数只有 1 和 n，

S_n=n

，显然满足条件。

当 n 为和数时，

$k> 2$

，设 p 为 n 的最小素因子，有

$S_n > d_{k-1}d_k=\frac{n}{p} \cdot n=\frac{n^2}{p}$

。假设

$S_n \mid n^2$

，则有

$\frac{n^2}{S_n} < p$

，而且注意到

$S_n=\sum_{i=1}^{k-1}d_id_{i+1}=n^2 \sum_{i=1}^{k-1}\frac{1}{d_id_{i+1}} < n^2$

，故

$\frac{n^2}{S_n}$

为

n^2

的一个大于 1 且比 p 小的因子，与前提 p 为

n^2

的最小素因子矛盾，合数情况不满足。

写一个线性素数筛即可通过所有数据。

c++

<code>const int N=1e7+10,M=9999973;

using namespace std;

int v[N],pr[N],cnt;

void INIT(int n)

{

rep(i,2,n+1){

if(!v[i]) pr[++cnt]=i;

rep(j,1,cnt+1){

if(i*pr[j]>n) break;

v[i*pr[j]]=1;

if(i%pr[j]==0) break;

}

void Solve()

{

int n;cin>>n;

rep(i,2,n+1) if(v[i]) cout<<"NO"<<endl;else cout<<"YES"<<endl;

}

int main()

{

ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

INIT(10000000);

int _=1;

//cin>>_;

while(_--){

Solve();

}

return 0;

}

java

import java.io.*;

import java.math.BigDecimal;

import java.math.BigInteger;

import java.util.StringTokenizer;

public class Main {

static InputReader in = new InputReader();

static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

static final int N = (int) 1e7;

static int[] vis = new int[N+5];

static int[] primes = new int[N+5];

public static void main(String[] args) throws Exception {

int t = 1;

//t = in.nextInt();

while (t-- > 0) {

solve();

}

out.close();

}

public static void solve() throws IOException {

int n = in.nextInt(), cnt = 0;

for (int i = 2; i <= N; i++) {

if (vis[i] == 0) primes[++cnt] = i;

for (int j = 1; j <= cnt && i * primes[j] <= N; j++) {

vis[i * primes[j]] = 1;

if (i % primes[j] == 0) break;

}

for (int i = 2; i <= n; i++) {

if (vis[i] != 0) out.println("NO"); else out.println("YES");

}

static class InputReader{

private StringTokenizer st;

private BufferedReader bf;

public InputReader() {

bf = new BufferedReader(new InputStreamReader(System.in));

st = null;

}

public String next() throws IOException{

while(st == null || !st.hasMoreTokens()) {

st = new StringTokenizer(bf.readLine());

}

return st.nextToken();

}

public String nextLine() throws IOException{

return bf.readLine();

}

public int nextInt() throws IOException{

return Integer.parseInt(next());

}

public long nextLong() throws IOException{

return Long.parseLong(next());

}

public double nextDouble() throws IOException{

return Double.parseDouble(next());

}

public BigInteger nextBigInteger() throws IOException{

return new BigInteger(next());

}

public BigDecimal nextBigDecimal() throws IOException{

return new BigDecimal(next());

}

F. 文件系统树

构造的链的数据可以卡掉 dfs 的做法，考虑拓扑排序，建立父节点到子节点的有向边，记录出度，把出度为 0 的子节点加入队列中，往上更新权值的同时删边，中途把产生的新子节点加入队列中，直到只剩下根节点为止。

c++

const int N=1e6+10,M=9999973;

using namespace std;

int fa[N],d[N];

LL w[N];

void Solve()

{

int n;

cin>>n;

int rt=0;

rep(i,0,n){

int a,b,c;

cin>>a>>b>>c;

w[a]=c;

if(b==-1) rt=a;

else{

fa[a]=b;++d[b];

}

queue<int>q;

rep(i,0,n) if(d[i]==0) q.push(i);

while(q.size()){

int t=q.front();q.pop();

if(t==rt) continue;

int u=fa[t];

w[u]+=w[t];

if(--d[u]==0) q.push(u);

}

rep(i,0,n) cout<<w[i]<<" ";

}

java

import java.io.*;

import java.math.BigDecimal;

import java.math.BigInteger;

import java.util.*;

public class Main {

static InputReader in = new InputReader();

static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

static final int N = (int) 1e6 + 10;

static int[] fa = new int[N];

static int[] deg = new int[N];

static long[] val = new long[N];

public static void main(String[] args) throws Exception {

int t = 1;

//t = in.nextInt();

while (t-- > 0) {

solve();

}

out.close();

}

public static void solve() throws IOException {

int n = in.nextInt();

for (int i = 0; i < n; i++) {

int a = in.nextInt(), b = in.nextInt(), c = in.nextInt();

val[a] = c; fa[a] = b;

if (b != -1) ++deg[b];

}

Queue<Integer> que = new LinkedList<>();

for (int i = 0; i < n; i++) {

if (deg[i] == 0) que.offer(i);

}

while (!que.isEmpty()) {

int v = que.poll(), u = fa[v];

if (u == -1) break;

val[u] += val[v];

if (--deg[u] == 0) que.offer(u);

}

for (int i = 0; i < n; i++) out.print(val[i] + " ");

}

static class InputReader{

private StringTokenizer st;

private BufferedReader bf;

public InputReader() {

bf = new BufferedReader(new InputStreamReader(System.in));

st = null;

}

public String next() throws IOException{

while(st == null || !st.hasMoreTokens()) {

st = new StringTokenizer(bf.readLine());

}

return st.nextToken();

}

public String nextLine() throws IOException{

return bf.readLine();

}

public int nextInt() throws IOException{

return Integer.parseInt(next());

}

public long nextLong() throws IOException{

return Long.parseLong(next());

}

public double nextDouble() throws IOException{

return Double.parseDouble(next());

}

public BigInteger nextBigInteger() throws IOException{

return new BigInteger(next());

}

public BigDecimal nextBigDecimal() throws IOException{

return new BigDecimal(next());

}

G. 10cm距离

不妨设

$a_i \le a_j$

，则有

$a_j-a_i \ge b_i+b_j$

，即

$a_j-b_j \ge b_i+a_i$

。对于每一个节点 i 都维护出

l_i=a_i-b_i,r_i=a_i+b_i

两个值。把节点信息看作线段

$[l_i,r_i]$

，两者不干扰条件就可以表示成

$l_j \ge r_i$

，可以发现只有线段不相交（包含端点相交的情况）才能满足

$l_j \ge r_i$

。有人问如果两个线段不相交且

$l_i > r_j$

也不满足条件，但是注意根据前提

$a_i \le a_j$

有

$l_i \le r_j$

，前提条件下并不会出现这种情况，只需要保证尽可能多的线段不相交（包含端点相交）即可。

问题转换为经典贪心问题做法，按照右端点的值从小到大排序，优先选择右端点的值小的。

c++

<code>const int N=1e6+10;

using namespace std;

pii a[N];

bool cmp(pii a,pii b)

{

return a.se<b.se;

}

void Solve()

{

int n;cin>>n;

rep(i,1,n+1){

int x,y;cin>>x>>y;

a[i].fi=x-y,a[i].se=x+y;

}

sort(a+1,a+1+n,cmp);

int ans=0,r=-2e9;

rep(i,1,n+1){

if(a[i].fi>=r) ++ans,r=a[i].se;

}

cout<<ans<<endl;

}

java

import java.io.*;

import java.math.BigDecimal;

import java.math.BigInteger;

import java.util.*;

public class Main {

static InputReader in = new InputReader();

static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

static final int N = (int) 1e6 + 10;

static class Pair implements Comparable<Pair> {

int x, y;

Pair(int x, int y) {

this.x = x;

this.y = y;

}

public int compareTo(Pair to) {

return Integer.compare(y, to.y);

}

static Pair[] p = new Pair[N];

public static void main(String[] args) throws Exception {

int t = 1;

//t = in.nextInt();

while (t-- > 0) {

solve();

}

out.close();

}

public static void solve() throws IOException {

int n = in.nextInt();

for (int i = 0; i < n; i++) {

int x = in.nextInt(), y = in.nextInt();

p[i] = new Pair(x - y, x + y);

}

Arrays.sort(p, 0, n);

int ans = 0;

int now = (int) -2e9;

for (int i = 0; i < n; i++) {

if (p[i].x >= now) {

ans++;

now = p[i].y;

}

out.println(ans);

}

static class InputReader{

private StringTokenizer st;

private BufferedReader bf;

public InputReader() {

bf = new BufferedReader(new InputStreamReader(System.in));

st = null;

}

public String next() throws IOException{

while(st == null || !st.hasMoreTokens()) {

st = new StringTokenizer(bf.readLine());

}

return st.nextToken();

}

public String nextLine() throws IOException{

return bf.readLine();

}

public int nextInt() throws IOException{

return Integer.parseInt(next());

}

public long nextLong() throws IOException{

return Long.parseLong(next());

}

public double nextDouble() throws IOException{

return Double.parseDouble(next());

}

public BigInteger nextBigInteger() throws IOException{

return new BigInteger(next());

}

public BigDecimal nextBigDecimal() throws IOException{

return new BigDecimal(next());

}

H. 退避时间管理带师

直接计算不现实，考虑计算 n 个数当中时间为 i 的个数，若 x 的时间为 i 需要满足

$j(1 \le j \le i-1) \mid x,i \nmid x$

，相当于求满足

$\left [ 1,2,...,i-1\right ] \mid x,\left [ 1,2,...,i\right ] \nmid x$

的个数（

$\left [ \ \right ]$

表示最小公倍数），即为

$\left \lfloor \frac{n}{\left [ 1,2,...,i-1 \right ]} \right \rfloor - \left \lfloor \frac{n}{\left [ 1,2,...,i \right ]} \right \rfloor$

，先预处理出 1~i 前缀最小公倍数，由于最小公倍数增长很快，处理到40到50就可以了。

c++

<code>const int MOD=998244353;

const int N=1e6+10;

using namespace std;

LL s[45];

LL Gcd(LL a,LL b)

{

while(b^=a^=b^=a%=b);

return a;

}

void INIT()

{

s[1]=1;

rep(i,2,41) s[i]=i/Gcd(s[i-1],i)*s[i-1];

}

void Solve()

{

LL n,res=0;cin>>n;

for(int i=2;s[i-1]<=n;++i){

res=(res+i*(n/s[i-1]-n/s[i])%MOD)%MOD;

}

cout<<res%MOD<<endl;

}

int main()

{

ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

int _=1;

cin>>_;

INIT();

while(_--){

Solve();

}

return 0;

}

java

import java.io.*;

import java.math.BigDecimal;

import java.math.BigInteger;

import java.util.*;

public class Main {

static InputReader in = new InputReader();

static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

static final int N = (int) 1e6 + 10;

static final int MOD = 998244353;

static long[] lcm = new long[50];

public static void main(String[] args) throws Exception {

int t = 1;

t = in.nextInt();

initial();

while (t-- > 0) {

solve();

}

out.close();

}

static long gcd(long a, long b) {

while (b != 0) {

long t = b;

b = a % b;

a = t;

}

return a;

}

static void initial() {

lcm[1] = 1;

for (int i = 2; i < 50; ++i) {

lcm[i] = i / gcd(lcm[i - 1], i) * lcm[i - 1];

}

public static void solve() throws IOException {

long n = in.nextLong();

long ans=0;

for (int i = 2; lcm[i-1] <= n; ++i) {

ans = (ans + i * ((n / lcm[i-1]) - (n / lcm[i])) % MOD) % MOD;

}

out.println(ans % MOD);

}

static class InputReader{

private StringTokenizer st;

private BufferedReader bf;

public InputReader() {

bf = new BufferedReader(new InputStreamReader(System.in));

st = null;

}

public String next() throws IOException{

while(st == null || !st.hasMoreTokens()) {

st = new StringTokenizer(bf.readLine());

}

return st.nextToken();

}

public String nextLine() throws IOException{

return bf.readLine();

}

public int nextInt() throws IOException{

return Integer.parseInt(next());

}

public long nextLong() throws IOException{

return Long.parseLong(next());

}

public double nextDouble() throws IOException{

return Double.parseDouble(next());

}

public BigInteger nextBigInteger() throws IOException{

return new BigInteger(next());

}

public BigDecimal nextBigDecimal() throws IOException{

return new BigDecimal(next());

}

I. Packet Subset Selection

相当于从集合

$A = \{1,2,3,...,2p\}$

中选择 p 个元素，记选择的 p 个元素为

$1 \le x_1 < x_2 ... < x_p \le 2p$

，求满足

$\sum_{x=1}^{p}x_i \equiv 0 \pmod{p}$

的解的个数。

考虑将一个合法解按照 p 为分界做划分，即：

$1 \le x_1 < x_2 < ... < x_t \le p < x_{t+1} < ... < x_p \le 2p$

下面可以分为三种情况：

（1）如果

t=0

，即所有数都比 p 大，显然存在唯一解：

x_i=i+p

（2）如果

t=p

，即所有数都小于等于 p ，显然存在唯一解：

x_i=i

（3）剩下

$1\le t \le p-1$

，含 p 个元素的子集总个数是

$\binom{2p}{p}$

，除去前面两种合法的情况就是

$\binom{2p}{p} -2$

，考虑把子集再次做划分，按照下面的规则划分为不相交的等价类：

定义两个子集

$\{x_1,x_2,...,x_p\}$

和

$\{x^{'}_1,x^{'}_2,...,x^{'}_p\}$

属于同一个等价类，当且仅当它们的

划分相等，当

$t+1 \le i \le p$

时满足

$x^{'}_i = x_i$

；当

$1 \le i \le t$

时，满足

$\exists m,x^{'}_i \equiv x_i + m \pmod{p}$

这样，每一个等价类按照 m 的取值都可以表示 p 个子集，等价类的总个数就是

$\frac{\binom{2p}{p} -2}{p}$

。

考虑某一个等价类的元素和，选择其中的一个子集

$\{x_1,x_2,...,x_p\}$

，记

$s=\sum_{i=1}^{p} x_i$

，这个等价类模 p 的和就可以表示成

$s+m \cdot t \pmod{p}$

，则需要满足条件

$s+m \cdot t \equiv 0 \pmod{p}$

，对于固定了

和

的等价类，p 为奇素数，该方程有唯一解为

$m \equiv (p-s)\cdot t^{p-2} \pmod{p}$

。所以满足条件解的个数就是等价类的总个数。

综上所述，总方案个数就是

$\frac{\binom{2p}{p} -2}{p} +2$

。

预处理阶乘逆元计算组合数，加上卢卡斯定理即可通过。

<code>const int N=1e7+10,M=9999973;

using namespace std;

int fac[N],inv[N];

int qp(int a,int b)

{

int res=1;

while(b){

if(b&1) res=1ll*res*a%M;

a=1ll*a*a%M;

b>>=1;

}

return res%M;

}

void INIT()

{

int n=10000000;

fac[0]=inv[0]=1;

rep(i,1,n+1) fac[i]=1ll*i*fac[i-1]%M,inv[i]=1ll*inv[i-1]*qp(i,M-2)%M;

}

int C(LL a,LL b)

{

if(b>a) return 0;

if(a==b||!b) return 1;

if(a<M&&b<M){

return 1ll*fac[a]*inv[b]%M*inv[a-b]%M;

}

return 1ll*C(a/M,b/M)*C(a%M,b%M)%M;

}

int sfmod(int x)

{

return (x%M+M)%M;

}

void Solve()

{

LL p;cin>>p;

int ans=C(2*p,p)-2;ans=sfmod(ans);

ans=1ll*ans*qp(p%M,M-2)%M;ans+=2;ans=sfmod(ans);

cout<<ans<<endl;

}

int main()

{

ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

int _=1;

cin>>_;

INIT();

while(_--){

Solve();

}

return 0;

}

上一篇： Java 工程解耦即高内聚低耦合

下一篇： redis常用知识汇总（包括 jedis 和 springboot 整合 redis）

本文标签

2024年实验班选拔考试（正式赛）

声明

本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。