Submission #2945091

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <set>
#include <functional>
#include <map>
#include <cmath>
#define MX 2005
#define MOD 998244353

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

set <ll> st;
set <ll>::iterator it;
map <ll,int> mp;
queue <ll> que;
vector <int> to[MX];
ll nm[MX][MX];
ll mul[MX][MX];
ll cur[MX][MX];
ll now;
int W,H;
int sz;

void dfs(int S,int pos,int T)
{
	if(pos==W)
	{
		now|=1LL<<T;
	}
	else
	{
		if(!(S>>pos&1)) dfs(S,pos+1,T);
		else
		{
			if(pos==0||!(T>>(pos-1)&1))
			{
				dfs(S,pos+1,T|(1<<pos));
			}
			if(pos+1<W&&(S>>(pos+1)&1))
			{
				dfs(S,pos+2,T);
			}
		}
	}
}
void solve(ll t)
{
	if(t==1)
	{
		for(int i=0;i<sz;i++)
		{
			for(int j=0;j<sz;j++)
			{
				mul[i][j]=nm[i][j];
			}
		}
		return;
	}
	solve(t/2);
	for(int i=0;i<sz;i++)
	{
		for(int j=0;j<sz;j++)
		{
			cur[i][j]=0;
			for(int k=0;k<sz;k++)
			{
				cur[i][j]+=mul[i][k]*mul[k][j]%MOD;
				if(cur[i][j]>=MOD) cur[i][j]-=MOD;
			}
		}
	}
	for(int i=0;i<sz;i++)
	{
		for(int j=0;j<sz;j++)
		{
			mul[i][j]=cur[i][j];
		}
	}
	if(t%2==1)
	{
		for(int i=0;i<sz;i++)
		{
			for(int j=0;j<sz;j++)
			{
				cur[i][j]=0;
				for(int k=0;k<sz;k++)
				{
					cur[i][j]+=mul[i][k]*nm[k][j]%MOD;
					if(cur[i][j]>=MOD) cur[i][j]-=MOD;
				}
			}
		}
		for(int i=0;i<sz;i++)
		{
			for(int j=0;j<sz;j++)
			{
				mul[i][j]=cur[i][j];
			}
		}
	}
}
int main()
{
	scanf("%d %d",&W,&H);
	st.insert(1);
	sz=0;
	mp[1]=sz++;
	que.push(1);
	while(!que.empty())
	{
		ll v=que.front();
		que.pop();
		for(int S=0;S<1<<W;S++)
		{
			now=0;
			for(int T=0;T<1<<W;T++)
			{
				if((v>>T&1)&&((S|T)==S))
				{
					dfs(S-T,0,0);
				}
			}
			if(now>0)
			{
				if(st.count(now)==0)
				{
					st.insert(now);
					mp[now]=sz++;
					que.push(now);
				}
				nm[mp[v]][mp[now]]++;
			}
		}
	}
	solve(H);
	ll ret=0;
	for(it=st.begin();it!=st.end();it++)
	{
		ll S=*it;
		if(S>>0&1)
		{
			ret+=mul[0][mp[S]];
			if(ret>=MOD) ret-=MOD;
		}
	}
	printf("%lld\n",ret);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:110:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&W,&H);
                      ^

Judge Result