首页 > 其他分享 >P3750 [六省联考 2017] 分手是祝愿

P3750 [六省联考 2017] 分手是祝愿

时间:2023-02-11 13:23:05浏览次数:59  
标签:六省 int GetC 线性 P3750 fac include 联考 向量

\(\mathcal Link\)

考虑建立异或方程组,则最终状态为该方程组的一个解,第 \(i\) 个方程形如 \(\displaystyle \bigoplus_{i\mid d} x_d=a_i\)。

这些方程构成的向量线性无关,证明如下:
考虑将这些向量从后往前插入线性基。插入第 \(i\) 个向量时,由于已有向量第 \(i\) 位都为 \(0\),故必然能成功插入线性基。

这意味着最终状态惟一,而求出该解只需要类似地从大到小将每个向量插入线性基即可。
由于本题向量的特殊性质,使得线性基每一位对应向量都只有一位有值,可以做到 \(\mathcal O(n\log n)\)

设 \(f(i)\) 表示从需要按下 \(i\) 个按钮到需要按下 \(i-1\) 个按钮的期望步数。

则有

\[\begin{split} f(i)&=\frac in +\frac{n-i}n[f(i+1)+f(i)+1] \\ \\ &=\frac{n+(n-i)f(i+1)}i \end{split}\]

边界条件 \(f(n)=1\)

#include <cstdio>
#include <algorithm>
#include <cctype>
using namespace std;

using ll=long long;

char buf[1<<14], *p1=buf, *p2=buf;
#define GetC() ((p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<14,stdin),p1==p2)?EOF:*p1++)

struct Ios{}io;
template <typename _tp>
Ios &operator >>(Ios &in, _tp &x){
    x=0; int w=0; char c=GetC();
    for(;!isdigit(c);w|=c=='-', c=GetC());
    for(;isdigit(c);x=x*10+(c^'0'), c=GetC());
    if(w) x=-x;
    return in;
}

const int N=1e5+5, mod=100003;

ll a[N], f[N], fac[N], inv[N];

int main(){
    int n, k; io>>n>>k;

    fac[0]=fac[1]=1; inv[1]=1;
    for(int i=2;i<=n;++i){
        fac[i]=fac[i-1]*i%mod;
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    }

    for(int i=1;i<=n;++i) io>>a[i];
    int cnt=0;
    for(int i=n;i;--i){
        for(int j=2*i;j<=n;j+=i) a[i]^=a[j];
        cnt+=a[i];
    }

    f[n]=1;
    for(int i=n-1;i;--i){
        f[i]=(n+(n-i)*f[i+1])%mod*inv[i]%mod;
    }
    for(int i=k;i;--i) f[i]=1;


    ll ans=0;
    for(int i=1;i<=cnt;++i) ans+=f[i];

    printf("%lld\n", ans*fac[n]%mod);
    return 0;
}

标签:六省,int,GetC,线性,P3750,fac,include,联考,向量
From: https://www.cnblogs.com/pref-ctrl27/p/17110998.html

相关文章

  • 「解题报告」[省选联考 2022] 序列变换
    我不是很能理解?神奇贪心题。括号序列考虑直接整树形结构,然后操作就是将一个子树内所有儿子放到另一颗子树里,并把这个点单独放到这个子树内,贡献为\(x\)乘终点子树权值加......
  • 「解题报告」[省选联考 2022] 卡牌
    放假上午想出的做法,写了一下TLE35分。以为有更高级的复杂度,然后刚看了看题解发现题解就是这个复杂度,呃呃,卡常吧。考虑将每个数写成它所包含的质因子的集合,写成一个0......
  • 「解题报告」[省选联考 2022] 学术社区
    摆烂了,不想写代码了。我怎么这么菜啊,看题解里说的各种思路,我一个都没想到。哭考虑给每个消息建一个点,每两个点之间连边\(x\toy\),边权为将\(y\)接在\(x\)后头能......
  • 洛谷 P3750 [六省联考 2017] 分手是祝愿
    洛谷传送门考虑先求出哪些点一定要按,然后dp。设\(f_i\)为当前还有\(i\)个点要按的期望步数。转移就是\(f_i=\dfrac{i}{n}f_{i-1}+\dfrac{n-i}{n}f_{i+1}\),初......
  • 【题解】P3750 [六省联考 2017] 分手是祝愿
    出题老哥收收味吧,阿米奈!记一下几个常用的手段。昨晚CF的D是差不多的思路吧,不然不会来做。思路期望dp.先做一些准备工作,求一下逆元和每个数的因数,复杂度\(O(n\l......
  • P7518 [省选联考 2021 A/B 卷] 宝石
    非常有意义的一道题,虽然不算太难。非常好题目,英雄联盟,爱来自瓷器。戳我看题题意给一定一个\(n\)个点的树,每个点有一个颜色,点\(u\)的颜色为\(w_u\)。给定一个\(P_......
  • 题解 P8294 [省选联考 2022] 最大权独立集问题
    Solution根据一些逝去的记忆可以得到一个DP状态:\(f_{u,x,y}\)表示\(u\)这棵子树,\(x\)从子树出去,\(y\)进来这棵子树。然后讨论一下状态转移,可以暴力枚举状态,暴力枚......
  • luogu P5291 [十二省联考 2019] 希望
    题面传送门真的很想吐。题目的意思大概就是在一棵树上选出\(k\)个联通块,使得这\(k\)个联通块有交。显然联通块的交还是联通块,因此转化为对联通块计数。而联通块个数等于......
  • 十二省联考 2019 题解
    Day1B字符串问题朴素的想法是,建一张\(n_a+n_b\)个点的有向图\(G\)。对于一个支配关系\((x,y)\),从\(x\)向\(y+n_a\)连边。此外,枚举\(1\lei\len_b\),对于每个......
  • P8294 [省选联考 2022] 最大权独立集问题
    题解可以发现对于一个子树,假设移出的点为\(u\),移入的点到\(v\),那么这棵子树的根一定是\(LCA(u,v)\).于是可以设\(dp_{u,v}\)表示在以\(LCA(u,v)\)为根的子树......