Loi_20181029_互测

Loi20181029互测

T1 咸鱼计数 || CF185A Plant
T2 咸鱼解锁 || [CQOI2018]屏幕解锁

T1 咸鱼计数 || CF185A Plant

A 咸鱼计数
(count.cpp)
【题目描述】
传说很久很久以前，世界上只有一条咸鱼。世界上所有的咸鱼都是它的后代。
当这条咸鱼出现的时候，它是这样的
而这一年被咸鱼们记录下来，称为咸鱼纪元的开始。
一年之后，它分裂了。然后变成了这个样子。
又过了一年，每条分裂的小咸鱼也再次分裂，变成了下面这个样子。现在请你算一算，过了 n 年之后，有多少条头朝上的咸鱼。
【输入描述】
一行一个整数 n。
【输出描述】
一个整数，表示头朝上的咸鱼数量。这个数可能很大，我们只需要它对
1000000007 取模的结果。
【样例输入 1】
1
【样例输出 1】
3
【样例输入 2】
2
【样例输出 2】
10
【数据范围及提示】
50%的数据，n <= 1e6
100%的数据，n <= 1e18

拿到题，10¹⁸。看出复杂度是O(1)或者O (log2(n))。
开始找规律，
在第0年时，有1条鱼，
在第1年时，有3条鱼，
在第2年时，有10条鱼，
在第3年时，有36条鱼。
好像找不出规律，在画个图试试。

Loi_20181029_互测

画的不好请见谅…
发现了什么…每行的黄色(也就是向上的)，都是它上一行+1。
那么第n年一共有几行？我们发现第n年的行数，是n-1年行数的两倍。那么到第n年，就有 2ⁿ 行。
那就可以做了，就是算出sum(1+2+3+4+…+ 2ⁿ )。
诶，好像不大对。这个复杂度好像是 O( 2ⁿ )，显然过不了。

那还有什么办法？
(听别人说可以用等差数列…然而我才初中，并不会)
还记得小学里，老师让算从1加到100吗？
还记得那个高斯，他把 1+99 , 2+98 , 3+97 这样，一个一个加起来的吗？
那我们也这样，手玩一下，找到公式:
sum(1+2+3+4+…+ r (r是偶数) ) = (r/2 -1)*r+r/2+r
此处的r就是行数, r=2ⁿ。
把式子化简一下,得到:sum(1+2+3+4+…+2 ⁿ ) =2^(2*n-1) + 2^(n-1)
这个东西就可以O(log2(n))的用快速幂来求了。
这是代码。

#include<iostream>
#include<cstdio>
using namespace std;
#define p 1000000007
#define LL long long

LL inp()
{
    LL Ans;char c;bool o=false;
    while((c=getchar())<'0'||c>'9')if(c=='-')o=true;Ans=c-48;
    while((c=getchar())>='0'&&c<='9')Ans=(Ans<<3)+(Ans<<1)+c-48;
    return o==true?-Ans:Ans;
}

LL n,r,rr;

LL ksm(LL a,LL b)
{
    LL ans=1;
    while(b)
    {
        if(b&1)ans=(ans*a)%p;
        b>>=1;
        a=(a*a)%p;
    }
    return ans;
}

int main()
{
    n=inp();
    if(n==0){cout<<1;return 0;}
    if(n==1){cout<<3;return 0;}
    if(n==2){cout<<10;return 0;}
    LL ans=(ksm(2,2*n-1)+ksm(2,n-1))%p;
    cout<<ans<<endl;
}

考试时，看到这个题后很快就有的思路。
打完之后，脑跑数据都对，可一到大样例就不对，后来又换dp做法，矩阵优化，暴力，就是过不了大样例，心态直接炸了。再加上后面三个题都没有思路，直接放弃…当时觉得，我的思路都没错啊，就是不对。
结果考完试，才发现，我误以为1年时有1条鱼，所有的n都应该是n-1。到luogu一交0->100。
烦死了啊…

T2 咸鱼解锁 || [CQOI2018]屏幕解锁

链接

