简单计数

NC24639. 简单计数

描述

$\mathfrak{the} \,\, \mathfrak{wind} \,\, \mathfrak{and} \,\, \mathfrak{rain} \,\, \mathfrak{is} \,\, \mathfrak{in} \,\, \mathfrak{my} \,\, \mathfrak{way} \,\, \mathfrak{and} \,\, \mathfrak{never} \,\, \mathfrak{going} \,\, \mathfrak{away}$
你在一个有 n 个城市的国家中行走，城市从 1 到 n 依次编号
任意两个城市之间都有一条双向道路可以通行，且你可以花一天的时间从当前所在的城市到达任意一个别的城市
由于你比较闲的无聊，所以你不会连续两天都呆在同一个城市，也就是说每天你所在的城市都不相同（这句话的意思是，对于相邻的两天，你所在的城市应该不同）
一开始你在 1 号城市，求经过 k 天后你回到 1 号城市的方案数

当然如果不存在任意一种方案就输出 0 就好了

输入描述

第一行两个整数 n,k

输出描述

一行一个整数表示答案对 998244353 取模后的结果

示例1

输入:

1 1

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 6ms, 内存消耗: 488K, 提交时间: 2019-05-29 19:55:18

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll p=998244353;
ll qw(ll x, ll y, ll p){
	int re=1%p;
	for(;y;y/=2){
		if(y%2==1){
			re=re*x%p;
		}
		x=x*x%p;
	}
	return re;
}
ll n,k;
int main(){
	cin>>n>>k;
	ll o=1;
	if(k%2==1){
		o=-1;
	}else{
		o=1;
	}
	ll cnt=((o*(n-1)+qw(n-1,k,p)+p)%p*qw(n,p-2,p))%p;
	cout<<cnt<<endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 376K, 提交时间: 2020-01-17 10:33:41

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

long long i,j,n,k,mod=998244353;
int fastpow(long long a,long long b)
{
	long long s=1;
	for(;b;b>>=1,a=a*a%mod)if(b&1)s=s*a%mod;
	return s;
}
int main()
{ 
	scanf("%lld%lld",&n,&k);
	i=(fastpow(n-1,k)-(1-n)*(k&1?-1:1)+mod)%mod,j=fastpow(n,mod-2);
	printf("%lld\n",i*j%mod);
	return 0;
}