A 以我为始

题目类型及难度定位:签到题,难度(1/10)星

注意到图片中的高校是河南工业大学(Henan University of Technology),英文缩写为HAUT,直接输出HAUT即可,注意要以大写形式输出。

参考代码:

#include <iostream>
using namespace std;

int main() {
    cout<<"HAUT";
    return 0;
}

“HAUT——梦开始的地方”

B 上大学第一个月就花光所有钱

签到题 直接进行暴力枚举,预处理枚举甜甜圈数量 a,再枚举蛋糕数量 b,时间复杂度为x*x/(47*352)完全可行,查询时仅需判断目标金额是否被标记即可,单次查询时间复杂度为 O(1)。 此外,本题还可以从数论角度理解。对于两个互质的正整数 47 和 352,根据裴蜀定理在非负整数情形下的常见推论,即 Frobenius 硬币问题,超过 47×352−47−352 的所有整数都可以表示为 47a+352b 的形式。因此,当目标金额足够大时,其可行性可以直接由该结论得到。

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define int long long
#define pb push_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define ff first
#define ss second
#define bb begin()
#define ee end()
#define pii pair<int,int>
#define lc p<<1
#define rc p<<1|1
using namespace std;
int n=10000;
vi st;
void solve()
{
	int x;cin>>x;
	if(st[x]) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T=1;
	cin>>T;
	st.assign(n+10,0);
	for(int i=0;i<=n/47;i++){
		for(int j=0;i*47+j*352<=n;j++){
			st[i*47+j*352]=1;
		}
	}
	while(T--)
	{
		solve();
	}
	return 0;
}

C 先打把王者荣耀

基础题

求三个不同属性在同一体积限制V下的最大乘积,思路就是求三个背包在任一限制j下能达到的最大值,然后通过枚举分配给三个背包多少容积去求答案。具体来说,对于三种属性先分别用 01 背包预处理一个 mx数组。mx[i][j]代表如果把背包容量限制在 j,可以获得属性 i 的最大增益值。接着枚举给前两种属性分配多少的背包容量,然后更新答案即可。假设给属性 1 分配 v1 的容量,属性 2 分配 v2 的容量,那么这种分配方式能得到的 最大战斗力为 mx[1][v1]*mx[2][v2]*mx[3][V-v1-v2]。复杂度为O(mV+V^2) 。

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define int long long
#define pb push_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define ff first
#define ss second
#define bb begin()
#define ee end()
#define pii pair<int,int>
using namespace std;
void solve()
{
	int m,n;cin>>m>>n;
	vvi f1(n+1,vi(m+1)),f2(n+1,vi(m+1)),f3(n+1,vi(m+1));
	vi v1(n+1),w1(n+1),v2(n+1),w2(n+1),v3(n+1),w3(n+1);
	for(int i=1;i<=n;i++) cin>>v1[i]>>w1[i];
	for(int i=1;i<=n;i++) cin>>v2[i]>>w2[i];
	for(int i=1;i<=n;i++) cin>>v3[i]>>w3[i];	

	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=m;j++)
		{
			f1[i][j]=f1[i-1][j];
			f2[i][j]=f2[i-1][j];
			f3[i][j]=f3[i-1][j];

			if(j>=v1[i]) f1[i][j]=max(f1[i-1][j],f1[i-1][j-v1[i]]+w1[i]);
			if(j>=v2[i]) f2[i][j]=max(f2[i-1][j],f2[i-1][j-v2[i]]+w2[i]);
			if(j>=v3[i]) f3[i][j]=max(f3[i-1][j],f3[i-1][j-v3[i]]+w3[i]);
		}
	}
	int ans=0;
	for(int i=0;i<=m;i++)
	{
		for(int j=0;j+i<=m;j++)
		{
			ans=max(ans,f1[n][i]*f2[n][j]*f3[n][m-i-j]);
		}
	}
	cout<<ans<<endl;

}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T;cin>>T;
	while(T--)
	{
		solve();
	}
	return 0;
}

D 终于快进到xcpc了,这是签到吗?

