茅山道术

似乎这个一个普通的 \(dp\) 就能搞掉。。

\[f_i = f_{i-1} + [i - pre_{a_i} > 1] * f_{pre_{a_i}} \]

愉快 \(ac\)

#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register signed i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
	#define sb(x) cout<<#x" = "<<x<<' '
	#define jb(x) cout<<#x" = "<<x<<endl
	#define debug cout<<"debug"<<endl
	#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
	char buf[1<<20],*p1 = buf,*p2 = buf; int ak; typedef long long ll; typedef unsigned long long ull;
	class xin_stream{public:template<typename type>inline xin_stream &operator >> (type &s)
	{
		register int f = 0;s = 0; register char ch = gc();
		while(!isdigit(ch)) {f |= ch == '-'; ch = gc();}
		while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch  xor 48),ch = gc(); return s = f ? -s : s,*this;
	}}io;
}
using namespace xin_io; static const int maxn = 1e7+10,inf = 1e9+7; const ll llinf = 1e18+7;
namespace xin
{
	const int mod = inf;
	int f[maxn];
	int pre[maxn],a[maxn];
	int n;
	inline short main()
	{
		freopen("magic.in","r",stdin); freopen("magic.out","w",stdout);
		io >> n;
		try(i,1,n) io >> a[i],pre[i] = n + 3;
		f[1] = 1; pre[a[1]] = 1;
		try(i,2,n)
		{
//			sb(a[i]); jb(pre[a[i]]);
			f[i] = (f[i-1] + (i - pre[a[i]] > 1) * f[pre[a[i]]]) % mod;
			pre[a[i]] = i;
		}
		cout<<f[n]<<endl;
		return 0;
	}
}
signed main() {return xin::main();}

泰拳警告

可以发现式子：

\[Ans = \sum_k (p+1)(\frac{p}{p+2})^k(\frac{1}{p+2})^{n-k}\dbinom{n}{k} \sum_{numwin}\dbinom{n-k}{sheng} \]

\[= \sum_k \frac{\;p^k\;(p+1)}{(p+2)^n} \frac{2^n - \dbinom{n/2}{k}(if\;(n-k)is\;even)}{n} \]

然后预处理一下

\(\mathcal O(n)\)

#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register signed i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
	#define sb(x) cout<<#x" = "<<x<<' '
	#define jb(x) cout<<#x" = "<<x<<endl
	#define debug cout<<"debug"<<endl
	#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
	char buf[1<<20],*p1 = buf,*p2 = buf; int ak; typedef long long ll; typedef unsigned long long ull;
	class xin_stream{public:template<typename type>inline xin_stream &operator >> (type &s)
	{
		register int f = 0;s = 0; register char ch = gc();
		while(!isdigit(ch)) {f |= ch == '-'; ch = gc();}
		while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch  xor 48),ch = gc(); return s = f ? -s : s,*this;
	}}io;
}
using namespace xin_io; static const int maxn = 3e6+10,inf = 1e9+7; const ll llinf = 1e18+7;
#define int long long
namespace xin
{
	const int mod = 998244353;
	auto ksm = [](int x,int y,int ret = 1) -> int
	{
		while(y)
		{
			if(y & 1) ret = ret * x % mod;
			x = x * x % mod; y >>= 1;
		}
		return ret;
	};
	int n,p,ans = 0;

	int fac[maxn],invfac[maxn],fangp[maxn],fang2[maxn];
	auto C = [](int n,int m) -> int
	{
		if(m > n) return 0;
		if(m == n) return 1;
		return fac[n] * invfac[m] % mod * invfac[n-m] % mod;
	};
	
