太原建站服务,手机报价大全2021中关村,做网站的天津,登封网站制作网站建设Problem 题目链接 Solution 吼题啊吼题#xff01; 首先如何求本质不同的子序列个数就是 \(f[val[i]]1\sum\limits_{j1}^k f[j]\) 其中 \(f[i]\) 表示的是以 \(i\) 结尾的子序列个数 先把原数列的不同子序列个数求出来#xff0c;然后观察一下这个转移#xff0c;贪心的发现…Problem 题目链接 Solution 吼题啊吼题 首先如何求本质不同的子序列个数就是 \(f[val[i]]1\sum\limits_{j1}^k f[j]\) 其中 \(f[i]\) 表示的是以 \(i\) 结尾的子序列个数 先把原数列的不同子序列个数求出来然后观察一下这个转移贪心的发现每次都是选一个最早出现的 \(i\) 填到序列末尾然后更新这个值。 所以填的部分一定是 \(\frac mk\) 个 \(K\) 的排列还有多出来了 \(m\%k\) 个元素暴力填进去。 每 \(K\) 个元素的转移是一样的可以拿矩乘做。然后多余的部分求前缀积暴力求就行了。 Code #includeset
#includemap
#includecmath
#includequeue
#includecctype
#includevector
#includecstdio
#includecstring
#includeiostream
#includealgorithm
using std::min;
using std::max;
using std::swap;
using std::vector;
const int N105;
const int M1e65;
typedef double db;
typedef long long ll;
#define int long long
const int mod1e97;
#define pb(A) push_back(A)
#define pii std::pairint,int
#define mp(A,B) std::make_pair(A,B)int n,m,k,per[M];
int val[M];pii las[M];struct Mat{int a[N][N];void clear(){memset(a,0,sizeof a);}void init(){clear();for(int i1;ik1;i)a[i][i]1;}void print(){for(int i1;ik1;i,puts())for(int j1;jk1;j)printf(%lld ,a[i][j]);}friend Mat operator*(Mat x,Mat y){Mat z;z.clear();for(int i1;ik1;i){for(int p1;pk1;p){for(int j1;jk1;j)z.a[i][j](z.a[i][j]x.a[i][p]*y.a[p][j]%mod)%mod;}} return z;}
}cs,f,qzh[N];int getint(){int X0,w0;char ch0;while(!isdigit(ch))w|ch-,chgetchar();while( isdigit(ch))XX*10ch-48,chgetchar();if(w) return -X;return X;
}Mat ksm(Mat x,int y){Mat ans;ans.init();while(y){if(y1) ansans*x;xx*x;y1;} return ans;
}signed main(){freopen(sequence.in,r,stdin);freopen(sequence.out,w,stdout);ngetint(),mgetint(),kgetint();int sum0;f.clear();f.a[1][k1]1;for(int i1;ik;i) las[i]mp(0,i);for(int i1;in;i){val[i]getint();int pf.a[1][val[i]];f.a[1][val[i]](sum1)%mod;sum-p;sumf.a[1][val[i]];sum%mod;las[val[i]]mp(i,val[i]);} std::sort(las1,las1k);qzh[0].init();for(int i1;ik;i){per[i]las[i].second;qzh[i].clear();for(int j1;jk1;j) qzh[i].a[j][j]1;for(int j1;jk1;j) qzh[i].a[j][per[i]]1;qzh[i]qzh[i-1]*qzh[i];} csksm(qzh[k],m/k);cscs*qzh[m%k];ff*cs;int ans0;for(int i1;ik;i) (ansf.a[1][i])%mod;printf(%lld\n,ans);return 0;
} 转载于:https://www.cnblogs.com/YoungNeal/p/9780949.html
