各省省选试题选做

发表于 阅读次数：

任务艰巨，慢慢啃吧。。。

山东

SDOI2019

移动金币

题目链接

solution:我蒯我自己系列，详见SDOI2011黑白棋游戏，只不过将nimk转成了阶梯nim而已。先算奇数堆的：设f[i][j]表示前i位异或都是0，用的石子总数是j的方案数，每次O(m)转移，总复杂度是O(nmlogn)的。然后对剩下的偶数堆和最后一堆算个重排即可。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define gc getchar()
inline int read(){
    register int x(0),f(1);register char c(gc);
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
    return f*x;
}
const int N=210000,P=1e9+9;
int jc[N],invjc[N],f[20][N],n,m,K,ans;
int quickpow(int a,int b){
    int ans=1,base=a;
    while(b){
        if(b&1)ans=1ll*ans*base%P;
        base=1ll*base*base%P;
        b>>=1;
    }
    return ans;
}
void pre(int n){
    register int i;
    jc[0]=1;
    for(i=1;i<=n;i++)jc[i]=1ll*jc[i-1]*i%P;
    invjc[n]=quickpow(jc[n],P-2);
    for(i=n-1;i>=0;i--)invjc[i]=1ll*invjc[i+1]*(i+1)%P;
}
inline int C(int m,int n){
    if(m<n)return 0;
    return 1ll*jc[m]*invjc[m-n]%P*invjc[n]%P;
}
int main(){
    register int i,j,k;
    pre(150000);
    n=read();m=read();
    int all=C(n,m);
    n-=m;
    K=(m+1)/2;
    m=m-K+1;
    for(k=0;k<=K&&k<=n;k+=2)f[0][k]=C(K,k);
    for(i=1;i<=19;i++)
        for(j=0;j<=n;j++)
            for(k=0;k<=K&&k*(1<<i)<=j;k+=2)
                f[i][j]=(1ll*f[i][j]+1ll*f[i-1][j-k*(1<<i)]*C(K,k)%P)%P;	
    for(i=0;i<=n;i++)
        ans=(1ll*ans+1ll*f[19][i]*C(n-i+m-1,m-1)%P)%P;
    cout<<(all-ans+P)%P;
    return 0;
}

快速查询

题目链接

solution:大概就是要支持O(1)的全局加减，单点修改，全局推平，询问全局和或者单点求值。只要维护一下乘法标记和加法标记就可以了，然后单点赋值就把它赋值成\frac{val-tagsum}{tagmul}即可，这样任意一个点乘上/加上全局标记后意义都是正确的。但是这里出题人很恶意的卡了tagmul\equiv0的情况，所以会出现找不到逆元的情况，然而一个乘法标记是0的非0数列和一个乘法标记是1的全0数列是等价的，直接推平即可，而非0的数字个数是有保证的。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<tr1/unordered_map>
using namespace std;
#define int long long
tr1::unordered_map<int,int> m;
#define gc getchar()
inline int read(){
    register int x(0),f(1);register char c(gc);
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
    return f*x;
}
const int N=2100000,P=1e7+19;
int n,Q,t,a[N],b[N];
struct node{
    int opt,x,y;
}q[N];
int tagsum,tagmul=1,ans,sum;
int quickpow(int a,int b){
    int ans=1,base=a;
    while(b){
        if(b&1)ans=1ll*ans*base%P;
        base=1ll*base*base%P;
        b>>=1;
    }
    return ans;
}
signed main(){
    register int i;
    n=read();Q=read();
    for(i=1;i<=Q;i++){
        q[i].opt=read();
        if(q[i].opt==1)q[i].x=read(),q[i].y=(read()%P+P)%P;
        else if(q[i].opt==6)continue;
        else q[i].x=(read()%P+P)%P;
    }
    t=read();
    for(i=1;i<=t;i++)a[i]=read(),b[i]=read();
    for(i=1;i<=t*Q;i++){
        int u1=(i-1)/Q+1,u2=(i-1)%Q+1,u=(1ll*a[u1]+1ll*u2*b[u1]%Q)%Q+1;
        switch(q[u].opt){
            case 1:{
                sum=(sum-m[q[u].x]+P)%P;
                m[q[u].x]=1ll*(q[u].y-tagsum+P)*quickpow(tagmul,P-2)%P;
                sum=(sum+m[q[u].x]+P)%P;
                break;
            }
            case 2:{
                (tagsum+=q[u].x)%=P;
                break;
            }
            case 3:{
                tagsum=1ll*tagsum*q[u].x%P;tagmul=1ll*tagmul*q[u].x%P;
                if(!tagmul){
                    tagmul=1;sum=0;m.clear();
                }
                break;
            }
            case 4:{
                tagmul=1;tagsum=q[u].x;sum=0;m.clear();
                break;
            }
            case 5:{
                ans=(ans+1ll*m[q[u].x]*tagmul%P+tagsum)%P;
                break;
            }
            case 6:{
                ans=(1ll*ans+1ll*sum*tagmul%P+1ll*tagsum*n%P)%P; 
                break;
            }
        }
    }
    cout<<ans;
    return 0;
}
0%