2019,10,25 长郡 csp

未分类

---

不得不说一句, 这位出题人的文笔还真不错...

T1 忧郁 gloomy

  学校里的樱花开了又谢，小W 向窗外望去，只有光秃秃的枝桠在秋风中挺立。他的离
开，似乎也带走了她的春天，她的心里没有了粉红色的花海，没有了和煦的春风，只剩下光秃秃的枝桠，和一颗无处安放的心。
  “该走了。”小W 晃晃脑袋，披上外套，打开前门。即使是有所准备，迎面的秋风还是打了她一个措手不及。小W缩紧了身子，不过那熟悉的怀抱并没有来到。小W 愣了一下，突然笑了，“今年的秋天，还真是冷呢。”
  去图书馆的路上已经堆满了银杏叶，树上的叶在呼啸的秋风中飘零。小W看着空中的树叶，仿佛看到了樱花树上粉红的花片片凋零的样子。“是不是越美的事物越容易消逝呢？如果心中的忧郁也能像樱花一样飘落，就好了。”小W心中的忧郁又涌上心头。“忧郁似乎也像微笑一样能够传递，最近也让大家或多或少地忧郁起来了呢，这些东西还是回到我身上来比较好吧。”低语中，小W已经进入图书馆研究同学之间分担忧郁的关系网络了。

题意

有 $n$ 个学生 $(1\le n\le 24)$, 它们之间有 $m$ 条忧郁值分担关系 $(1\le m\le 10^4)$,

一条关系 $a,b,c$ 表示 $a$ 为 $b$ 分担 $c$ 单位的忧郁值 $(1\le c \le 10^5)$,
即 $val_a+=c,\ val_b-=c$,

现在, 小W 可以执行若干次命令 $x,y,z$, 表示让 $x$ 分担 $z$ 单位 $y$ 的忧郁值,
即 $val_x+=z,\ val_y+=z$,

问小W 至少要执行多少次命令才能使所有人的忧郁值归零 (初始时忧郁值为零).

方法

这道题的描述有点迷...差点就没看懂题... (单押*1)

若有 $t$ 的点的权值总和为 0, 则可以执行 $t-1$ 次命令使它们的权值归零,
要是执行命令的次数最少, 我们就要把这 $n$ 个点分成尽量多个权值和为 0 的部分.

考场上写了个复杂度似乎很正确的爆搜, 结果 20pts...
复杂度确实正确, WA了...
因为每次把能凑在一起的点凑一起不一定是最优方案,

正解是状压dp, 设 $f[i]$ 为点集为 $i$ 时, 权值和为 0 的块数的最大值,
再记一个 $sum[i]$, 表示权值和, 每次枚举一个新点转移就行了, 方程如下

$$f[i]=max\{ f[i \oplus (1<<j)]+[sum[i^(1<<j)]+val[j]==0] \},\ (!(i\&(1<<j)))$$

后面的那个中括号是个 bool 变量

代码

(加了一些奇怪的卡常优化...)

#include<bits/stdc++.h>
using namespace std;
const int N=24+7;
const int M=16777216+7;
int T,n,m,val[N],bi[N],f[M],sum[M],q0[N],q1[N],fl[M],num[M];
void print(int x){
    for(int i=1;i<=n;i++){ printf("%d",x&1); x>>=1; }
}
int main(){
//  freopen("gloomy.in","r",stdin);
//  freopen("gloomy.out","w",stdout);
    cin>>n>>m;
    int x,y,w;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&w);
        val[x]+=w; val[y]-=w;
    }
    for(int i=0;i<n;i++){
        if(val[i]<0){ q0[++q0[0]]=i; if(val[i]<0) fl[bi[i]]=-1; }
        else{ q1[++q1[0]]=i; if(val[i]>0) fl[bi[i]]=1; }
        bi[i]=1<<i;
        num[bi[i]]=i;
    }
    int all=(1<<n)-1;
    int cnt=0;
    for(int i=0;i<=all;i++){
        int j=num[i&(-i)];
        if(i){
            sum[i]=sum[i^bi[j]]+val[j];  
            if(fl[i^bi[j]]==-1&&val[j]<=0){ fl[i]=-1; continue; }
            else if(fl[i^bi[j]]==1&&val[j]>=0){ fl[i]=1; continue; }
        }
        int lim=sum[i]>0 ?q0[0] :q1[0];
        for(int k=1;k<=lim;k++){
            int j=sum[i]>0 ?q0[k] :q1[k];
            if(!(i&bi[j])){
                if(sum[i]+val[j]==0) f[i|bi[j]]=max(f[i|bi[j]],f[i]+1);
                else f[i|bi[j]]=max(f[i|bi[j]],f[i]);
            }
        }
    }
    printf("%d\n",n-f[all]);
    return 0;
}