	inline short main()
	{
		freopen("fight.in","r",stdin); freopen("fight.out","w",stdout);

		io >> n >> p;

		fac[0] = fac[1] = 1; fangp[1] = p; fangp[0] = 1;
		
		try(i,2,n) fac[i] = fac[i-1] * i % mod,fangp[i] = fangp[i-1] * p % mod;
		invfac[n] = ksm(fac[n],mod-2);
		throw(i,n-1,1) invfac[i] = invfac[i+1] * (i + 1) % mod;
		invfac[0] = 1;

		int pinv = ksm(ksm(p + 2,n),mod - 2),inv2 = ksm(2,mod-2);
//		jb(pinv);
	
		fang2[1] = 2; fang2[0] = 1;
		try(i,2,n) fang2[i] = fang2[i-1] * 2 % mod;

		try(ping,0,n-1)
		{
			register int k = n - ping;
			int temp = (fang2[k] - (!(k & 1)) * C(k,k/2) + mod) % mod * inv2 % mod;
			(ans += fangp[ping] * (ping + 1) % mod * pinv % mod * C(n,ping) % mod * temp % mod) %= mod;
		}
		
		cout<<ans<<endl;
		
		return 0;
	}
}
signed main() {return xin::main();}

万猪拱塔

挺妙的

就是我们将每一个选择的权值染黑，然后如果合法组成一个矩形，那么图中一定有四个只被染了一个的小正方形。

然后我们分四个位置转移。

然后没啥了。。

对了，要线段树维护信息。

%: pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(signed i=a;i<=b;++i)
#define throw(i,a,b) for(signed i=a;i>=b;--i)
#define go(i,x) for(signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
	#define file(a,b) freopen(#a"","r",stdin),freopen(#b"","w",stdout)
	#define sb(x) cout<<#x" = "<<x<<' '
	#define jb(x) cout<<#x" = "<<x<<endl
	#define debug cout<<"debug"<<endl
	#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
	char buf[1<<20],*p1 = buf,*p2 = buf; int ak; typedef long long ll; typedef unsigned long long ull;
	class xin_stream{public:template<typename type>inline xin_stream &operator >> (type &s)
	{
		register int f = 0;s = 0; register char ch = gc();
		while(!isdigit(ch)) {f |= ch == '-'; ch = gc();}
		while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch  xor 48),ch = gc(); return s = f ? -s : s,*this;
	}}io;
}
using namespace xin_io; static const int maxn = 1e6+10,inf = 1e9+7; const ll llinf = 1e18+7;
namespace xin
{
	auto min = [](int x,int y) -> int{return x < y ? x : y;};
	auto max = [](int x,int y) -> int{return x > y ? x : y;};
	const int mod = 998244353;
	class xin_seg
	{
		private:
			#define ls(fa) (fa << 1)
			#define rs(fa) (fa << 1 | 1)
			inline void up(int fa)
			{
				if(t[ls(fa)].minn > t[rs(fa)].minn)
					t[fa].minn = t[rs(fa)].minn,t[fa].cnt = t[rs(fa)].cnt,t[fa].s = t[rs(fa)].s;

				if(t[ls(fa)].minn == t[rs(fa)].minn)
					t[fa].minn = t[ls(fa)].minn,t[fa].cnt = t[ls(fa)].cnt + t[rs(fa)].cnt,t[fa].s = t[ls(fa)].s + t[rs(fa)].s;

				if(t[ls(fa)].minn < t[rs(fa)].minn)
					t[fa].minn = t[ls(fa)].minn,t[fa].cnt = t[ls(fa)].cnt,t[fa].s = t[ls(fa)].s;
			}
			inline void down(int fa)
			{
				if(!t[fa].debt) return ;
				
				t[ls(fa)].minn += t[fa].debt; t[rs(fa)].minn += t[fa].debt;
				t[ls(fa)].debt += t[fa].debt; t[rs(fa)].debt += t[fa].debt;

				t[fa].debt = 0;
			}
		public:
			class xin_tree{public:int debt,minn,cnt,s;}t[maxn<<2];
			void build(int fa,int l,int r)
			{
				if(l == r) return t[fa].minn = inf,void();
				register int mid = l + r >> 1;
				build(ls(fa),l,mid); build(rs(fa),mid+1,r);
				up(fa);
			}
			void update(int fa,int l,int r,int ql,int qr,int val)
			{
				//sb(ql); sb(qr); sb(l); jb(r);
				if(ql > qr) return ;
				if(ql <= l and qr >= r)
				{
					t[fa].minn += val; t[fa].debt += val;
					return;
				}
				down(fa);
				register int mid = l + r >> 1;
				if(ql <= mid) update(ls(fa),l,mid,ql,qr,val);
				if(qr >  mid) update(rs(fa),mid+1,r,ql,qr,val);
				up(fa);
			}
			void modify(int fa,int l,int r,int pos,int val)
			{
				if(l == r)
				{
					t[fa].minn = val; t[fa].s = l; t[fa].cnt = 1;
					return ;
				}
				register int mid = l + r >> 1;
				if(pos <= mid) modify(ls(fa),l,mid,pos,val);
				else modify(rs(fa),mid+1,r,pos,val);
				up(fa);
			}
	}t;

