提出 #76310030

---

ソースコード 拡げる

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define eb emplace_back
#define VI vector<int>
#define VII vector<pii>
#define VL vector<ll>
#define VLL vector<pll>
#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 LOCAL true

using namespace std;
bool st;
const bool MUL=false;

const int N=705;
int n;
ll p,c[N][N],p2[N],pval[N][N],q[N],f[N];

void clr(){
	return;
}
void solve(){
	cin>>n>>p;
	rep(i,0,n){c[i][0]=1;rep(j,1,i)c[i][j]=(c[i-1][j-1]+c[i-1][j])%p;}
	p2[0]=1;rep(i,1,n)p2[i]=p2[i-1]*2%p;
	rep(k,0,n-1){
		ll x=p2[k],nx=(p-x)%p;q[0]=1;
		rep(a,1,n-k){
			ll s=0;
			rep(i,0,a-1)s=(s+c[a-1][i]*q[i])%p;
			q[a]=nx*s%p;pval[a][k]=(p-q[a])%p;
		}
	}
	f[0]=1;
	rep(m,1,n){ll s=0;rep(a,1,m)s=(s+f[m-a]*pval[a][m-a]%p*c[m][a])%p;f[m]=s;}
	ll ans=0;
	rep(m,0,n)ans=(ans+c[n][m]*f[m])%p;
	cout<<ans<<"\n";
	return; 
}

bool ed;
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int tc=1;if(MUL){cin>>tc;}while(tc--)clr(),solve();
// 	cerr<<"time:"<<clock()<<"ms.\n";
// 	cerr<<fixed<<setprecision(4)<<"memory:"<<(1.0*(&st-&ed)/1048576.0)<<"MB.\n";
	return 0;
}

提出情報

ジャッジ結果