Submission #61384147

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline
#define pii pair<int,int>
#define x first
#define y second
#define gc getchar()
#define rd read()
#define debug() puts("------------")
namespace yzqwq{
    il int read(){
        int x=0,f=1;char ch=gc;
        while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc;}
        while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=gc;
        return x*f;
    }
    il int qmi(int a,int b,int p){
        int ans=1;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline
#define pii pair<int,int>
#define x first
#define y second
#define gc getchar()
#define rd read()
#define debug() puts("------------")

namespace yzqwq{
    il int read(){
        int x=0,f=1;char ch=gc;
        while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc;}
        while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=gc;
        return x*f;
    }
    il int qmi(int a,int b,int p){
        int ans=1;
        while(b){
            if(b&1) ans=ans*a%p;
            a=a*a%p,b>>=1;
        }
        return ans;
    }
    il int gcd(int a,int b){
        if(!b) return a;
        return gcd(b,a%b);
    }
    il int lcm(int a,int b){
        return a/gcd(a,b)*b;
    }
    il void exgcd(int a,int b,int &x,int &y){
        if(!b) return x=1,y=0,void(0);
        exgcd(b,a%b,x,y);
        int t=x;
        x=y,y=t-a/b*x;
        return ;
    }
    il int F(int n,int a,int b,int c){
        //sum{|_ (ai+b)/c _| i:0~n}
        if(!n) return b/c;
        if(!a) return (n+1)*(b/c);
        if(a>=c||b>=c){
            int x=a/b,y=b/c;
            return n*(n+1)/2*x+(n+1)*y+F(n,a%c,b%c,c);
        }
        int m=(a*n+b)/c;
        return n*m+F(m-1,c,c-b+1,a);
    }
    struct lb{
        int d[64];
        il void print(){
            for(re int i=0;i<63;++i)
            if(d[i]) printf("%lld:%lld\n",i,d[i]);
            return ;
        }
        lb(){memset(d,0,sizeof(d));}
        il void operator +=(int x){
            for(re int i=62;i>=0;--i){
                if(!(x&(1ll<<i))) continue;
                if(d[i]) x^=d[i];
                else return d[i]=x,void(0);
            }
            return ;
        }
        int& operator [](int x){
            return d[x];
        }
        il void operator +=(lb &x){
            for(re int i=62;i>=0;--i)
            if(x[i]) *this+=x[i];
            return ;
        }
        il friend lb operator +(lb &x,lb &y){
            lb z=x;
            for(re int i=62;i>=0;--i)
            if(y[i]) z+=y[i];
            return z;
        }
        il int Max_calc(){
            int ans=0;
            for(re int i=62;i>=0;--i)
            if((ans^d[i])>ans) ans^=d[i];
            return ans;
        }
    };
    mt19937 rnd(time(0));
}
using namespace yzqwq;

const int N=1e6+10,M=1e4+10,p=998244353;
int n,m,a[N];
int dfn[N],low[N],cnt;
int Col,st[N],top;
int col[N],d[N];
bool vis[N];
vector<int> e[N],V[N],E[N],E_[N];
int dp[N],f[M][M];
map<pii,bool> Vis;
int Fuc[N],siz[N],to[N];

il int find(int x){
	if(Fuc[x]==x) return x;
	return Fuc[x]=find(Fuc[x]);
}
il void tj(int u){
	dfn[u]=low[u]=++cnt;
	st[++top]=u;
	vis[u]=1;
	for(auto v:e[u]){
		if(!dfn[v]) tj(v),low[u]=min(low[u],low[v]);
		else if(vis[v]) low[u]=min(low[u],dfn[v]);	
	}
	if(dfn[u]==low[u]){
		++Col;
		while(1){
			int x=st[top];--top;
			vis[x]=0;
			col[x]=Col;++siz[Col];
			V[Col].push_back(x);
			if(x==u) break;
		}
	}
	return ;
}