	int n,m,ans = 0;
	class xin_data
	{
		public:
			int x,y;
			xin_data(){}
			xin_data(int x,int y):x(x),y(y){}
	}d[maxn];
	int temp[5];
	int **a;

	inline short main()
	{
		file(pig.in,pig.out);
		register std::function<void()> zhuan = [](){};


		io >> n >> m;
		a = new int *[n + 3];
		try(i,1,n) {a[i] = new int[m+3]; try(j,1,m) io >> a[i][j],d[a[i][j]] = xin_data(i,j);}
		a[n + 1] = new int[m+3]; a[0] = new int [m + 3];
		try(i,0,n+1) a[i][0] = a[i][m+1] = inf;
		try(j,0,m+1) a[0][j] = a[n+1][j] = inf;
		
		t.build(1,1,n*m);

		try(r,1,n*m)
		{
			register int x = d[r].x,y = d[r].y;
			
			auto work1 = [=]()mutable -> void //zuo_shang
			{
				temp[1] = a[x-1][y-1]; temp[2] = a[x-1][y]; temp[3] = a[x][y-1]; temp[4] = a[x][y];
				std::sort(temp+1,temp+5);
				int pos; try(i,1,4) if(temp[i] == r) {pos = i;temp[i] = r - 1; break;}
				int f = 1;
				throw(i,pos,1)
					t.update(1,1,n*m,temp[i-1]+1,temp[i],f),f = -f;
			};
			
			auto work2 = [=]()mutable -> void //you_shang
			{
				temp[1] = a[x][y-1]; temp[2] = a[x+1][y-1]; temp[3] = a[x+1][y]; temp[4] = a[x][y];
				std::sort(temp+1,temp+5);
				int pos; try(i,1,4) if(temp[i] == r) {pos = i; temp[i] = r - 1;break;}
				int f = 1;
				throw(i,pos,1)
					t.update(1,1,n*m,temp[i-1]+1,temp[i],f),f = -f;
			};
			
			auto work3 = [=]()mutable -> void //zuo_xia
			{
				temp[1] = a[x][y]; temp[2] = a[x-1][y]; temp[3] = a[x-1][y+1]; temp[4] = a[x][y+1];
				std::sort(temp+1,temp+5);
				int pos; try(i,1,4) if(temp[i] == r) {pos = i; temp[i] = r - 1;break;}
				int f = 1;
				throw(i,pos,1)
					t.update(1,1,n*m,temp[i-1]+1,temp[i],f),f = -f;
			};
			
			auto work4 = [=]()mutable -> void //you_xia
			{
				temp[1] = a[x][y]; temp[2] = a[x][y+1]; temp[3] = a[x+1][y]; temp[4] = a[x+1][y+1];
				std::sort(temp+1,temp+5);
				int pos; try(i,1,4) if(temp[i] == r) {pos = i; temp[i] = r - 1;break;}
				int f = 1;
				throw(i,pos,1)
					t.update(1,1,n*m,temp[i-1]+1,temp[i],f),f = -f;
			};

			t.modify(1,1,n*m,r,4);
			work1(); work2(); work3(); work4();
			ans += (t.t[1].minn == 4) * (r * t.t[1].cnt - t.t[1].s + t.t[1].cnt);
			ans %= mod;
		}
		
		cout<<ans<<endl;

		return 0;
	}
}
signed main() {return xin::main();}

抑郁刀法

咕了。。。。