---

T2 枣子 jujube

  天色渐晚，暮色像一头小熊，笨拙、漂亮地攀爬着天空的梯子。在落日余晖的照映下，小W 家门口的枣树披上了金色的衣，树上的枣子红灿灿的，甚是可人。仔细想来，枣树也已〸六有余，恰与她同岁呢。小时候小W就认为，门口的那株枣树就是她的守护神。无论春夏还是秋冬，都陪在她的身旁。天热了，洒下一片阴凉，她和朋友们打闹嬉戏；天凉了，结出一颗颗枣子，甜甜的，沁人心脾，她和家人在树下吃枣闲聊。似乎所有的美妙回忆都离不开这株枣树，所有的伤心故事也在枣树下消散殆尽。

题意

给定三个数 $a,b,c$, 求 $a^{b^c}$ 能表示为多少种 $x_1^{x_2^{x_3^{...x_k}} }$ 的形式 $(a,b,c \le 4*10^4)$.

方法

设 $A^k$ 为化简后的 $a$, 考场上只考虑的了 $k$ 与 $b^c$ 同底数的情况, 没有考虑把 $k*b^c$ 表示为 $p*q^r$ 的情况, 所以...

那么还是先处理出 $f[i]$, 表示 $i$ 能表示为多少种 "枣子塔" 的形式 (没错就是上面那货).

然后把 $a$ 化简为 $A^k$, 然后质因数分解 $k*b^c$ (先分解 $k$, 然后再分解 $b$).

那么每一个质因子的每一个次方都可以放在下面或留在上面, 变成 $p*q^r$ ( $p$ 就是放在下面的).