先对比S和T的长度的大小区别,再分别对几种情况暴力对比是否符合。

bool same_or_change(string a,string b) { //相等或者修改一个得到t
    int diff = 0;
    for (int i = 0; i < a.size(); i++) {
        if (a[i] != b[i]) {
            if (++diff > 1) return false;
        }
    }
    return true;
}
bool insert_one(string s,string t) {     //检查t是否可以通过插入得到
    int n = s.size(), m = t.size();
    int i = 0, j = 0;
    bool used = false;

    while (i < n && j < m) {
        if (s[i] == t[j]) {
            i++; j++;
        } else {
            if (used) return false;
            used = true;
            j++;
        }
    }
    return true;
}

bool delete_one(string s,string t) {
    int n = s.size(), m = t.size();
    int i = 0, j = 0;
    bool used = false;

    while (i < n && j < m) {
        if (s[i] == t[j]) {
            i++; j++;
        } else {
            if (used) return false;
            used = true;
            i++;
        }
    }
    return true;
}

int main() {
    int N;
    cin >> N;
    string T;
    cin >> T;
    vector<int> ans;
    for (int i = 1; i <= N; i++) {
        string S;
        cin >> S;

        int a = S.size(), b = T.size();
        bool ok = false;

        if (abs(a - b) > 1) {
            ok = false;
        } 
        else if (a == b) {
            ok = same_or_change(S, T);
        } 
        else if (a + 1 == b) {
            ok = insert_one(S, T);
        } 
        else if (a == b + 1) {
            ok = delete_one(S, T);
        }

        if (ok) ans.push_back(i);
    }
    cout << ans.size() << "\n";
    if (!ans.empty()) {
        for (int i = 0; i <ans.size(); i++) {
            if (i) cout << " ";
            cout << ans[i];
        }
        cout << "\n";
    }
    return 0;
}

E 不是,你这是什么代码啊?

简单题

由于输入范围中 n 最大可达 1e18,若直接照搬该递归实现,会产生极深的递归调用链,导致栈空间耗尽,从而在评测时直接崩溃。简单分析发现,当 n≥20250101 时,递归参数会不断减小并最终进入基本情况区间,且该过程的最终返回值与初始的 n 无关,始终收敛为同一个常数。具体而言,当 n<20250101 时,结果为 n+2024;当 n≥20250101 时,结果恒为 20250101+2023。因此可以用简单的条件判断直接输出结果,完全避免递归调用。该解法时间复杂度为 O(1),空间复杂度为 O(1)。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    const long long T = 20250101;
    long long n;
    cin >> n;

    if (n < T) cout << n + 2024 << "\n";
    else cout << T + 2023 << "\n";  // 即 20252124

    return 0;
}

F 这是贪心吗?

可以将问题转化为背包的最大容量是总重量/2向下取整,每个物品的价值是它放在头部的幸福度减去放在身体的幸福度的背包问题。

#define int long long
#define endl '\n'
const int N = 510;
int w[N],h[N],b[N],new_worthy[N],dp[260000];
signed main()
{
    int n;cin>>n;int sum_w=0;int base=0;
    for(int i=1;i<=n;i++)
    {
         cin>>w[i]>>h[i]>>b[i];base+=b[i];
         new_worthy[i]=h[i]-b[i];
         sum_w+=w[i];
    }
    //等价于背包容量是sum_w/2向下取整

    for(int i=1;i<=n;i++)
    {
       for(int j=sum_w/2;j>=w[i];j--)
       {
           dp[j]=max(dp[j-w[i]]+new_worthy[i],dp[j]);
       }
    }
    cout<<dp[sum_w/2]+base<<endl;
}

G 来吧,甜蜜的博弈

题目类型及难度定位:博弈论、贪心,难度(7/10)星

一道很有意思的题,策略想清楚后代码很简单。

(下标从 1 开始)记 x=a[n−1],y=a[n]。

情况一xy 之间有空位,即 x+1<y

