Loading... ## 题意 给定一个长为 $n$ 的序列 $a$，$\forall i\in[1,n],a_i\in[1,k]$，有序列 $b$，满足 $a$ 是 $b$ 的子序列，$b_i \in [1,k]$ 且 $b$ 的长度为 $m$。 求满足条件的 $b$ 数组个数。 ## 题解 考虑用总数减去不合法的。考虑只匹配了前 $i$ 位，假设某个位置匹配了 $c$ 那么到下一个匹配位置都不能出现 $c$ 所以方案数是 ${m\choose i}\left(k-1\right)^{m-i}$，所以答案是： $$ k^m-\sum_{i=0}^{m-1}{m\choose i}\left(k-1\right)^{m-i} $$ ```cpp #include<bits/stdc++.h> // #define ONLINE_JUDGE #define INPUT_DATA_TYPE int #define OUTPUT_DATA_TYPE int inline __attribute((always_inline)) INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10^48);return;} #define MODINT_TYPE long long #define barK (64) namespace MODINT{ unsigned long long d; __uint128_t m; inline __attribute((always_inline)) void init(const long long &mod){ m=(((__uint128_t)1)<<barK)/(d=mod); return; } inline __attribute((always_inline)) unsigned long long mod(const unsigned long long &x){ register unsigned long long w=(m*x)>>barK; w=x-w*d; return w>=d?w-d:w; } MODINT_TYPE exgcd(MODINT_TYPE a,const MODINT_TYPE b,MODINT_TYPE &x,MODINT_TYPE &y){ if(!b){ x=1; y=0; return a; } MODINT_TYPE d=exgcd(b,a%b,y,x); y-=a/b*x; return d; } inline __attribute((always_inline)) MODINT_TYPE inv(const MODINT_TYPE &n,const MODINT_TYPE &p){ MODINT_TYPE x,y; exgcd(n,p,x,y); x%=p; return x>=0?x:x+p; } struct MODNUM{ MODINT_TYPE val; inline __attribute((always_inline)) MODNUM(const MODINT_TYPE &x){ if(x<0){ val=d-mod(-x); if(val>=d) val-=d; }else val=mod(x); return; } inline __attribute((always_inline)) MODNUM(){val=0;} inline __attribute((always_inline)) MODNUM operator + (const MODNUM& o) const{return (MODNUM){(val+o.val>=d)?(val+o.val-d):(val+o.val)};} inline __attribute((always_inline)) MODNUM operator + (const MODINT_TYPE& o) const{return *this+MODNUM(o);} friend inline __attribute((always_inline)) MODNUM operator + (const MODINT_TYPE &o,const MODNUM&a){return a+o;} inline __attribute((always_inline)) MODNUM operator - (const MODNUM& o) const{return (MODNUM){(val-o.val<0)?(val-o.val+d):(val-o.val)};} inline __attribute((always_inline)) MODNUM operator - (const MODINT_TYPE& o) const{return *this-MODNUM(o);} friend inline __attribute((always_inline)) MODNUM operator - (const MODINT_TYPE &o,const MODNUM&a){return MODNUM(o)-a;} inline __attribute((always_inline)) MODNUM operator * (const MODNUM& o) const{return (MODNUM){mod(val*o.val)};} inline __attribute((always_inline)) MODNUM operator * (const MODINT_TYPE& o) const{return *this*MODNUM(o);} friend inline __attribute((always_inline)) MODNUM operator * (const MODINT_TYPE &o,const MODNUM&a){return a*o;} inline __attribute((always_inline)) MODNUM operator / (const MODNUM& o) const{return (MODNUM){mod(val*inv(o.val,d))};} inline __attribute((always_inline)) MODNUM operator / (const MODINT_TYPE& o) const{return *this/MODNUM(o);} friend inline __attribute((always_inline)) MODNUM operator / (const MODINT_TYPE &o,const MODNUM&a){return MODNUM(o)/a;} inline __attribute((always_inline)) MODNUM operator ++(){ ++val; if(val>=d) val-=d; return *this; } inline __attribute((always_inline)) MODNUM operator ++(const int){ MODNUM tmp=*this; ++val; if(val>=d) val-=d; return tmp; } inline __attribute((always_inline)) MODNUM operator --(){ --val; if(val<0) val+=d; return *this; } inline __attribute((always_inline)) MODNUM operator --(const int){ MODNUM tmp=*this; --val; if(val<0) val+=d; return tmp; } inline __attribute((always_inline)) MODNUM& operator += (const MODNUM& o) {return *this=*this+o;} inline __attribute((always_inline)) MODNUM& operator += (const MODINT_TYPE& o) {return *this=*this+o;} inline __attribute((always_inline)) MODNUM& operator -= (const MODNUM& o) {return *this=*this-o;} inline __attribute((always_inline)) MODNUM& operator -= (const MODINT_TYPE& o) {return *this=*this-o;} inline __attribute((always_inline)) MODNUM& operator *= (const MODNUM& o) {return *this=*this*o;} inline __attribute((always_inline)) MODNUM& operator *= (const MODINT_TYPE& o) {return *this=*this*o;} inline __attribute((always_inline)) MODNUM& operator /= (const MODNUM& o) {return *this=*this/o;} inline __attribute((always_inline)) MODNUM& operator /= (const MODINT_TYPE& o) {return *this=*this/o;} inline __attribute((always_inline)) operator MODINT_TYPE(){return val;} }; }; #define QPOW_DATA_TYPE MODINT::MODNUM #define QPOW_DATA_E_TYPE int QPOW_DATA_TYPE qpow(register QPOW_DATA_TYPE base,register QPOW_DATA_E_TYPE e){ register QPOW_DATA_TYPE res=1; while(e){ if(e&1) res*=base; base*=base; e>>=1; } return res; } void solve(){ register int i; register MODINT::MODNUM res=0,fact=1,A=1; int n=read();int m=read();int k=read(); res=qpow(k,m); for(i=0;i<n;++i){ read(); res-=A/fact*qpow(k-1,m-i); fact*=(i+1),A*=(m-i); } print(res),putchar('\n'); } int main(){ #ifndef ONLINE_JUDGE freopen("name.in", "r", stdin); freopen("name.out", "w", stdout); #endif MODINT::init(1000'000'007); register int i; int T=read(); while(T--) solve(); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; } ``` 最后修改：2024 年 03 月 15 日 © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用，请随意赞赏