kmjp's blog

競技プログラミング参加記です

yukicoder : No.2903 A Round-the-World Trip with the Tent

yukicoder

なるほど…。
https://yukicoder.me/problems/no/2903

問題

正整数N,Kが与えられる。
[0,1]の値xを取る関数f(x)は以下のように定義される。
{\displaystyle f(x) = \begin{eqnarray} \left\{ \begin{array}{ll} 2^K x^K & (0 \le x \le 1/2) \\ 2^K (1-x)^K & (1/2 \lt x \le 1) \\ \end{array} \right. \end{eqnarray} }

f_{K}^N(x) = xかつn＜Nにおいて f_{K}^n(x) \neq x となるxは何通りか。

解法

まず、 f_{K}^N(x) = xだけ考える。これを満たすxの個数をg(N)とする。
(0,1)の範囲において、f(y)=xとなるyは、1/2以下と1/2より大きな2通りが考えられる。計2^Nパターンそれぞれで、 f_{K}^N(x) = xとなるxがある。
よってg(N)=2^Nである。

あとは約数包除の要領で、N回未満で元の値に戻るケースを取り除こう。

追加で、N=1かつKが2以上の場合、例外的にf_K^N(0)=0となるが上記では漏れるので追加が必要。

ll N,K;
const ll mo=998244353;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll dp[1010101];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K>>N;
	ll p=modpow(2,N);
	for(i=1;i<=N;i++) {
		dp[i]=(dp[i]+modpow(2,i))%mo;
		for(j=i*2;j<=N;j+=i) dp[j]+=mo-dp[i];
	}
	
	
	ll ret=dp[N];
	if(K>1&&N==1) ret++;
	
	cout<<ret<<endl;
	
}

まとめ

うーむ。