第一回合,Alice 先试着把 y 移动到 x+1。然后轮到 Bob,他必须将 x+1 移动到一个小于 x 的位置 z

  • 如果 Bob 没有必胜的移动方案,那么 Alice 获胜。
  • 如果 Bob 移动到 z 是必胜的,那么 Alice 可以「悔棋」,在第一回合,直接把 y 移动到 z,从而必胜。

所以只要 x+1<y,Alice 就一定是必胜的。

情况二xy 之间没有空位,即 x+1=y

通过情况一的讨论,我们知道,如果 Alice 移动后,留给 Bob 的是一个「有空位」的局面,那么 Bob 是必胜的。

因此,为了不让 Bob 必胜,Alice 必须保证,移动后,最右边的两个石子是没有空位的。对于 Bob 也同理。

因此,每回合,max(a) 只会减少 1。

由于游戏结束时 max(a)=n−1,所以一共有 a[n]−(n−1) 个回合。

因此,如果 a[n]−(n−1) 是奇数,或者说 a[n]−n 是偶数,那么 Alice 必胜,否则 Bob 必胜。

参考代码:

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

int a[300010];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);
    if (a[n] - a[n - 1] > 1) cout << "Alice";
    else if ((a[n] - n) & 1) cout << "Bob";
    else cout << "Alice";
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int T = 1;
    // cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}

“唉唉,不想博弈了”

H 求第k大用什么来着?

中等题

本题中的树是一棵以 1 为根的完全二叉树,按节点编号从 1 到 N 截断,其中编号为 i 的节点,其父节点为 i 除以 2 取整。对于给定节点 X,与其距离恰好为 K 的节点可以分为两类:第一类是以 X 为根向下走得到的节点;第二类是先从 X 向上走若干步,再从某个祖先节点的另一侧子树向下扩展得到的节点。

对于第一类情况,当 K 不过大时,以 X 为根向下走 K 步所能到达的节点编号构成一个连续区间,从 X 乘以 2 的 K 次方开始,到该值加上 2 的 K 次方减 1 为止,与 N 取交即可得到合法节点数量。

对于第二类情况,沿着 X 的父节点方向向上枚举,当向上走的步数等于 K 时,对应的祖先节点本身计入答案;当向上走的步数小于 K 时,可以从该祖先节点的兄弟子树向下继续走若干层,形成一个同样连续的编号区间,对该区间与 N 取交并计数即可。由于树的高度最多为对数级,只需沿父链向上处理即可完成统计。

整个过程无需显式建树,仅通过编号区间计算完成统计,适用于 N 高达 1e18 的情况。单个测试用例的时间复杂度为 O(log N),空间复杂度为 O(1)。

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define int long long
#define pb push_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define ff first
#define ss second
#define bb begin()
#define ee end()
#define pii pair<int,int>
#define lc p<<1
#define rc p<<1|1
#define endl "\n"
using namespace std;
const int eps=62;
void solve()
{
	int n,x,k;cin>>n>>x>>k;
	__int128 p=-1,t=k;
	if(k==0){
		cout<<1<<endl;
		return ;
	}
	if(k<=eps) p=1ll<<k;
	int res=0;
	__int128 l=x*p,r=min((__int128)n,l+p-1);
	if(p!=-1)res+=max((__int128)0,r-l+1);
	int cnt=-1;
	//cout<<res<<endl;
	while(x && k>=0){
		cnt++;
		if(cnt==t) res++;
		if(x==1) break;
		int cur=0;
		if(x%2==0) cur=x+1;
		else cur=x-1;
		p=-1;
		if(k-2<=eps && k-2>=0) p=1ll<<(k-2);
		l=cur*p,r=min((__int128)n,l+p-1);
		if(p!=-1)res+=max((__int128)0,r-l+1);
		x/=2;
		k--;
	}
	cout<<res<<endl;

}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T=1;
	cin>>T;
	while(T--)
	{
		solve();
	}
	return 0;
}

I 两个序列?为什么不让我模拟!

较难题

本题需要维护两个长度为 N 的数列 A 和 B,支持区间加法操作以及区间内 A[i] 与 B[i] 乘积之和的查询。若直接对区间逐元素进行修改或统计,单次操作的时间复杂度为 O(N),在 N 和 Q 均达到 2e5 的数据范围下显然无法通过,因此必须使用高效的数据结构进行维护。

