发布于 

ACM SD 2017 C

ACM SD 2017 C

好像是除了签到题外最水的一题 ，做题时思路还算是清晰，但是第一次做时想错了。

题目来源: sdibt

分析

题目给出了n个点，然后每秒钟每个点会分裂为两个点，分别移动到其左边和右边。即对于第t秒时存在一个点的位置为x，那么在t+1秒时便存在两个由其分裂出来的点在x-1,x+1。由此，我们可以得出对于一个点衍生出的所有的点的位置分布图，大致如下： 

1
2
3
4
5
6
1
             1 0 1
           1 0 2 0 1
         1 0 3 0 3 0 1
       1 0 4 0 6 0 4 0 1
       	 ......

由此，我们可以看出其存在的规律--将其中的0全部去掉之后，其分布便为一个杨辉三角，即下图： 

1
2
3
4
5
6
1
              1 1
             1 2 1
            1 3 3 1
           1 4 6 4 1
            ......

而题目要求给出了n个点的初始位置和各自的数量之后，能够计算得出在T秒之后在位置w处的点的总数。

因此，我们可以对于每一个初始的点与w之间进行判断，得出由此点衍生出的图中w是否为0，若不为0则将根据坐标，将其化为一个求组合数的问题。

结论

\[ Ans = \sum_{i=1}^n cnt(i) \]

\[ cnt(i) = \left\{ \begin{aligned} &0 &, abs(w-x) > T \\ &0 &, odd(w-x-T) \\ &C(n,m) &,even(w-x-T) \end{aligned} \right.\] \[ (n=T,m=abs(w-x+t)/2) \]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <cstdio>

#define MOD 1000000007

long long a[100001];

struct FireWork
{
trueint num,x;

trueFireWork(int x=0,int num=1):x(x),num(num)	{}
}fire[100100];

long long abs(long long x)
{
truereturn x>0?x:-x;
}

void exgcd(long long a,long long b,long long &x,long long &y){
    if (b==0){
        x=1,y=0;
        return;
    }
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}

long long getInverse(long long x,long long y){
    long long res,tmp;
    exgcd(x,y,res,tmp);
    return (res+y)%y;
}

long long C(long long n,long long m,long long p){//C(n,m)%p 
    
    long long tmp1=getInverse(a[m],p);
    tmp1=a[n]*tmp1%p;
    long long tmp2=getInverse(a[n-m],p);
    return tmp1*tmp2%p;
}

long long cnt(int x,int w,int t)
{
truelong long dis = abs(x-w);

trueif (dis > t)
truetruereturn 0;
trueif ( (t-dis)%2 == 1)
truetruereturn 0;

truedis = dis/2;
truedis += (t+1)/2;
truedis = t - dis;

true//printf("!%lld %d %lld\n",dis,t,C(dis,t,MOD));

truereturn C(t,dis,MOD);
}

int main()
{
trueint n,t,w;

truea[0] = 1;
truefor (int i = 1; i<=100000; i++)
truetruea[i] = a[i-1]*i % MOD;

truewhile (scanf("%d%d%d",&n,&t,&w)!=EOF)
true{
truetruefor (int i = 0; i<n; i++)
truetrue{
truetruetrueint x,y;
truetruetruescanf("%d%d",&x,&y);
truetruetruefire[i] = FireWork(x,y);
truetrue}

truetruelong long ans = 0;
truetruefor (int i = 0; i<n; i++)
truetruetrue{
truetruetruetrueans += fire[i].num*cnt(fire[i].x,w,t);
truetruetruetrueans %= MOD;
truetruetrue}

truetrueprintf("%lld\n",ans%MOD);

true}
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

本站由 [@Songer](https://blog.songer.xyz/) 创建，使用 Stellar 作为主题。