首页 > 其他 > 详细

test20181223

时间:2018-12-24 14:14:37      阅读:37      评论:0      收藏:0      [点我收藏+]

标签:pan   stdout   ....   会有   stack   math   sub   ati   long long   

Written with StackEdit.

T1

取石子(stone)

Description

\(n\)堆石子,第\(i\)堆有\(x_i\)个。
\(Alice\)\(Bob\)轮流取石子(先后手未定),\(Alice\)每次从一堆中取走\(a\)个,\(Bob\)每次从一堆中取走\(b\)个,无法操作者输。
不难发现只会有四种情况:\(Alice\)必胜;\(Bob\)必胜;先手必胜;后手必胜。
你需要选定若干堆石子(共有\(2^n\)种方案),\(Alice\)\(Bob\)只能在你选出的堆中取,问以上四种情况对应的方案数。对\(10^9+7\)取模。

Input

第一行三个整数\(n,a,b\),第二行\(n\)个整数\(x_1.....x_n\)

Output

一行四个整数,分别表示\(Alice\)必胜、\(Bob\)必胜、先手必胜和后手必胜的方案数,对\(10^9+7\)取模。

Sample Input

2 2 3
2 3

Sample Output

2 0 1 1

Explanation

选定空集时后手必胜,选定{\(2\)}时\(Alice\)必胜,选定{\(3\)}时先手必胜,选定{\(2,3\)}时\(Alice\)必胜。

HINT

对于\(10\%\)的数据,\(n,x_i\leq 5\)
对于\(50\%\)的数据,\(n\leq 20\)
对于另外\(10\%\)的数据,\(a=b\)
对于又另外\(20\%\)的数据,\(a=1\)
对于\(100\%\)的数据,\(1\leq n\leq 100000,1\leq a,b,x_i\leq 10^9\)

Solution

  • 假设有\(a \leq b.\)
  • 自然可以想到将每堆石子对\(a+b\)取模.得到一个余数\(r\).
    1. \(r < a\),这堆石子谁也不能取.没有影响.随意选即可.
    1. \(a \leq r<b.\)这堆石子只有\(Alice\)能取,只要选了,\(Alice\)必胜.
    1. \(b\leq r <2a.\) 这堆石子两人轮流取,取到双方都不能取时,先后手完成了交换.对结果的影响显然只与这样的堆数的奇偶性有关.
    1. \(2a\leq r <a+b.\)这种石子若有\(2\)堆及以上,无论谁先手,\(Alice\)总可以从这样的堆中取一次,使其变为情况\(2\)的一堆,所以\(Alice\)必胜.若有\(1\)堆且情况\(3\)的堆数为偶数,则先手必胜.若有\(1\)堆且情况\(3\)的堆数为奇数,则\(Alice\)必胜.若不存在这种堆,情况\(3\)为奇数,先手必胜,情况\(3\)为偶数,后手必胜.
  • \(Alice\)必胜的情况在\(2\)\(4\)中有重叠部分,所以可以计算出先手后手必胜的情况数目,再用总数减去即可.(\(Bob\)不可能必胜).
#include<bits/stdc++.h>
using namespace std;
typedef long long LoveLive;
inline int read()
{
    int out=0,fh=1;
    char jp=getchar();
    while ((jp>'9'||jp<'0')&&jp!='-')
        jp=getchar();
    if (jp=='-')
        {
            fh=-1;
            jp=getchar();
        }
    while (jp>='0'&&jp<='9')
        {
            out=out*10+jp-'0';
            jp=getchar();
        }
    return out*fh;
}
const int P=1e9+7;
inline int add(int a,int b)
{
    return (a+b) % P;
}
inline int mul(int a,int b)
{
    return 1LL * a * b % P;
}
inline int sub(int a,int b)
{
    return (add(a,-b)+P)%P;
}
int fpow(int a,int b)
{
    int res=1;
    while(b)
        {
            if(b&1)
                res=mul(res,a);
            a=mul(a,a);
            b>>=1;
        }
    return res;
}
int flag=0;
int calcodd(int x)
{
    if(!x)
        return 0;
    return fpow(2,x-1);
}
int calceven(int x)
{
    if(!x)
        return 1;
    return fpow(2,x-1);
}
int x[4],ans[4];
int main()
{
    int n,a,b;
    freopen("stone.in","r",stdin);
    freopen("stone.out","w",stdout);
    n=read(),a=read(),b=read();
    if(a>b)
        swap(a,b),flag=1;
    for(int i=1; i<=n; ++i)
        {
            int r=read();
            r%=(a+b);
            if(r<a)
                ++x[0];
            else if(r>=a && r<b)
                ++x[1];
            else if(r>=b && r<2*a)//这个区间可能为空集.加上else.
                ++x[2];
            else if(r>=2*a)
                ++x[3];
        }
    ans[2]=mul(x[3],calceven(x[2]));
    ans[2]=add(ans[2],calcodd(x[2]));
    ans[2]=mul(ans[2],fpow(2,x[0]));
    ans[3]=calceven(x[2]);
    ans[3]=mul(ans[3],fpow(2,x[0]));
    ans[0]=sub(fpow(2,n),add(ans[2],ans[3]));
    if(flag)
        swap(ans[0],ans[1]);
    for(int i=0; i<4; ++i)
        printf("%d ",ans[i]);
    return 0;
}

T2

占坑.

T3

占坑.

test20181223

标签:pan   stdout   ....   会有   stack   math   sub   ati   long long   

原文:https://www.cnblogs.com/jklover/p/10168260.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 designnerd.net 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号