P6308 「Wdsr-1」笨蛋结构

· · 题解

Why so fancy?

根据套路，第 i 次操作相当于对于 [s_i, s_i + l_i) 加上一个多项式 w_i(x-s_i+1)^{k_i}

没了

用二项式定理不知道的左转百度百科展开，则我们相当于给这个区间里 的 j 次项（0 \le j \le k_i）加上了某个相同（容易发现只和 i 有关）的系数，直接差分即可。

最后用差分数组还原原数组，然后直接算多项式就行。

注：这里提到的多项式就是字面意思的多项式，暴力算即可，别被名字劝退了

code:

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#define miu 1000007
using namespace std;
typedef unsigned long long u64;
typedef unsigned int       u32;
u32 MT[624],idx;
void _init(u32 seed){
    MT[0]=seed; idx=0; for(int i=1;i<624;++i) 
    MT[i]=(0x6c078965*(MT[i-1]^((MT[i-1])>>30)+i));
}
void _gene(){
    for(int i=0;i<624;++i){
        int x=MT[i]&0x80000000+(MT[(i+1)%624]&0x7fffffff);
        MT[i]=MT[(i+397)%624]^(x>>1);
        if(x&2)MT[i]^=0x9908b0df;
    }
}
u32  _calc(){
    if(!idx) _gene(); int x=MT[idx];
    x^=x>>11,x^=(x<<7)&(0x9d2c5680);
    x^=(x<<15)&0xefc60000,x^=x>>18;
    idx=(idx+1)%624; return x;
}
u64 _get(){u64 ret=_calc()*_calc(); return ret;}
u64 _get(u64 _l,u64 _r){return _get()%(_r-_l+1ull)+_l;}
void input(int &_n,int &_m,int &_q,int *_S,int *_L,u64 *_W,int *_K){
    u32 seed; scanf("%d%d%d%u",&_n,&_m,&_q,&seed); _init(seed); int i=1;
    if(_n>100) for(;i<=_q/4;++i){
        int _a=_get(1,_n-100),_b=_get(_a+_m,_a+_m+1),_l=_b-_a+1,_k=_get(0,_m);
        u64 _w=_get(); _S[i]=_a,_L[i]=_l,_W[i]=_w,_K[i]=_k;
    }
    if(_n>100) for(;i<=_q/2;++i){
        int _a=_get(1,100),_b=_get(_n-100,_n),_l=_b-_a+1,_k=_get(0,_m);
        u64 _w=_get(); _S[i]=_a,_L[i]=_l,_W[i]=_w,_K[i]=_k;
    }
    for(;i<=_q;++i){
        int _a=_get(1,_n),_b=_get(1,_n); if(_a>_b) swap(_a,_b);
        int _l=_b-_a+1,_k=_get(0,_m); u64 _w=_get();
        _S[i]=_a,_L[i]=_l,_W[i]=_w,_K[i]=_k;
    }
}
void output(int n,u64 *R){
    u64 ret=n^_get(); for(int i=1;i<=n;i++) ret^=_get()+R[i];
    printf("%llu\n",ret);
}
u64 C[17][17]; //组合数，其实你打表也行，反正就前10行
int n, m, q, s[miu], l[miu], k[miu];
u64 w[miu], r[miu], c[miu][17]; //c是系数（差分）矩阵
signed main() {
    input(n, m, q, s, l, w, k); 
    for(int i = 0; i <= m; ++i) {
        C[i][0] = 1ull;
        for(int j = 1; j <= i; ++j) C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }
    for(int i = 1; i <= q; ++i) {
        u64 a = w[i];
        for(int j = k[i]; j >= 0; --j) {
            c[s[i]][j] += a * C[k[i]][j];
            c[s[i] + l[i]][j] -= a * C[k[i]][j];
            a *= (1 - s[i]);
        }
    }
    for(int i = 1; i <= n; ++i) {
        u64 v = 1ull;
        for(int j = 0; j <= m; ++j) {
            c[i][j] += c[i - 1][j];
            r[i] += c[i][j] * v;
            v *= i;
        }
    } 
    output(n, r);
    return 0;
}