Submission #39079357

---

Source Code Expand

#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;
const int MAXN=3010,MAXM=1.2e4+10,MAXL=1e7+10,LIM=1e7,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;
	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 fact[MAXL],rfact[MAXL];

void preSolve(){
	fact[0]=1;rep(i,1,LIM)fact[i]=fact[i-1]*i%mod;
	rfact[LIM]=myinv(fact[LIM]);per(i,LIM-1,0)rfact[i]=rfact[i+1]*(i+1)%mod;
}
ll C(ll n,ll m){
	if(m<0 || n<m)return 0;
	return fact[n]*rfact[m]%mod*rfact[n-m]%mod;
}
ll P(ll n){return (n%2)?(mod-1):(1);}

ll n,m,k;
ll ans;

ll sum[2][MAXN][MAXN*2]; //二维差分统计不等式解数
ll simple_sum[2][MAXN]; 

ll S(ll n,ll k){
	if(n==0)return k==0;
	//x1+x2+...+xn=k
	ll res=0;
	rep(i,0,n)if(i*(m+1)<=k){
		ll rest=k-i*(m+1),ways=C(n,i)*P(i)%mod*C(rest+n-1,n-1)%mod;
		add(res,ways);
	}
	return res;
}
ll S2[MAXM],S3[MAXM],T2[MAXM];

ll calc1(){
	ll res=0;
	rep(sum,0,min(k,4*m))if(even(sum)){
		rep(rsum,sum/2+1,sum){
			ll ways=T2[rsum]*S2[sum-rsum]%mod;
			add(res,ways);
		}
	}
	return res;
}
ll calc2(){
	ll res=0;
	rep(b,0,m)rep(d,0,b-1)if(b+d<=k){
		int c=d-b,rest=k-b-d;
		//|x1-x2| < -c 且 x1+x2 <= rest 且奇偶性固定的的方案数
		ll ways=S3[d];
		if(rest<=2*m){
			ways=ways*sum[odd((b+d))][-c-1][rest]%mod;
		}else{
			ways=ways*simple_sum[odd((b+d))][-c-1]%mod;
		}
		
		
		add(res,ways);
	}
	return res;
}
namespace GF{
	ll F[MAXL],G[MAXL];

	void pre(){	
		rep(i,0,n){
			if((m+1)*i <= k){
				add(F[(m+1)*i],1ll*C(n,i)*P(i)%mod);
			}
		}
		rep(i,2,k)add(F[i],F[i-2]);

		rep(i,0,k)G[i]=C(i+n-1,i);

		if(even(k))rep(i,0,k)add(ans,F[i]*G[k-i]%mod);
		else rep(i,0,k-1)add(ans,F[i]*G[k-i-1]%mod);
	}
}
int main(){
	preSolve();

	cin>>n>>m>>k;

	GF::pre();

	//
	rep(x1,0,m)rep(x2,0,m){
		add(sum[odd((x1+x2))][abs(x1-x2)][x1+x2],1);
		add(simple_sum[odd((x1+x2))][abs(x1-x2)],1);
	}
	rep(flag,0,1){
		rep(i,1,m)add(simple_sum[flag][i],simple_sum[flag][i-1]);

		rep(i,0,m)rep(j,0,2*m){
			if(i)add(sum[flag][i][j],sum[flag][i-1][j]);
			if(j)add(sum[flag][i][j],sum[flag][i][j-1]);
			if(i&&j)sub(sum[flag][i][j],sum[flag][i-1][j-1]);
		}
	}

	rep(i,0,min(k,4*m))S2[i]=S(n-2,i),T2[i]=S(2,i),S3[i]=S(n-3,i);
	
	sub(ans,n*calc1()%mod);

	add(ans,n*calc2()%mod);

	cout<<ans<<endl;

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll mypow(ll, ll)’:
./Main.cpp:17:2: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   17 |  if(!n)return 1;ll tmp=mypow(a,n/2);
      |  ^~
./Main.cpp:17:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
   17 |  if(!n)return 1;ll tmp=mypow(a,n/2);
      |                 ^~

Judge Result