Fork me on GitHub

Wannafly挑战赛18

发表于 | 分类于

A 序列

题目描述：

有一个长度为n的序列a，已知a[1]=a[n]=1，且对于2 <= x <= n，a[x] / a[x-1]是以下三个数字之一 [ 1，-2，0.5 ],问有多少种不同的序列满足题意。
两个序列不同当且仅当它们有至少一个位置上的数字不同，序列a可以为任何实数。

输入描述：

一个整数 表示n (1<= n <= 1e3)；

输出描述：

一个整数 表示答案模109+7；

示例1：

输入
5
输出
7

思路：

本题有个比较明显的规律 -2和0.5要同时出现并且-2要出现两次所以0.5要出现两次。并且他们的位置随意。所以先求出有多少个即n/4；然后枚举i从0到 n/4;

代码：

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e3+10;
const int mod=1e9+7;
ll f[maxn][maxn];
void init(){
    for(int i=0;i<=1009;i++)
        f[i][0]=1;
    for(int i=1;i<=1009;i++)
        for(int j=1;j<=i;j++)
         f[i][j]=(f[i-1][j]+f[i-1][j-1])%mod;
    return ;
}
int main(){
    int n;
    cin>>n;
    init();
    int t=n-1;
    ll ans=0;
    int h=t/4;
    for(int i=0;i<=h;i++){
        ans=(ans+f[t][2*i]*f[t-2*i][2*i]%mod)%mod;
    }
    cout<<ans<<endl;
    return 0;
}

总结：这题虽然找到要成对出现但我没有想到他出现的位置可以随意。

C 异或和

题目描述：

有一个nm的网格图，给出小B出现在每个位置的可能性，用一个nm的01矩阵表示，小B等概率出现在所有1的位置。求小A在每个位置上与小B期望曼哈顿距离的异或和，先把期望取模之后再异或

输入描述：

第一行读入两个整数 n,m (n,m <= 2000)
接下来n行，每行读入一个长度为m的01字符串。

输出描述：

输出一个整数表示答案模 109+7

示例1

输入
1 3
101
输出
1

说明

小A出现在(1,1)的时候期望曼哈顿距离是1
小A出现在(1,2)的时候期望曼哈顿距离是1
小A出现在(1,3)的时候期望曼哈顿距离是1
答案是这三者的异或和。

思路：

分别求x方向对点的贡献度，y方向对点的贡献度
然后求出期望再异或和(注意：异或和不要取模)。

代码：

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
	#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2010;
const int mod=1e9+7;
ll lx[maxn],rx[maxn],ly[maxn],ry[maxn],vis1[maxn],vis2[maxn];
char s[maxn][maxn];
ll quickpow(ll a,ll b){
    ll sum=1;
    while(b){
        if(b&1){
            sum=(sum*a)%mod;
            //cout<<sum<<endl;
        }
        a=(a*a)%mod;
        b>>=1;
    }
    //cout<<sum<<endl;
    return sum;
}
int main(){
    ll n,m;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%s",s[i]+1);
    }
    ll num=0;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        if(s[i][j]=='1'){
            vis1[j]++;
            vis2[i]++;
            num++;
        }
    }
    ll t=vis1[1];
    for(int i=2;i<=m;i++){
        lx[i]=(lx[i-1]+t)%mod;
        t=(t+vis1[i])%mod;
    }
     t=vis1[m];
    for(int i=m-1;i>=1;i--){
        rx[i]=(rx[i+1]+t)%mod;
        t=(t+vis1[i])%mod;
    }
    t=vis2[1];
    for(int i=2;i<=n;i++){
        ly[i]=(ly[i-1]+t)%mod;
        t=(t+vis2[i])%mod;
    }
    t=vis2[n];
    for(int i=n-1;i>=1;i--){
        ry[i]=(ry[i+1]+t)%mod;
        t=(t+vis2[i])%mod;
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            ans=(ans^((lx[j]+rx[j]+ly[i]+ry[i])%mod*quickpow(num,mod-2))%mod);
           // cout<<ans<<endl;
            //cout<<((lx[j]+rx[j]+ly[i]+ry[i])%mod*quickpow(num,mod-2))%mod<<endl;
    }
    printf("%lld\n",ans);
}

总结：这道题关键是分开求x，y的贡献度这也给了我一个解题经验。