20171030 考试总结

考试策略

T1 和异或有关…… 异或的东西我都不是很懂，估计做不出来，打个 20 分暴力。

T2 是数学题…… 数学我完全学不懂啊，估计做不出来，打个暴力……woc 为什么模数这么小，取逆元都不好搞。

T3 是什么鬼啦，不过 50 分暴力还是会的…… 为什么死活调不出来啊喂！

今天考试体验极差….. 姑且不论机房好冷和键盘特别反人类，出题人也很反人类而且 jyf 和 boshi 还会在做出题后敲键盘欢呼是什么鬼啦。

反正就是炸了……

T1

题目分析：

首先假设所有数在二进制下有 num(i) 个数第 i 位是 1，那么这一位造成的异或和贡献是 $2\times (n-num(i))\times num(i)$嘛。所以用一个 map 来搞所有数，还是不难的…..

可是出题人太反人类了，模数给得特别大，所以必须用快速乘……

可是如果用 log 复杂度的快速乘会被卡成暴力分……

所以只能用 O(1) 玄学快速乘，并且取模还要玄学一发…..

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
#define LL unsigned long long
LL read() {
    LL q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+(LL)(ch-'0'),ch=getchar();
    return q;
}
const int N=200005;
map<LL,int>mp;
int n,m;LL p;
LL a[N],bin[63],ans,num[63];
inline LL qm(LL x){return x>=p?x-p:x;}
LL mul(LL x,LL y){
    return (x*y-(LL)((long double)x/p*y)*p+p)%p;
}
LL ask() {
    LL re=0;
    for(int i=0;i<=62;++i)
        re+=mul(bin[i],mul(num[i],n-num[i])),re=qm(re);
    return re;
}
void work(LL x,LL y) {
    if(!mp[x]) return;
    int kl=mp[x];mp[y]+=mp[x],mp[x]=0;
    for(int i=0;i<=62;++i) {
        if((x&bin[i])) num[i]-=kl;
        if((y&bin[i])) num[i]+=kl;
    }
}
int main()
{
    freopen("meaningless.in","r",stdin);
    freopen("meaningless.out","w",stdout);
    int bj,i,j;LL x,y;
    n=read(),m=read();
    bin[0]=1;for(i=1;i<=62;++i) bin[i]=bin[i-1]<<1;
    for(i=1;i<=n;++i) {
        a[i]=read(),++mp[a[i]];
        for(j=0;j<=62;++j) if((a[i]&bin[j])) ++num[j];
    }
    for(i=1;i<=m;++i) {
        bj=read();
        if(bj==1) x=read(),y=read(),work(x,y);
        else p=read(),printf("%lld\n",qm(ask()<<1));
    }
    return 0;
}

T2

题目分析:

p=2333

设 $S_n^k=\sum^k_{i=0} C_n^i \bmod p$

则利用卢卡斯定理

$S_n^k=\sum^k _ {i=0}(C^{n \bmod p} _ {n \bmod p}\times C^{i/p} _ {n/p})$

然后通过考虑 $i/p$的取值来提取公因数（注意最后一项要单独考虑……）

$= \sum_{i=0}^{k/p-1}(C_{n/p}^i * \sum_{j=0}^{p-1} C_{n \bmod p}^j)+ C_{n/p}^{k/p}*\sum_{i=0}^{k \bmod p} C^i_{n \bmod p}$

然后前面的式子提取一下公因式，用 S 的定义化简一下：

$=S_{n/p}^{k/p-1}\times S_{n \bmod p}^{p-1}+C_{n/p}^{k/p}\times S_{n \bmod p}^{k \bmod p}$

于是我们可以打表出 n 与 k 小于 p 的所有 S 和 C，然后运用递归和卢卡斯定理的手法来求解。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
LL read() {
    LL q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+(LL)(ch-'0'),ch=getchar();
    return q;
}
int T,mod=2333;
LL n,k,c[2340][2340],s[2340][2340];
inline int qm(int x){return x>=mod?x-mod:x;}
void init() {
    int i,j;
    for(i=0;i<mod;++i) {
        c[i][0]=1;
        for(j=1;j<=i;++j) c[i][j]=qm(c[i-1][j]+c[i-1][j-1]);
    }
    for(i=0;i<mod;++i) {
        s[i][0]=1;
        for(j=1;j<mod;++j) s[i][j]=qm(s[i][j-1]+c[i][j]);
    }
}
int lucas(LL n,LL k) {
    if(k>n) return 0;
    if(n<mod&&k<mod) return c[n][k];
    return lucas(n/mod,k/mod)*c[n%mod][k%mod]%mod;
}
int work(LL n,LL k) {
    if(n<mod&&k<mod) return s[n][k];
    int re=lucas(n/mod,k/mod)*s[n%mod][k%mod]%mod;
    return qm(work(n/mod,k/mod-1)*s[n%mod][mod-1]%mod+re);
}
int main()
{
    freopen("quondam.in","r",stdin);
    freopen("quondam.out","w",stdout);
    T=read();init();
    while(T--) n=read(),k=read(),printf("%d\n",work(n,k));
    return 0;
}

T3

题目分析:

考虑枚举剩余血量，那么不能用了的攻击可以强制用掉，然后玩多重背包。

那么我们可以根据攻击伤害来枚举剩余血量。

其实还可以排序后一边算多重背包一边计算答案。

然后用队列优化（计数问题无需单调队列）一下多重背包即可。

注意假如从大到小排序后，剩余血量应大于等于 w(i), 那么要强制用掉前 i-1 个技能，并且第 i 个技能要留下一个，跑多重背包。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
const int N=505,M=100005;
int n,m,f[2][M],tot,t,ans,mod=19260817;
struct node{int num,w;}a[N];
bool cmp(node x,node y) {return x.w<y.w;}
inline int qm(int x){return x>=mod?x-mod:x;}
void work(int num,int w) {
    int c,j,he,sum;
    for(c=0;c<w;++c) {
        he=sum=0;
        for(j=0;j<=(m-c)/w;++j) {
            sum=qm(sum+f[t^1][j*w+c]);
            //直接计算所有能达成的情况，用队列排除不能达成的即可
            while(j-he>num) sum=qm(sum-f[t^1][w*he+c]+mod),++he;
            f[t][j*w+c]=sum;
        }
    }
}
int main()
{
    freopen("refrigerator.in","r",stdin);
    freopen("refrigerator.out","w",stdout);
    int i,j;
    n=read(),m=read(),--m;
    for(i=1;i<=n;++i)
        a[i].num=read(),a[i].w=read(),tot+=a[i].num*a[i].w;
    if(tot<=m) {puts("1");return 0;}
    sort(a+1,a+1+n,cmp);
    f[0][0]=1;
    for(i=n;i>=1;--i) {
        tot-=a[i].num*a[i].w,t^=1;
        work(a[i].num-1,a[i].w);
        for(j=max(0,m-tot-a[i].w+1);j<=m-tot;++j) ans=qm(ans+f[t][j]);
        work(a[i].num,a[i].w);//重新计算
    }
    printf("%d\n",ans);
    return 0;
}