第二周结束了啊……

今天是什么挂分大赛

我又是什么纸张……

您所钟爱的原题

[A]

调挂了，明天继续。

大概的思路是合法方案当且仅当三个数组中两个最上且最左的’1’是重合时候方案才会满足。

然后暴力判断，但是写挂了。

[B]

什么极好的容斥，使我的得分骤降。

观察到 m \leq 15，因此是可以直接 2^m 枚举状态的。

然后容斥就可以了。

但是系数应该是 2^{cnt-1} 而不是 cnt

调出来的时候当场崩溃，不知道为什么大样例+拍了5组的情况下还能挂80。

后面冷静了一下发现拍的几组数据都太大了，根本没有机会让三个相乘。。。

#include<bits/stdc++.h>
using namespace std;
const int M=15;
typedef __int128 LL;
LL n,m,x[M];
LL res=0;
LL lcm(LL a,LL b){return a/__gcd(a,b)*b;}
inline LL read()
{
    LL x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void write(LL x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
    return;
}
LL quick_power(LL a,LL b)
{
    LL res=1;
    while(b)
    {
        if(b&1)res*=a;
        a*=a;
        b>>=1;
    }
    return res;
}
int main()
{
    freopen("light.in","r",stdin);
    freopen("light.out","w",stdout);
    n=read();
    m=read();
    for(LL i=0;i<m;i++)x[i]=read();
    for(LL i=1;i<(1<<m);i++)
    {
        LL l=1,cnt=0,flag=1;
        for(LL j=m-1;~j;j--)
        {
            if((i>>j)&1)
            {
                l=lcm(l,x[j]);
                if(l>n)
                {
                    flag=0;
                    break;
                }
                cnt++;
            }
        }
        if(flag)
        {
            if(cnt&1)res+=quick_power(2,cnt-1)*(n/l);
            else res-=quick_power(2,cnt-1)*(n/l);
        }   
    }
    write(res);
    return 0;
}
/*
12
1 2 3 4 5 6 7 8 9 10 11 12
- - -   -   -   - -  -  -   
5+2-1
*/

[C]

严查此题数据！

不是为什么 O(mq) 的暴力能过啊。

正解应该需要采用将询问离线后排序，最后倒着做一遍DP。

[D]

首先需要DFS一遍将子树的问题转成区间问题。
然后上扫描线求区间面积并。
实在是没想到扫描线……

[E]

不会，为什么是矩阵快速幂+一堆DP。