2017 ACM-ICPC 亚洲区（西安赛区）网络赛-白红宇

2017 ACM-ICPC 亚洲区（西安赛区）网络赛

阅读量：6931 次

发布时间：2019-06-27

本文共 6730 字，大约阅读时间需要 22 分钟。

这个西安赛区大概是我们学校打得最好的一次了，因为数学题多，而且嘛，那个I竟然就是暴力，恭喜我们学校分了个机会

只看题面

23.46%

1000ms

32768K

Bob has a not even coin, every time he tosses the coin, the probability that the coin's front face up is $\frac{q}{p}(\frac{q}{p} \le \frac{1}{2})pq(pq≤21).$

The question is, when Bob tosses the coin

If the answer is $\frac{X}{Y}YX, because the answer could be extremely large, you only need to print (X * Y^{-1}) \mod (10^9+7)(X∗Y−1)mod(109+7).$

Input Format

First line an integer $\le 100T≤100).$

Then Each line has $p,q,k(1\le p,q,k \le 10^7)p,q,k(1≤p,q,k≤107) indicates the i-th test case.$

Output Format

For each test case, print an integer in a single line indicates the answer.

样例输入

22 1 13 1 2

样例输出

500000004555555560

题目来源

这个可以推到一个公式

(P^n+(p-2q)^n)/（2*p^n）

这个要得到这个数要求逆元什么的，因为直接除会造成误差

当时写的那么脑残么，奇质数可以直接求

#include
         
          using namespace std;typedef long long ll;const ll MD=1e9+7;ll po(ll a, ll b){    ll ans=1;    for(;b;a=a*a%MD,b>>=1)if(b&1)ans=ans*a%MD;    return ans;}int main(){    int T;    scanf("%d",&T);    while(T--)    {        ll p,q,k;        scanf("%lld%lld%lld",&p,&q,&k);        printf("%lld\n",(po(p,k)+po(p-2*q,k))*po(2*po(p,k),MD-2)%MD);    }    return 0;}

#include
         
          using namespace std;const int MD=1e9+7;typedef long long LL;LL po(LL a, LL b){    LL ans=1;    while(b){        if(b&1)        ans=ans*a%MD;        b=b/2;        a=a*a%MD;    }    return ans;}LL la(LL a,LL b,LL &x,LL &y){    LL d;    if(!b)    {        x=1;        y=0;        return a;    }    d=la(b,a%b,y,x);    y-=a/b*x;    return d;}int main(){    int T;    scanf("%d",&T);    while(T--)    {        LL p,q,k;        scanf("%lld%lld%lld",&p,&q,&k);        LL x,y;        la(2*po(p,k),MD,x,y);        x=(x%MD+MD)%MD;        printf("%lld\n",(po(p,k)+po(p-2*q,k))*x%MD);    }    return 0;}

只看题面

40.09%

1000ms

32768K

Define the function $S(k*x)\%233=0S(k∗x)%233=0.$

Input Format

First line an integer $\le 100T≤100). Then Each line has a single integer x(1 \le x \le 1000000)x(1≤x≤1000000)indicates i-th test case.$

Output Format

For each test case, print an integer in a single line indicates the answer. The length of the answer should not exceed

样例输入

样例输出

89999999999999999999999999

这个C的构造嘛，其实还是比较巧妙的。有输出233个9或1e6过的,1e6这个比较好想，因为每一位都得到贡献都相同，所以233次一定是233的倍数

#include
             
              int main(){    int t,n,a=(int)1e6;    scanf("%d",&t);    while(t--)    {        scanf("%d",&n);        for(int i=1;i<=233;i++)        printf("%d",a);        puts("");    }}

只看题面

19.64%

1000ms

32768K

Given a directed graph with $\cdots, n-10,1,⋯,n−1.$

For each $\le i < j < n0≤i<j<n, there exists an edge from the i-th node to the j-th node, the capacity of which is iii xor jjj.$

Find the maximum flow network from the 0-th node to the (n-1)-th node, modulo

Input Format

Multiple test cases (no more than

In each test case, one integer in a line denotes $\le n \le 10^{18})n(2≤n≤1018).$

Output Format

Output the maximum flow modulo

样例输入

样例输出

题目来源

#include
             
              #include
              
               #include
               
                #include
                
                 #define LL long long#define mod 1000000007using namespace std;int main(){    LL a[100]={
           0},b[100]={
           0},c[100]={
           0},d[100],i;    a[1]=1;b[1]=1;    for(i=2;i<62;i++){        a[i]=a[i-1]*2;//每行个数         b[i]=b[i-1]+a[i];//总个数         b[i]%=mod;    }    d[1]=1;    for(i=2;i<62;i++){        d[i]=(d[i-1]*4)%mod;    }    c[1]=1;    for(i=2;i<62;i++){        c[i]=((2*c[i-1])%mod+(d[i]-d[i-1]+mod)%mod+mod)%mod;//每组的和     }    LL n,m;    while(~scanf("%lld",&n)){        LL k=0,kk=n-1;        for(i=1;i<=60;i++){            if(a[i]
                 
                  =1;i--){            //printf("%lld - %lld\n",n,a[i]);            if(n>a[i]){                sum=(sum+c[i])%mod;                n-=a[i];            }            //if(n<=0)break;        }        printf("%lld\n",(sum+m-1+mod)%mod);     }}

只看题面

22.95%

4000ms

524288K

Barty have a computer, it can do these two things.

Add a new string to its memory, the length of this string is even.

For given

Please help your computer to do these things.

Input Format

Test cases begins with $\le 5)T(T≤5).$

Then

Each test case begins with an integer $\le 30000)Q(Q≤30000).$

Then

1 s: add a new string

2 a b c d: find how many strings satisfying the requirement above.

$∑∣s∣+∣a∣+∣b∣+∣c∣+∣d∣≤2000000\sum |s| + |a| + |b| + |c| + |d| \le 2000000∑∣s∣+∣a∣+∣b∣+∣c∣+∣d∣≤2000000.$

Output Format

For type

样例输入

1101 abcqaq1 abcabcqaqqaq2 ab bc qa aq2 a c q q1 abcabcqaqqwq2 ab bc qa aq2 a c q q1 abcq2 a c q q2 a b c q

样例输出

题目来源

#include 
                 
                  using namespace std;const int N = 1e6+10;typedef long long LL;char str[N], a[N], b[N], c[N], d[N];const LL mod = 1e9+7;const LL MD = 1313;LL *has[N], pos[N];int xlen[N];int main(){    pos[0]=1;    for(int i=1;i
                  
                   xlen[i]/2||l3+l4>xlen[i]/2) continue;                    int cx=xlen[i]/2;                    LL x=has[i][l1];                    if(x!=ans1) continue;                    x=(has[i][cx]-has[i][cx-l2]*pos[l2]%mod+mod)%mod;                    if(x!=ans2) continue;                    x=(has[i][cx+l3]-has[i][cx]*pos[l3]%mod+mod)%mod;                    if(x!=ans3) continue;                    x=(has[i][2*cx]-has[i][2*cx-l4]*pos[l4]%mod+mod)%mod;                    if(x!=ans4) continue;                    cnt++;                }                printf("%d\n",cnt);            }        }    }    return 0;}