本文共 3394 字，大约阅读时间需要 11 分钟。
唔，D：概率最多是 $ \frac{1}{2} $ ，在n==1000的时候这个阈值大概是7284，O(7284n)即可
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #define eps 1e-715 #define INF 0x3f3f3f3f16 #define MOD 100000000717 #define rep0(j,n) for(int j=0;j nxt)24 #define max(a,b) (a>b?a:b)25 #define min(a,b) (a
E：考虑一下最原始的nim游戏里每堆石子数量的意义，它的意思是这堆石子可以在1,2,3..n次内取完，并且这个信息支持减法，然后这题里的这个规则好像也是这个意思，事实上每一个有这种限制的石碓可以映射到一个原来的石碓上，即 $ sg(n) = t (\sum_{i=1}^{t} \leqslant n < \sum_{i=1}^{t+1}) $ ，然后直接异或起来即可
F：唔，枚举架子的数量，然后对于某一个确定的架子数量n，分类大力讨论，插板法计数即可，总数直接插板，合法的数量就是先从w里减掉堆数*h再插板
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #define eps 1e-715 #define INF 0x3f3f3f3f16 #define MOD 100000000717 #define rep0(j,n) for(int j=0;j nxt)24 #define print_runtime printf("Running time:%.3lfs\n",double(clock())/1000.0)25 #define TO(j) printf(#j": %d\n",j);26 //#define OJ27 using namespace std;28 const int MAXINT = 100010;29 const int MAXNODE = 100010;30 const int MAXEDGE = 2*MAXNODE;31 char BUF,*buf;32 int read(){33 char c=getchar();int f=1,x=0;34 while(!isdigit(c)){ if(c=='-') f=-1;c=getchar();}35 while(isdigit(c)){x=x*10+c-'0';c=getchar();}36 return f*x;37 }38 char get_ch(){39 char c=getchar();40 while(!isalpha(c)) c=getchar();41 return c;42 }43 //------------------- Head Files ----------------------//44 45 ll cnt_t,cnt_g;46 ll fact[100010],df[100010];47 ll f,w,h;48 ll fp(ll b,ll u){49 ll ans = 1;50 for(;u;b=b*b%MOD,u>>=1) if(u&1) ans=ans*b%MOD;51 return ans;52 }53 ll C(ll n,ll m){54 if(m>n) return 0;55 return (fact[n]*df[m]%MOD)*df[n-m]%MOD;56 }57 void add(ll &a,ll b){58 a=(a+b)%MOD;59 }60 void get_input();61 void work();62 int main() {63 get_input();64 work();65 return 0;66 }67 void work(){68 fact[0]=1;69 rep1(i,100000) fact[i]=fact[i-1]*i%MOD;70 rep0(i,100001) df[i] = fp(fact[i],MOD-2);71 //printf("%lld\n",df[0]);72 for(int i=1;1;i++){73 if(i>f+w||i>min(f,w)*2+1) break;74 75 if(i==1){76 if(f==0||w==0) cnt_t++;77 if(w==0||(f==0&&w>h)) cnt_g++;78 }else{79 if(i&1){80 add(cnt_t,C(f-1,i/2)*C(w-1,i/2-1));81 add(cnt_t,C(f-1,i/2-1)*C(w-1,i/2));82 add(cnt_g,C(f-1,i/2)*C(w-1-i/2*h,i/2-1));83 add(cnt_g,C(f-1,i/2-1)*C(w-1-(i/2+1)*h,i/2));84 }else{85 add(cnt_t,(C(f-1,i/2-1)*C(w-1,i/2-1)%MOD)*2);86 add(cnt_g,(C(f-1,i/2-1)*C(w-1-(i/2)*h,i/2-1)%MOD)*2);87 }88 }89 //printf("%d %lld\n",i,cnt_t);90 }91 //printf("%lld\n",cnt_t);92 printf("%lld\n",cnt_g*fp(cnt_t,MOD-2)%MOD);93 }94 void get_input(){95 f=read();w=read();h=read();96 }
转载于:https://www.cnblogs.com/LoveYayoi/p/6979337.html
