提出 #48248921

---

ソースコード 拡げる

// LUOGU_RID: 138549584
#include<bits/stdc++.h>
#include<atcoder/modint>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef atcoder::modint998244353 mint;

#define rep(i,l,r) for(int i(l);i<=(r);++i)
#define per(i,r,l) for(int i(r);i>=(l);--i)
#define eb emplace_back
#define File(filename) freopen(filename ".in","r",stdin),freopen(filename ".out","w",stdout)

#ifdef EXODUS
	#define Debug(...) fprintf(stderr,__VA_ARGS__)
#else
	#define Debug(...) 0
#endif

//=========================================================================================================
// Something about IO

template<typename T>
void read(T &x){
	x=0;T flg=1;
	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')flg=-1;ch=getchar();}
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	x*=flg;
}
template<typename T,typename... Args>
void read(T &x,Args &...args){read(x),read(args...);}

//=========================================================================================================
// Define the global variables here.

bool membg=0;
constexpr int N=1e6+7,S=(1<<19)+7;
int n,m,K,pos[N],lim[S];
bool invaild[S];
ll a[N],b[N];
mint inv[N],f[S],C[20][20],val[20],ans;

bool memed=0;

//=========================================================================================================
// Code here.

mint calc(int x,int y){
	if(x<y)return (mint)0;
	mint res=0;
	for(int i=0;i<=y;i++)res+=C[y][i]*(((y-i)&1)?-1:1)*mint(i).pow(x);
	for(int i=1;i<=y;i++)res=res*inv[i];
	return res;
}


void solve(){
	read(n,m,K);
	inv[0]=1;for(int i=1;i<=K;i++)inv[i]=(mint)1/i;
	for(int i=(C[0][0]=1).val();i<=K;i++)
		for(int j=(C[i][0]=1).val();j<=i;j++)
			C[i][j]=C[i-1][j]+C[i-1][j-1];
	for(int i=1;i<=n;i++)read(a[i]);
	for(int i=1;i<=n;i++)read(b[i]);
	set<pair<ll,int>>st;
	for(int i=1;i<=n;i++)st.emplace(a[i],i);
	for(int i=1;i<=n;i++){
		auto it=st.lower_bound({b[i],0});
		pos[i]=it->second;st.erase(it);
	}
	for(int i=1,s=0,t=0;i<n;i++,s=0,t=0){
		ll now=b[i],nxt=b[i+1];
		for(int k=0;k<K;k++){
			if(now%10<nxt%10)s|=(1<<k);
			if(now%10>nxt%10)t|=(1<<k);
			now/=10,nxt/=10;
		}
		lim[s]|=t;
		if(pos[i]>pos[i+1])
			invaild[s]=true;
	}
	// for(int s=0;s<(1<<K);s++)printf("%d\n",lim[s]);
	// for(int s=0;s<(1<<K);s++)printf("%d\n",invaild[s]);
	for(int s=0;s<(1<<K);s++)
		for(int k=0;k<K;k++)
			if((s>>k)&1)
				lim[s]|=lim[s^(1<<k)],invaild[s]|=invaild[s^(1<<k)];
	f[0]=1;
	for(int s=0;s<(1<<K);s++)
		for(int k=0;k<K;k++)
			if((!(s&(1<<k)))&&(!((lim[((1<<K)-1)^s]>>k)&1)))
				f[s|(1<<k)]+=f[s];
	// for(int s=0;s<(1<<K);s++)printf("%d\n",f[s].val());
	for(int i=0;i<=K;i++)val[i]=calc(m,i);
	// for(int i=0;i<=K;i++)printf("%d\n",val[i]);
	for(int s=0;s<(1<<K);s++)
		if(!invaild[((1<<K)-1)^s])
			ans+=f[s]*val[__builtin_popcount(s)];
	printf("%d\n",ans.val());
	return;
}


//=========================================================================================================

signed main(){
	Debug("%.3lfMB\n",fabs(&memed-&membg)/1024.0/1024.0);
	int timbg=clock();
	int T=1;
	while(T--)solve();
	int timed=clock();
	Debug("%.3lfs\n",1.0*(timed-timbg)/CLOCKS_PER_SEC);
	fflush(stdout);
	return 0;
}

提出情報

コンパイルエラー

Main.cpp: In function ‘int main()’:
Main.cpp:20:28: warning: statement has no effect [-Wunused-value]
   20 |         #define Debug(...) 0
      |                            ^
Main.cpp:111:9: note: in expansion of macro ‘Debug’
  111 |         Debug("%.3lfMB\n",fabs(&memed-&membg)/1024.0/1024.0);
      |         ^~~~~
Main.cpp:20:28: warning: statement has no effect [-Wunused-value]
   20 |         #define Debug(...) 0
      |                            ^
Main.cpp:116:9: note: in expansion of macro ‘Debug’
  116 |         Debug("%.3lfs\n",1.0*(timed-timbg)/CLOCKS_PER_SEC);
      |         ^~~~~
Main.cpp:112:13: warning: unused variable ‘timbg’ [-Wunused-variable]
  112 |         int timbg=clock();
      |             ^~~~~
Main.cpp:115:13: warning: unused variable ‘timed’ [-Wunused-variable]
  115 |         int timed=clock();
      |             ^~~~~

ジャッジ結果