Submission #41095734

---

Source Code Expand

#include<atcoder/all>

#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 op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
using namespace atcoder;
typedef vector<ll> Poly;
const ll MAXN=5e4+10,mod=998244353;
ll mypow(ll a,ll n){
	if(!n)return 1;
	ll tmp=mypow(a,n/2);tmp=tmp*tmp%mod;
	if(n&1)tmp=tmp*a%mod;return tmp;
}
ll myinv(ll a){
	return mypow(a,mod-2);
}

void add(ll& x,ll y){x=(x+y)%mod;}
void sub(ll& x,ll y){x=(x-y+mod)%mod;}
ll addv(ll x,ll y){return (x+y)%mod;}
ll subv(ll x,ll y){return (x-y+mod)%mod;}

Poly operator+(const Poly& a,const Poly& b){
	Poly r(max(a.size(),b.size()),0);
	rep(i,0,(int)(r.size())-1){
		if(i<a.size())add(r[i],a[i]);
		if(i<b.size())add(r[i],b[i]);
	}
	return r;
}

ll k,n,a[MAXN],f[MAXN];

void adjust(Poly& p,int k){
	int i;
	for(i=k;i<p.size();i+=2)p[i/2]=p[i];
	p.resize(i/2);
}

void solve(Poly p,Poly q,ll n){
	while(n){
		int k=(n&1);n>>=1;

		Poly rq=q,op=p,ep=p;
		for(int i=1;i<rq.size();i+=2)rq[i]=subv(0,rq[i]);

		q=convolution(q,rq);
		op=convolution(op,rq);
		ep=convolution(ep,rq);

		adjust(q,0);
		adjust(op,1);
		adjust(ep,0);

		if(!k)p=ep;
		else p=op+ep;
		
	}

	ll ans=(p.size())?(p[0]*myinv(q[0])%mod):(0);
	cout<<ans<<endl;
}

int main(){
	cin>>k>>n;
	rep(i,1,k)f[i]=a[i-1]=1;

	Poly p(k),q(k+1);
	
	q[0]=1;rep(i,1,k)q[i]=(mod-1),p[i-1]=1;
	p=convolution(p,q);
	p.resize(k);

	//f=p/q
	solve(p,q,n);

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll mypow(ll, ll)’:
./Main.cpp:23:2: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   23 |  if(n&1)tmp=tmp*a%mod;return tmp;
      |  ^~
./Main.cpp:23:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
   23 |  if(n&1)tmp=tmp*a%mod;return tmp;
      |                       ^~~~~~
./Main.cpp: In function ‘Poly operator+(const Poly&, const Poly&)’:
./Main.cpp:37:7: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   37 |   if(i<a.size())add(r[i],a[i]);
      |      ~^~~~~~~~~
./Main.cpp:38:7: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   38 |   if(i<b.size())add(r[i],b[i]);
      |      ~^~~~~~~~~
./Main.cpp: In function ‘void adjust(Poly&, int)’:
./Main.cpp:47:11: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   47 |  for(i=k;i<p.size();i+=2)p[i/2]=p[i];
      |          ~^~~~~~~~~
./Main.cpp: In function ‘void solve(Poly, Poly, ll)’:
./Main.cpp:56:16: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   56 |   for(int i=1;i<rq.size();i+=2)rq[i]=subv(0,rq[i]);
      |               ~^~~~~~~~~~

Judge Result