/* Creation Date - 26-01-2023 */ /* Creation Time - 21:32:07.33 */ #define ill #define mod_2 /* Written By : mafailure In the name of God O Allah, May you grant peace and honor on Muhammad and his family. Allahumm-a-Sall-iAla Muhammad-in Wa Al-i Muhammad */ #ifdef LOCAL #define AATIF_DEBUG #endif /*Add -DLOCAL in compiler command to trigger it*/ #include #include // Common file #include #include // for less using namespace std; using namespace __gnu_pbds; #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define endl "\n" /*------------------------int to long long -----------------*/ #ifdef ill #define int long long #endif /*---------------------------DEBUG HELPER--------------------------------------*/ template ostream& operator<<(ostream &os, const vector &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; } template ostream& operator<<(ostream &os, const array &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; } template ostream& operator<<(ostream &os, const pair &p) { return os << '(' << p.first << ", " << p.second << ')'; } template ostream& operator<<(ostream & os,const map & mapp){ os<<"{"; string sep=""; for(const auto& x:mapp)os< ostream & operator<<(ostream & os,const set & sett){os<<'{'; string sep=""; for(const auto & x:sett)os< void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); } #ifdef AATIF_DEBUG #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #else #define dbg(...) #endif //#define int long long // int dx[]={-1,1,0,0}; int dy[]={0,0,1,-1}; // int dx[]={2,2,-2,-2,1,1,-1,-1}; int dy[]={1,-1,1,-1,2,-2,2,-2}; #ifndef mod_2 long long mod = 1e9 + 7; #else long long mod =998244353; #endif const double eps=1e-9; typedef vector vi; typedef vector vvi; typedef vector vs; typedef vector vb; typedef pair ii; typedef vector< pair< int, int > > vii; typedef map mii; typedef pair pip; typedef pair ppi; #define arrinp(arr,init,final,size,type) type* arr=new type[size];for(int i=init;i>arr[i]; #define cr2d(arr,n,m,t) t**arr=new t*[n];for(int i=0;i>t; while(t--) #define takeInp(n) int n;cin>>n; #define fr(i,init,final) for(int i=init;i=final;i--) #define Fr(i,final) for(int i=0;i=0;i--) #define fi first #define se second #define mp make_pair #define pb push_back #define all(c) (c).begin(),(c).end() #define rall(c) (c).rbegin(),(c).rend() #define debug(x) cerr<<">value ("<<#x<<") : "< mapp; struct custom_hash { static uint64_t splitmix64(uint64_t x) { /* http://xorshift.di.unimi.it/splitmix64.c */ x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; /*---------------------------ORDERED SET--------------------------------------*/ typedef tree, rb_tree_tag, tree_order_statistics_node_update> ordered_set; /*----------------------------------------------------------------------------*/ vi init(string s) { istringstream sin(s); int n; vi arr; while(sin>>n)arr.push_back(n); return arr; } int power(int x, int y) { if(y==0)return 1; int u=power(x,y/2); u=(u*u)%mod; if(y%2)u=(x*u)%mod; return u; } int gcd(int a,int b) { if(a>b)&1;} //786 121 786 121 786 121 786 121 786 121 786 121 786 121 786 121 786 121 /*========================CODE*****CODE****CODE======================*/ const int N=1e5+5; int pw[N][6]; int c[6][6]; int ncr(int n,int r){return c[n][r];} template class segTree { public: #define left (p<<1) #define right (left|1) #define mid ((l+r)>>1) #define toleft left,l,mid #define toright right,mid+1,r int n; vector t; vector lazy; vector a; int k; vector zero; //T tmp; segTree(int n,int k):n(n),k(k),t(4*n),lazy(4*n),zero(4*n){} T mer(T a, T b) { T c; fr(i,0,k+1)c[i]=add(a[i],b[i]); return c; } void build(int p,int l,int r) { if(l==r) { t[p][0]=r-l+1; //t[p]=a[l]; //zero[p]=1; return void(); } build(toleft); build(toright); t[p][0]=r-l+1; //t[p]=mer(t[left],t[right]); //zero[p]=zero[left]+zero[right]; } void push(int p,int l,int r) { if(lazy[p]==0)return; frr(i,k,1) { int c=t[p][i]; int f=0; fr(j,0,i+1) { f=add(f,mul(ncr(i,j),mul(pw[lazy[p]][i-j],t[p][j]))); } t[p][i]=f; } /*if(zero[p]) { fr(i,0,k+1) t[p][i]=add(t[p][i],mul(zero[p],pw[lazy[p]][i])); zero[p]=0; }*/ if(l!=r) { lazy[left]+=lazy[p]; lazy[right]+=lazy[p]; } lazy[p]=0; } T query(int p,int l,int r,int i,int j) { push(p,l,r); if(i<=l&&r<=j)return t[p]; if(j<=mid)return query(toleft,i,j); if(i>mid)return query(toright,i,j); return mer(query(toleft,i,j),query(toright,i,j)); } template void lazy_oper(int p,int l,int r,V val,Args...args) { lazy[p]+=val; } template void update(int p,int l,int r,int i,int j,V... val) { push(p,l,r); if(rj)return void(); if(i<=l&&r<=j) { lazy_oper(p,l,r,val...); push(p,l,r); return; } update(toleft,i,j,val...); update(toright,i,j,val...); t[p]=mer(t[left],t[right]); } #undef toright #undef toleft #undef mid #undef right #undef left }; signed main() { IOS fr(i,1,N) { pw[i][0]=1; fr(j,1,6)pw[i][j]=mul(i,pw[i][j-1]); } fr(i,0,6)fr(j,0,i+1)if(j==0||j==i)c[i][j]=1; else c[i][j]=add(c[i-1][j],c[i-1][j-1]); w(T) { int n,k; cin>>n>>k; segTree>seg(n,k); seg.build(1,0,n-1); using T=array; vi a(n); fr(i,0,n)cin>>a[i],a[i]--; vector nxt(n,n); int ans=0; frr(i,n-1,0) { seg.update(1,0,n-1,i,nxt[a[i]]-1,1); ans=add(ans,seg.t[1][k]); nxt[a[i]]=i; } cout<

sumrangepow

Code examples by languages