il void solve(){
	n=rd,m=rd;
	for(re int i=1;i<=n;++i){
		a[i]=rd;Fuc[i]=i;
		e[i].push_back(a[i]);
//		cout<<i<<" "<<a[i]<<"\n";
	}
	for(re int i=1;i<=n;++i) if(!dfn[i]) tj(i);
	for(re int i=1;i<=Col;++i)
	for(auto u:V[i]){
		for(auto v:e[u])
		if(col[v]!=col[u]){
			if(Vis[{i,col[v]}]) continue;
			Vis[{i,col[v]}]=1;
			E[i].push_back(col[v]),++d[col[v]]; 
			E_[col[v]].push_back(i);
			Fuc[find(i)]=find(col[v]);
		}
	}
//	for(re int i=1;i<=n;++i) cout<<col[i]<<" ";
	queue<int> qu;
	for(re int i=1;i<=Col;++i){
		for(re int j=1;j<=m;++j) f[i][j]=1;
		if(!d[i]){
			qu.push(i);dp[i]=siz[i];to[find(i)]=i;
			for(re int j=1;j<=m;++j) f[i][j]=(f[i][j]+f[i][j-1])%p;
		}	
	}
	while(!qu.empty()){
		int u=qu.front();qu.pop();
		for(auto v:E[u]){
			--d[v];
			if(!d[v]){
				to[find(v)]=v;
				for(re int j=1;j<=m;++j)
				for(auto w:E_[v]){
					f[v][j]=(f[v][j]*f[w][j])%p;
				}
				for(re int j=1;j<=m;++j) f[v][j]=(f[v][j]+f[v][j-1])%p;
				qu.push(v);
			}
		}
	}//cout<<f[to[2]][m]<<"\n";
	int sum=1;
	for(re int i=1;i<=Col;++i)
	if(find(i)==i) sum=(sum*f[to[i]][m])%p;
	cout<<sum;
	return ;
}

signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
    int t=1;while(t--)
    solve();
    return 0;
}

Submission Info

Compile Error

Main.cpp: In member function ‘void yzqwq::lb::print()’:
Main.cpp:56:24: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   56 |             for(re int i=0;i<63;++i)
      |                        ^
Main.cpp: In member function ‘void yzqwq::lb::operator+=(long long int)’:
Main.cpp:62:24: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   62 |             for(re int i=62;i>=0;--i){
      |                        ^
Main.cpp: In member function ‘void yzqwq::lb::operator+=(yzqwq::lb&)’:
Main.cpp:73:24: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   73 |             for(re int i=62;i>=0;--i)
      |                        ^
Main.cpp: In function ‘yzqwq::lb yzqwq::operator+(lb&, lb&)’:
Main.cpp:79:24: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   79 |             for(re int i=62;i>=0;--i)
      |                        ^
Main.cpp: In member function ‘long long int yzqwq::lb::Max_calc()’:
Main.cpp:85:24: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   85 |             for(re int i=62;i>=0;--i)
      |                        ^
Main.cpp: In function ‘void solve()’:
Main.cpp:132:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  132 |         for(re int i=1;i<=n;++i){
      |                    ^
Main.cpp:137:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  137 |         for(re int i=1;i<=n;++i) if(!dfn[i]) tj(i);
      |                    ^
Main.cpp:138:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  138 |         for(re int i=1;i<=Col;++i)
      |                    ^
Main.cpp:142:42: warning: address requested for ‘i’, which is declared ‘register’ [-Wextra]
  142 |                         if(Vis[{i,col[v]}]) continue;
      |                                          ^
Main.cpp:151:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  151 |         for(re int i=1;i<=Col;++i){
      |                    ^
Main.cpp:152:28: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  152 |                 for(re int j=1;j<=m;++j) f[i][j]=1;
      |                            ^
Main.cpp:154:32: warning: address requested for ‘i’, which is declared ‘register’ [-Wextra]
  154 |                         qu.push(i);dp[i]=siz[i];to[find(i)]=i;
      |                         ~~~~~~~^~~
Main.cpp:155:36: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  155 |                         for(re int j=1;j<=m;++j) f[i][j]=(f[i][j]+f[i][j-1])%p;
      |                                    ^
Main.cpp:164:44: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  164 |                                 for(re int j=1;j<=m;++j)
      |                                            ^
Main.cpp:168:44: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  168 |                                 for(re int j=1;j<=m;++j) f[v][j]=(f[v][j]+f[v][j-1])%p;
      |                                            ^
Main.cpp:174:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  174 |         for(re int i=1;i<=Col;++i)
      |                    ^

Judge Result