【TIOJ 1971】撿豆豆（Beans）

原題連結：http://tioj.infor.org/problems/1971
最近怎麼反而在練選訓題了(汗
明明根本還沒進選訓

這題一整個經典拈題
前55分有顯然的O(MN) SG Value解
比較值得提到的是後面的第三子題和第四子題

我先確定55分自己能拿之後跳過第三的12分開始想後面的33分
因為保證a_i<=20，假設我們能在這個子題實行SG Value的話
首先先觀察到所有>1的SG值都沒有用處，可以直接填上1就好了，0就還是0
於是可以觀察到，對於連續K個的區間，最多只存在2^K種區間SG
又因為第四子題a_i<=20，所以對於一個SG[i]需要呼叫的子問題絕對不低於SG[i-20]，也就是K=20
所以可以保證出現第一個重複的「大小N的區間SG」時，後面的SG結果就會和前面呈現週期性的重複
由於區間SG只有2^20種，轉換後又很方便是整數，所以可以開一個2^20的陣列紀錄每種區間SG出現的時刻
這裡還用map之類的資結絕對是中毒了(?，計算轉換的值可以邊跑邊算，所以是完完全全的O(2^N)
寫起來也不難，找到週期後記得處理一下餘數問題加前面就有88分了，似乎頗賺的(?

最讓我意外的是剩下的12分，因為我第一次拿完88分就直接卡死了只好放棄
直到最近看了某國手的文才發現，據說用O(MN)拿bitset硬開會過！？

......然後真的過了
雖然看他的文章讓我有種我可能假解了的feel，可是看在我執行時間不算久的情況下就算了(X
結論就是，bitset真強大啊OwO~~

	#pragma GCC optimize("Ofast")
	#include <bits/stdc++.h>
	#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	#define ll long long
	#define pb push_back
	#define MEM(i,j) memset(i,j,sizeof i)
	#define F first
	#define S second
	#define ET cout << "\n"
	#define DB(a,s,e) {for(int i=s;i<e;i++) cout << a[i] << " ";ET;}
	using namespace std;
	ll take[20];
	bitset<100000001> SG;
	ll vis[1048576];
	int main()
	{jizz
	ll m,n,i,j,ans=0,x,k,MOD,tmp;
	cin >> m >> n;
	for(i=0;i<n;i++)
	cin >> take[i];
	sort(take,take+n);
	if(m<=100000000)
	{
	for(i=0;i<=m;i++)
	{
	if(SG[i]) ans++;
	else
	for(j=0;j<n && take[j]+i<=m;j++)
	SG[take[j]+i]=1;
	}
	cout << ans << "\n";
	}
	else
	{
	MOD=1<<take[n-1],fill(vis,vis+MOD,-1);
	for(i=0,x=0;i<take[n-1];i++)
	{
	x=x<<1|SG[i];
	if(!SG[i])
	for(j=0;j<n;j++)
	SG[take[j]+i]=1;
	}
	for(vis[x]=0,k=1;;i++,k++)
	{
	x=(x<<1|SG[i])%MOD;
	if(~vis[x]) break;
	if(!SG[i])
	for(j=0;j<n;j++)
	SG[take[j]+i]=1;
	vis[x]=k;
	}
	for(i=0;i<vis[x];i++)
	if(SG[i]) ans++;
	for(tmp=0;i<k;i++)
	if(SG[i]) tmp++;
	ans+=tmp*((m-vis[x]+1)/(k-vis[x])),tmp=(m-vis[x]+1)%(k-vis[x]);
	for(i=0;i<tmp;i++)
	if(SG[i+vis[x]]) ans++;
	cout << ans << "\n";
	}
	}

view raw gistfile1.txt hosted with ❤ by GitHub

\