Submission #41183138

---

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 mod=998244353;
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;}
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);}

const int MAXN=20,d6=myinv(6),V=1e9;

struct Mat{
	ll a[MAXN][MAXN],n,m;
	Mat(int n=0,int m=0){
		memset(a,0,sizeof a);
		this->n=n,this->m=m;
	}
	void operator=(const Mat& m2){
		n=m2.n,m=m2.m;
		rep(i,1,n)rep(j,1,m)a[i][j] = m2.a[i][j];
	}

	void solve(int x,int y){ 
		if(x>n || y>=m)return;
		int r=-1;
		rep(i,x,n)if(a[i][y]){r=i;break;}
		if(r==-1)return solve(x,y+1);
		
		rep(i,1,m)swap(a[x][i],a[r][i]);
		rep(i,x+1,n)if(a[i][y]){
			ll k=a[i][y] * myinv(a[x][y])%mod;
			rep(j,1,m)sub(a[i][j],a[x][j] * k%mod);
		}
		return solve(x+1,y+1);
	}
	void calc(ll* f){
		per(i,n,1){
			int r=-1;
			rep(j,1,m-1)if(a[i][j]){r=j;break;}
			if(r==-1)continue;
			f[r-1] = a[i][m]*myinv(a[i][r])%mod;
			per(j,i-1,1)if(a[j][r]){
				sub(a[j][m],a[j][r]*f[r-1]%mod);
				a[j][r]=0;
			}
		}
	}
};
Mat operator*(const Mat x,const Mat y){
	Mat z(x.n,y.m);
	rep(i,1,x.n)rep(k,1,x.m)rep(j,1,y.m)add(z.a[i][j],x.a[i][k] * y.a[k][j]%mod);
	return z;
}
Mat mypow(const Mat x,int n){
	if(n==1)return x;
	Mat tmp=mypow(x,n/2);tmp=tmp*tmp;
	if(n&1)tmp=tmp*x;return tmp;
}

ll r;
typedef array<ll,2> pr;

pr calc(ll t){ //f = sum f*p g = sum (g+f)*p 
	ll f[10]={0},g[10]={0};
	f[0] = 1;
	rep(i,1,6){
		rep(j,0,i-1)add(f[i],f[j]*d6%mod),add(g[i],(g[j]+f[j])*d6%mod);
	}	
	if(t<=6)return {f[t],g[t]};
	Mat v(1,12),a(12,12);

	rep(i,1,6){
		v.a[1][i] = f[i],v.a[1][6+i] = g[i];
		if(i>1)a.a[i][i-1] = a.a[6+i][5+i] = 1;
		a.a[i][6] = a.a[i][12] = a.a[i+6][12] = d6;
	}

	v=v*mypow(a,t-6);
	return {v.a[1][6],v.a[1][12]};
}

pr calc(ll s,ll t){ 
	ll f[10]={0},g[10]={0};
	rep(i,0,t-s){
		pr tmp=calc(s+i);
		f[i] = tmp[0],g[i] = tmp[1];
	}
	t-=s;
	per(i,t,1){
		rep(j,0,i-1){
			sub(f[i],f[j]*d6%mod);
			sub(g[i],(g[j]+f[j])*d6%mod);
		}
	}
	return {f[t],g[t]};
}
//
ll p[MAXN],g[MAXN][MAXN],a[MAXN],b[MAXN],ans;

int main(){
	cin>>r;

	rep(i,0,5)p[i] = calc(r,r+i)[0];

	rep(i,0,5)rep(j,0,5)g[i][j] = calc(V-i,V-i+j)[0];

	Mat ma(6,7),mb(6,7);
	rep(i,0,5){
		ma.a[i+1][7] = p[i];
		ma.a[i+1][i+1] = 1;
		
		rep(j,1,5)sub(ma.a[i+1][j+1],g[j][i]);
	}

	ma.solve(1,1);
	ma.calc(a);

	rep(i,0,5){
		ll w=calc(r,r+i)[1];
		add(ans,w);
	}

	rep(i,1,5)rep(j,0,5){
		ll w=calc(V-i,V-i+j)[1];
		add(ans,w*a[i]%mod);
	}

	cout<<ans<<endl;
    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 ‘Mat operator*(Mat, Mat)’:
./Main.cpp:69:9: warning: implicitly-declared ‘constexpr Mat::Mat(const Mat&)’ is deprecated [-Wdeprecated-copy]
   69 |  return z;
      |         ^
./Main.cpp:35:7: note: because ‘Mat’ has user-provided ‘void Mat::operator=(const Mat&)’
   35 |  void operator=(const Mat& m2){
      |       ^~~~~~~~
./Main.cpp: In function ‘Mat mypow(Mat, int)’:
./Main.cpp:72:17: warning: implicitly-declared ‘constexpr Mat::Mat(const Mat&)’ is deprecated [-Wdeprecated-copy]
   72 |  if(n==1)return x;
      |                 ^
./Main.cpp:35:7: note: because ‘Mat’ has user-provided ‘void Mat::operator=(const Mat&)’
   35 |  void operator=(const Mat& m2){
      |       ^~~~~~~~
./Main.cpp:73:21: warning: implicitly-declared ‘constexpr Mat::Mat(const Mat&)’ is deprecated [-Wdeprecated-copy]
   73 |  Mat tmp=mypow(x,n/2);tmp=tmp*tmp;
      |                     ^
./Main.cpp:35:7: note: because ‘Mat’ has user-provided ‘void Mat::operator=(const Mat&)’
   35 |  void operator=(const Mat& m2){
      |       ^~~~~~~~
./Main.cpp:71:21: note:   initializing argument 1 of ‘Mat mypow(Mat, int)’
   71 | Mat mypow(const Mat x,int n){
      |           ~~~~~~~~~~^
./Main.cpp:73:31: warning: implicitly-declared ‘constexpr Mat::Mat(const Mat&)’ is deprecated [-Wdeprecated-copy]
   73 |  Mat tmp=mypow(x,n/2);tmp=tmp*tmp;
      |                               ^~~
./Main.cpp:35:7: note: because ‘Mat’ has user-provided ‘void Mat::operator=(const Mat&)’
   35 |  void operator=(const Mat& m2){
      |       ^~~~~~~~
./Main.cpp:66:25: note:   initializing arg...

Judge Result