Codeforces Round #315 DIV1 B問題 (1000pt)
Codeforces Round #315 DIV2 D問題 (2250pt)
Problem description
$N$ 元の集合の上で定義された二項関係であって，対称律と推移律を満たすが，反射律を満たさないものは何個あるかを ${\rm mod}\ 1000000007\ (10^9+7)$ で求める問題．
もう少し説明を加えると，集合を $S$ と書き，二項関係は $\rho \subseteq S \times S$ であって，$(a,b) \in \rho$ のとき $a \sim b$ と書くことにする．
このとき，
反射律：${}^\forall x \in S, \;\; x \sim x$
対称律：${}^\forall x,y \in S, \;\; x \sim y \Rightarrow y \sim x$
推移律：${}^\forall x,y,z \in S, \;\; x \sim y$ かつ $y \sim z$ ならば $x \sim z$
である．
ちなみに，この $3$ つの性質を満たすものを同値関係というが，対称律と推移律があれば反射律を証明できるというよくある間違えが元ネタになっており，その以下の間違えた証明が紹介されている．
推移律より $a \sim b$ かつ $b \sim a$ なので，推移律より $a \sim a$ が任意の $a \in S$ に対して成り立つ．
間違えている証明がどんな時に間違えるのかがポイントで，$a \sim a$ を示すときに $a \sim b$ なる $b \in S$ が存在しないことがあるというのが間違えである．
逆に，$a \sim b$ なる $b \in S$ が存在したら $a \sim a$ となってしまう．
つまり，同値関係なので，$\sim$ で結ばれているグループ（等しいもののグループ）に別れることになるが，$1$ つの要素のみからなるグループは，自分自身と等しいかどうかの $2$ パターン考えられる．
また，数えるべきものは，$1$ つの要素のみからなるグループで自分自身と等しくないというものが存在する関係の数である．
よって，動的計画法で，（残りの要素の数，既に $1$ つの要素のみからなるグループで自分自身と等しくないものが存在するかどうか）を状態として，そのパターン数を数えていく．
時間計算量は $O(N^2)$ で，空間計算量は $O(N)$．
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar()
#define mypc(c) putchar(c)
#define ll long long
#define ull unsigned ll
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
#define MD 1000000007
int get_inv(ll a, int md){ll t=a,s=md,u=1,v=0,e;while(s){e=t/s;t-=e*s;u-=e*v;swap(t,s);swap(u,v);}if(u<0)u+=md;return u;}
struct mint{
static unsigned md, W, R, Rinv, mdninv, RR;
unsigned val;
mint(){}mint(int a){val=mulR(a);}mint(unsigned a){val=mulR(a);}mint(ll a){val=mulR(a);}mint(ull a){val=mulR(a);}
unsigned setmod(unsigned m){int i;unsigned t;W=32;md=m;R=(1ULL<<W)%md;RR=(ull)R*R%md;switch(m){case 104857601:Rinv=2560000;mdninv=104857599;break;case 998244353:Rinv=232013824;mdninv=998244351;break;case 1000000007:Rinv=518424770;mdninv=2226617417U;break;case 1000000009:Rinv=171601999;mdninv=737024967;break;case 1004535809:Rinv=234947584;mdninv=1004535807;break;case 1007681537:Rinv=236421376;mdninv=1007681535;break;case 1012924417:Rinv=238887936;mdninv=1012924415;break;case 1045430273:Rinv=254466304;mdninv=1045430271;break;case 1051721729:Rinv=257538304;mdninv=1051721727;break;default:Rinv=get_inv(R,md);mdninv=0;t=0;rep(i,W){if(t%2==0)t+=md,mdninv|=(1U<<i);t/=2;}}}
unsigned mulR(unsigned a){return(ull)a*R%md;}unsigned mulR(int a){if(a<0)a=a%md+md;return mulR((unsigned)a);}unsigned mulR(ull a){return mulR((unsigned)(a%md));}unsigned mulR(ll a){if(a<0)a=a%md+md;return mulR((unsigned)a);}
unsigned reduce(unsigned T){unsigned m=T*mdninv;unsigned t=(unsigned)((T+(ull)m*md)>>W);if(t>=md)t-=md;return t;}unsigned reduce(ull T){unsigned m=(unsigned)T*mdninv;unsigned t=(unsigned)((T+(ull)m*md)>>W);if(t>=md)t-=md;return t;}
unsigned get(){return reduce(val);}
mint&operator+=(mint a){val+=a.val;if(val>=md)val-=md;return*this;}mint&operator-=(mint a){if(val<a.val)val=val+md-a.val;else val-=a.val;return*this;}mint&operator*=(mint a){val=reduce((ull)val*a.val);return*this;}mint&operator/=(mint a){return*this*=a.inverse();}
mint operator+(mint a){return mint(*this)+=a;}mint operator-(mint a){return mint(*this)-=a;}mint operator*(mint a){return mint(*this)*=a;}mint operator/(mint a){return mint(*this)/=a;}
mint operator+(int a){return mint(*this)+=mint(a);}mint operator-(int a){return mint(*this)-=mint(a);}mint operator*(int a){return mint(*this)*=mint(a);}mint operator/(int a){return mint(*this)/=mint(a);}
mint operator+(ll a){return mint(*this)+=mint(a);}mint operator-(ll a){return mint(*this)-=mint(a);}mint operator*(ll a){return mint(*this)*=mint(a);}mint operator/(ll a){return mint(*this)/=mint(a);}
mint operator-(void){mint res;if(val)res.val=md-val;else res.val=0;return res;}
operator bool(void){return val!=0;}operator int(void){return get();}operator ll(void){return get();}
mint inverse(){int a=val,b=md,u=1,v=0,t;mint r;while(b){t=a/b;a-=t*b;swap(a,b);u-=t*v;swap(u,v);}if(u<0)u+=md;r.val=(ull)u*RR%md;return r;}
mint pw(ull b){mint a(*this),r;r.val=R;while(b){if(b&1)r*=a;b>>=1;a*=a;}return r;}
bool operator==(int a){return get()==a;}
bool operator!=(int a){return get()!=a;}
};
unsigned mint::md, mint::W, mint::R, mint::Rinv, mint::mdninv, mint::RR;
mint operator+(int a, mint b){return mint(a)+=b;}mint operator-(int a, mint b){return mint(a)-=b;}mint operator*(int a, mint b){return mint(a)*=b;}mint operator/(int a, mint b){return mint(a)/=b;}
mint operator+(ll a, mint b){return mint(a)+=b;}mint operator-(ll a, mint b){return mint(a)-=b;}mint operator*(ll a, mint b){return mint(a)*=b;}mint operator/(ll a, mint b){return mint(a)/=b;}
mint mval[10000], minv[10000];
void mint_init(int md=MD, mint val[]=mval, int vals=10000, mint inv[]=minv, int invs=10000){int i;val[0].setmod(md);val[0].val=0;REP(i,1,vals){val[i].val=val[i-1].val+mint::R;if(val[i].val >=md)val[i].val-=md;}inv[1].val=1;REP(i,2,invs){inv[i].val=md-((ll)(md/i)*inv[md%i].val%md);}REP(i,1,invs)inv[i].val=(ull)inv[i].val*mint::R%md;}
mint C[4444][4444];
mint dp1[4444], dp2[4444];
int main(){
int i, j, k, N;
mint_init();
rep(i,4444) C[i][0] = mval[1];
REP(i,1,4444) REP(j,1,4444) C[i][j] = C[i-1][j-1] + C[i-1][j];
dp1[0] = mval[1];
REP(k,1,4444){
dp1[k] = dp1[k-1];
dp2[k] = dp1[k-1] + dp2[k-1] + dp2[k-1];
REP(i,2,k+1){
dp1[k] += dp1[k-i] * C[k-1][i-1];
dp2[k] += dp2[k-i] * C[k-1][i-1];
}
}
reader(&N);
writerLn( (int)dp2[N] );
return 0;
}
Current time: 2024年04月24日23時03分03秒
Last modified: 2015年08月15日05時59分58秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF315 CF_Div1_B CF_Div2_D
トップページに戻る
Logged in as: unknown user (not login)