题目描述】
转眼间到了咸元 8102 年，咸鱼们的科技水平突飞猛进。他们已经设计出了
智能手机！这里研究的是咸鱼手机的解锁问题。
人类的普通辣鸡安卓解锁屏幕由 3*3 的点组成，手指在屏幕上画一条线，将
其中一些点连接起来，即可构成一个解锁图案。比如下面的例子：
除此之外，还要遵守以下规则：
连接的点数不能少于 4 个。也就是说只连接两个点或者三个点会提示错误。
两个点之间的连线不能弯曲。
每个点只能“使用”一次，不可重复。这里的“使用”是指手指划过一个点，
该点变绿。
两个点之间的连线不能“跨过”另一个点，除非那个点之前已经被“使用”过了。
对于最后一条规则，参见下图的解释。左边两幅图违反了该规则; 而右边两
幅图(分别为 2->4-1-3-6 和 6->5-4->1->9-2) 则没有违反规则，因为在“跨过”
点时，点已经被“使用”过了。
但是咸鱼们认为这样实在是太 low 了，完全不符合咸鱼的伟大气质。
咸鱼国的咸鱼工程师改进了解锁屏幕，增减了点的数目，并移动了点的位置。
所以咸鱼国的手机解锁屏幕已经不再是一个九宫格形状，但保持上述画线的规则
不变。请计算新的解锁屏幕上，一共有多少满足规则的画线方案。
【输入描述】
输入第一行为一个整数 n ，表示点的数目。
接下来 n 行，每行两个空格分开的整数 xi 和 yi，表示每个点的坐标。
【输出描述】
输出共一行，为题目所求方案数除以 100000007 的余数。
【样例输入】
4
0 0
1 1
2 2
3 3
【样例输出】
8
【样例解释】
设 4 个点编号为 1 到 4 ，
方案有 1→2→3→4，2→1→3→4， 3→2→1→4， 2→3→1→4 以及它们的镜像。
【样例输入 2】
4
0 0
0 1
0 2
1 0
【样例输出 2】
18
【数据范围及提示】
对于 30% 的数据， 1≤n≤10 。
对于 100% 的数据， −1000≤xi,yi≤1000， 1≤n<20 。各点坐标不相同
状态压缩形的递推.

我们用f[i][j]表示所有点的使用情况为i,最后碰到的一个点是j的总方案数.

比如 f[10110][3]表示5,3,2号点被连接,且现在落在3号点的总方案数.

这道题可以采用从前面向后面推的方法,比如 f[10110][3] ,它可以推导到的状态有 f[11110][4] 和f[10111][1] .以f[11110][4] 为例,我们从f[10110][3] 转移的条件就是在4号点和3号点连线上的点都被使用过了,否则就会违背题目的4号规则.

那对于每个状态f[s][j] ,我们就可以枚举它下一次连接的点 kk ,只要 jj 和 kk 连线上的所有点都已经在 ss 这个状态中被使用了,那么 f[s|(1<<(k-1))][k]+=f[s][j] 即可.

对于点与点之间相互的"跨越"关系,在开始时预处理一下即可.

最后统计答案的时候别忘了排除连接的点小于4个的所有状态.

贴上代码:

#include<cstdio>
#include<cstdlib>
#include<vector>
#include<cmath>
#include<algorithm>
#define maxn 22
#define eps 1e-5
#define p 100000007
using namespace std;
struct point{int x,y;}a[maxn];
int f[1<<20][maxn],n,F;
vector<int> cr[maxn][maxn];
int judge(int l,int r,int m)
{
    if((a[m].x==a[l].x||a[m].x==a[r].x)&&a[l].x==a[r].x) return 1;
    else if(a[m].x==a[l].x||a[m].x==a[r].x) return 0;
    double k1=1.0*(a[m].y-a[l].y)/(a[m].x-a[l].x);
    double k2=1.0*(a[r].y-a[m].y)/(a[r].x-a[m].x);
    return fabs(k1-k2)<=eps;
}
int cmp(point a,point b){return a.x==b.x?a.y<b.y:a.x<b.x;}
int main()
{
    scanf("%d",&n);
    F=(1<<n)-1;
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            for(int k=i+1;k<=j-1;k++)
            {
                if(judge(i,j,k)) cr[i][j].push_back(k);
            }
        }
    }
    for(int i=1;i<=n;i++) f[(1<<(i-1))][i]=1;
    for(int i=1;i<=F;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if((i>>(j-1))&1) continue;
            int s=(i|(1<<(j-1)));
            for(int k=1;k<=n;k++)
            {
                if(k==j) continue;
                int x=min(j,k),y=max(j,k),flag=0;
                for(int t=0;t<cr[x][y].size();t++)
                    if(!((i>>(cr[x][y][t]-1))&1)) {flag=1;break;}
                if(flag) continue;
                f[s][j]=(f[s][j]+f[i][k])%p;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=F;i++)
    {
        if(__builtin_popcount(i)<4) continue;
        for(int j=1;j<=n;j++)ans=(ans+f[i][j])%p;
    }
    printf("%d",ans);
    return 0;
}