这是一个经典的高阶数据结构问题,可以使用线段树来解决。在线段树的每个节点中,维护区间内 A[i] 的元素和、B[i] 的元素和,以及 A[i] 与 B[i] 乘积之和,并分别设置针对 A 和 B 的区间加懒标记。对于区间加 A 的操作,区间内 A 的元素和增加相应值,同时乘积和增加当前区间 B 的元素和乘以增量;对 B 的区间修改同理。通过合理设计懒标记的下传与合并规则,可以保证多次修改叠加后的结果正确。区间查询时直接返回对应节点维护的乘积和即可。

该方法避免了逐元素模拟操作,将每次查询与修改的时间复杂度降低至 O(log N),空间复杂度为 O(N),能够高效处理所有给定数据范围。本题涉及区间信息耦合与懒标记传递,是线段树中较为典型但实现难度偏高的一类问题,新生选手可在掌握线段树基础操作后再回头完成本题,会更有收获。

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define int long long
#define pb push_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define ff first
#define ss second
#define bb begin()
#define ee end()
#define pii pair<int,int>
#define lc p<<1
#define rc p<<1|1
using namespace std;
const int N=2e5+10,mod=998244353;
struct node{
	int l,r,suma,sumb,sum,lazya,lazyb;
}tr[N*4];
int a[N],b[N];
void pushup(int p)
{
	tr[p].suma=(tr[lc].suma+tr[rc].suma)%mod;
	tr[p].sumb=(tr[lc].sumb+tr[rc].sumb)%mod;
	tr[p].sum=(tr[lc].sum+tr[rc].sum)%mod;
}
void pushdown(int p)
{
	if(tr[p].lazya)
	{
		int x=tr[p].lazya;
		tr[lc].suma=(tr[lc].suma+(tr[lc].r-tr[lc].l+1)*x)%mod;
		tr[lc].sum=(tr[lc].sum+tr[lc].sumb*x)%mod;
		tr[lc].lazya+=x;tr[lc].lazya%=mod;
		tr[rc].suma=(tr[rc].suma+(tr[rc].r-tr[rc].l+1)*x)%mod;
		tr[rc].sum=(tr[rc].sum+tr[rc].sumb*x)%mod;
		tr[rc].lazya+=x;tr[rc].lazya%=mod;
		tr[p].lazya=0;
	}
	if(tr[p].lazyb)
	{
		int x=tr[p].lazyb;
		tr[lc].sumb=(tr[lc].sumb+(tr[lc].r-tr[lc].l+1)*x)%mod;
		tr[lc].sum=(tr[lc].sum+tr[lc].suma*x)%mod;
		tr[lc].lazyb+=x;tr[lc].lazyb%=mod;
		tr[rc].sumb=(tr[rc].sumb+(tr[rc].r-tr[rc].l+1)*x)%mod;
		tr[rc].sum=(tr[rc].sum+tr[rc].suma*x)%mod;
		tr[rc].lazyb+=x;tr[rc].lazyb%=mod;
		tr[p].lazyb=0;
	}
}
void updata1(int p,int l,int r,int x)
{
	if(tr[p].l>=l && tr[p].r<=r)
	{
		tr[p].suma=(tr[p].suma+(tr[p].r-tr[p].l+1)*x)%mod;
		tr[p].sum=(tr[p].sum+tr[p].sumb*x)%mod;
		tr[p].lazya+=x;tr[p].lazya%=mod;
		return ;
	}
	int mid=(tr[p].l+tr[p].r)/2;
	pushdown(p);
	if(l<=mid) updata1(lc,l,r,x);
	if(r>mid) updata1(rc,l,r,x);
	pushup(p);
}
void updata2(int p,int l,int r,int x)
{
	if(tr[p].l>=l && tr[p].r<=r)
	{
		tr[p].sumb=(tr[p].sumb+(tr[p].r-tr[p].l+1)*x)%mod;
		tr[p].sum=(tr[p].sum+tr[p].suma*x)%mod;
		tr[p].lazyb+=x;tr[p].lazyb%=mod;
		return ;
	}
	int mid=(tr[p].l+tr[p].r)/2;
	pushdown(p);
	if(l<=mid) updata2(lc,l,r,x);
	if(r>mid) updata2(rc,l,r,x);
	pushup(p);
}
int query(int p,int l,int r)
{
	if(tr[p].l>=l &&tr[p].r<=r)
	{
		return tr[p].sum;
	}
	int mid=(tr[p].l+tr[p].r)/2,sum=0;
	pushdown(p);
	if(l<=mid) sum=(sum+query(lc,l,r))%mod;
	if(r>mid) sum=(sum+query(rc,l,r))%mod;
	return sum;
}
void build(int p,int l,int r)
{
	tr[p]={l,r,a[l]%mod,b[l]%mod,a[l]*b[l]%mod,0,0};
	if(l==r) return ;
	int mid=(l+r)/2;
	build(lc,l,mid);
	build(rc,mid+1,r);
	pushup(p);
}
/*每个节点需要维护数组a和suma,数组b和sumb,以及乘积之和sum,考虑两个操作带来的影响
操作1,l~r内的suma+=x*(r-l+1),sum+=(l~r)sumb*x
操作2,l~r内的sumb+=x*(r-l+1),sum+=(l~r)suma*x
因此正常区修区查即可,需要全局取模,否则比如lazya被加到了1e14,而一节点的最大长度是2e5,
他们相乘会超过1e18,就出问题了
另外两个懒标记都有的话,考虑p子节点lc,首先suma,sumb与修改顺序无关,
因为他们只依赖于原值和长度,这无关懒标记,而sum,这里lazya用了旧sumb计算,
lazyb这里用了新的suma计算,看样子似乎是很不对的,但是实际上是正确的,怎么回事呢?其实这里非常的巧妙
求和sum=(a+x)*(b+y)=a*b+b*x+a*y+x*y*len=sumold+suma*x+sumb*y+x*y*len
而我们的计算方式lazya时sum=sumold+sumbold*x,suma=(sumaold+len*x)
计算lazyb时sum=(sumold+sumbold*x)+y*(sumaold+len*x)=sumold+sumbold*x+sumaold*y
+len*x*y,恰好相等,非常巧妙地pushdown成功了
*/
void solve()
{
	int n,q;cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	build(1,1,n);
	while(q--)
	{
		int op,l,r;cin>>op>>l>>r;
		if(op==1)
		{
			int x;cin>>x;
			updata1(1,l,r,x);
		}
		else if(op==2)
		{
			int x;cin>>x;
			updata2(1,l,r,x);
		}
		else
		{
			cout<<query(1,l,r)<<endl;
		}
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T=1;
	while(T--)
	{
		solve();
	}
	return 0;
}

J 最大化美丽比

假设B/C最大是x

那么一定满足B/C>=x, 则满足B-C*x>=0,即可以推出以下公式

将边的权值改写为w=b-x*c。于是问题变成:

是否存在一条从 1 到 N 的简单路径,使得 路径权值和 ≥ 0

如果存在,说明真实答案 ≥ x 否则 < x

考虑到可以二分这个x,通过check来检查该x是否满足上述不等式,该图本身是一个有向无环图,check的方法是用dp。

double INF = 1e18;
struct Edge {
    int to;
    int b, c; 
};
int N, M;
vector<vector<Edge>> g;

// 判定函数:判断是否存在一条路径,使得 b - x * c 的权值和 >= 0
bool check(double x) {
    vector<double> dp(N + 1, -INF);//用最小值初始化dp值
    dp[1] = 0;
    for (int u = 1; u <= N; u++) {
        if (dp[u] < -1e17) continue;
        for (auto &e : g[u]) {
            dp[e.to] = max(dp[e.to], dp[u] + e.b - x * e.c);
        }
    }
    return dp[N] >= 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;
    g.assign(N + 1, vector<Edge>());
    for (int i = 0; i < M; i++) {
        int u, v, b, c;
        cin >> u >> v >> b >> c;
        g[u].push_back({v, b, c});
    }

    double L = 0, R = 1e4; 
    for (int iter = 0; iter < 100; iter++) { 
        double mid = (L + R) / 2;
        if (check(mid)) L = mid;
        else R = mid;
    }
    printf("%.9f\n", L);

    return 0;
}

K New Place,New Start

题目类型及难度定位:字符串、贪心,难度(4/10)星

首先有个结论:若 S 中每个字母的个数都与 T 中这个字母的个数相等,则一定有解,否则无解。

如果有数量不相等的字母,则显然怎么操作都不可能有解。

否则,我们就可以考虑把 S 开头所有对不上 T 的字符都通过操作插到后面。设 S 中为 T 的子序列的最长后缀子串的长度为 l,则答案为 (Nl),也就是保持后面 l 位不动,把前面 (Nl) 位插到这 l 位中间去,共需要 (Nl) 次操作。容易发现这种做法在字母数相等的情况下一定有解,而且不会有比这更优的方法了。

匹配最长子序列是越早配上越好,所以可以 O(N) 求出 l

参考代码:

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

void solve() {
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    map<char, int> mp1, mp2;
    for (int i = 0; i < n; i++) {
        mp1[s[i]]++;
        mp2[t[i]]++;
    }
    if (mp1 != mp2) {
        cout << "-1";
        return ;
    }
    int cnt = 0, idx = n - 1;
    for (int i = n - 1; i >= 0; i--) {
        if (s[idx] == t[i]) idx--, cnt++;
    }
    cout << n - cnt;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int T = 1;
    //cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}

"Attention is All You Need"

L 再见了,所有的XCPC

题目类型及难度定位:模拟题,难度(2/10)星

本题最大的难度在于读题,题读清楚后很容易解决。

MAGI System只能预测到某一时刻**“同意离开”** 和 “反对离开” 的票量。MAGI System预测到的这一时刻的投票结果是否已经确定仅需判断 当前时刻**“同意离开”** 和 “反对离量较少的票数 加上 尚未被投出的票数,看能否大于当前时刻**“同意离开”** 和 “反对离量较多的票数,若能大于,则结果尚未确定,输出No,否则输出Yes。

参考代码:

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

void solve() {
    int x, a, b;
    cin >> x >> a >> b;
    if (min(a, b) + x - a - b > max(a, b)) cout << "No";
    else cout << "Yes";
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int T = 1;
    //cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}

“再见了,所有的XCPC”

M 以我为终

题目类型及难度定位:数学、微积分,防AK题,测挂题(?)。难度(10/10)星

题如其名,最后的一题,终焉之题。

参考代码:

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

const int mod = 1e9 + 7;

int ksm(int a, int b) {
    int c = 1;
    while (b) {
        if (b & 1)c = c * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return c;
}

void solve() {
    int n, ans = 0;
    cin >> n;
    for (int k = 0; k <= n - 1; k++) {
        ans = (ans + ksm(ksm(3, k) * n % mod * (n - k) % mod, mod - 2)) % mod;
    }
    cout << ans* ksm(3, mod - 2) % mod;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

后记:

本题是本次比赛的防AK题,也应该是最难的一道题。

如果你能凭自己的实力做出来本题,恭喜你,你很有天赋也很努力,前途大有可为;

如果你没能做出来本题也别灰心,一般XCPC比赛都会有一道巨难的题来防止AK,无论比赛的结果如何,开心就好,享受每次比赛,你能参加今天的比赛就已经很优秀了,继续保持学习动力,相信将来也同样能大有所为;

如果你做出来了该题但不是凭借自己的实力,而是靠“天赋与努力”、或者一些科技,希望你在以后的比赛中不要再使用这些科技,争取用自己真正的实力取得好成绩。

(注:AK(All-Killed),中文名“全杀”,是信息学竞赛术语,指选手在比赛中完美通过所有题目并获得每题Accepted(AC)的判定结果)

“以我为始,以我为终”