那么对于每一个 $r$, 质因子 $d_i$ 的贡献就是 $\lfloor \frac{r_i}{r} \rfloor+1$ ( $\lfloor \frac{r_i}{r} \rfloor$ 种留在上面的情况再加上一种放在下面的情况),
最终的答案就是 $(\Pi{\lfloor \frac{r_i}{r} \rfloor+1})-1$ (减去全部都放在下面的情况).

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=7e5+7;
const ll mod=998244353;
int T,a,b,c,top,num[N],v[N],pri[N],cnt;
ll f[N],g[N],r[N],ans,maxr;
void pre(){
    for(int i=2;i<=20;i++){
        f[i]=1;
        for(int j=2;j*j<=i;j++)
            if(!(i%j)){
                int t=i,cnt=0;
                while(!(t%j)){ t/=j; cnt++; }
                if(t==1) f[i]+=f[cnt];
            }
    }
    for(ll i=2;i<=640000;i++){
        if(i>20) f[i]++;
        ll t=i*i;
        for(int j=2;t<=640000&&t>0;j++,t*=i)
            if(t>20) f[t]+=f[j];
    }
    for(int i=2;i<=200;i++){
        if(!v[i]){ v[i]=i; pri[++cnt]=i; }
        for(int j=1;j<=cnt;j++){
            if(pri[j]>v[i]||pri[j]*i>200) break;
            v[pri[j]*i]=pri[j];
        }
    }
}
int simp(int &x){
    for(int i=2;i*i<=x;i++)
        if(!(x%i)){
            int t=x,cnt=0;
            while(!(t%i)){ t/=i; cnt++; }
            if(t==1){ x=i; return cnt; }
        }
    return 1;
}
void divd(int x,int tms){
    for(int i=1;pri[i]*pri[i]<=x;i++)
        if(!(x%pri[i])){
            int cnt=0;
            while(!(x%pri[i])){ x/=pri[i]; cnt++; }
            if(!num[pri[i]]) num[pri[i]]=++top;
            r[num[pri[i]]]+=cnt*tms;
            maxr=max(maxr,r[num[pri[i]]]);
        }
    if(x!=1){
        if(!num[x]) num[x]=++top;
        r[num[x]]+=tms;
        maxr=max(maxr,r[num[x]]);
    }
}
int main(){
//  freopen("jujube.in","r",stdin);
    pre();
    cin>>T;
    while(T--){
        memset(r,0,sizeof(r));
        memset(num,0,sizeof(num));
         top=0;
        scanf("%d%d%d",&a,&b,&c);
        int k=simp(a); 
        divd(k,1);
        divd(b,c);
        ans=0;
        for(ll rr=2;rr<=maxr;rr++){
            ll res=1;
            for(int i=1;i<=top;i++) res=res*(r[i]/rr+1)%mod;
            ans=(ans+(res-1)*f[rr]%mod)%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

---

T3 开关 switch

  夜已深了，银白色的月光洒在地上，香樟叶被风抚过，树影婆娑。树旁教学楼的灯一盏盏熄灭，与树相伴的只剩下小W。教室里奋笔疾书的沙沙声在如刀入鞘般的合笔声中结束，小W 轻呼出一口气。该走了，她这样想着。

题意

有 $n$ 盏灯 $(1\le n\le 10^9)$, 其中前 $v$ 盏是开着的 $(0\le v\le n)$,

在每次操作中, 小W 每次可以选择任意盏灯, 将它们的状态取反, 若干次操作构成一个方案.

一个方案是合法的, 当且仅当:
1. 这个方案是一个集合 (操作不重复).
2. 执行完这个方案后, 所有灯都熄灭了.

求有多少种大小为 $m$ 的方案 $(0\le m \le 10^3)$
(方案大小的为它的操作个数).

做法

考场上大概还剩半个小时才看这道题, 本来想就写个暴力, 结果不会写...
然后随便推了个式子, 样例都没过...
最后特判了几种情况, 20pts...

题目要求的是集合 (也就是 $C$ ), 为了方便, 我们先认为它是有顺序的 (因为 dp 的话需要一个拓扑序), 最后再除以一个 $m!$ 就行了,

考虑设 $f[i]$ 为当 $m=i$ 时的方案数, 若不考虑重复, 那么$f[i] = A_{2^n}^{i-1}$ (因为最后一位是固定的).
由于前面选的 $i-1$ 个操作都不会重复, 不合法的情况就只有当前需要选的那个操作在之前已经被选过了,

那我们把所有不合法的情况按照重复的操作进行分类, 最后加法原理就行了,

考虑若第 $i$ 次操作与前面一个操作重复了, 那么这两个操作就相当于抵消了, 剩下的 $i-2$ 个操作的异或和就应该要能把全部灯熄灭, 情况数就是 $f[i-2]$, 然后对于每一个重复的操作 (每一类不合法的情况), 我们还要枚举它出现在哪一位, 所以不合法的情况为

$$(tot-(i-2))*(i-1)*f[i-2].$$
其中 $(tot-(i-2))$ 是枚举每一个重复的操作,
$(i-1)$ 是重复操作的位置,

所以转移方程为

$$f[i]=A_{2^n}^{i-1}-(tot-(i-2))*(i-1)*f[i-2].$$

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=1e3+7;
const ll mod=19260817;
int T;
ll n,m,v;
ll f[M];
ll q_pow(ll a,ll p){
    ll res=1;
    while(p){
        if(p&1) res=res*a%mod;
        p>>=1;
        a=a*a%mod;
    }
    return res;
}
ll inv(ll x){ return q_pow(x,mod-2); }
ll dif(ll x,ll y){ return ((x-y)%mod+mod)%mod; }
int main(){
//  freopen("switch.in","r",stdin);
    cin>>T;
    while(T--){
        cin>>n>>m>>v;
        f[0]=v==0; f[1]=1;
        ll tot=q_pow(2,n),res=1,fac=1;
        for(ll i=2;i<=m;i++){
            res=res*dif(tot,i-2)%mod;
            fac=fac*i%mod;
            f[i]=dif(res%mod,dif(tot,i-2)*(i-1)%mod*f[i-2]%mod);
        }
        printf("%lld\n",f[m]*inv(fac)%mod);
    }
    return 0;
}