Single Round Match 508 Round 1 - Division I, Level Two YetAnotherORProblem

很容易發現，滿足題目性質就意味着所有位的加法不能産生進位。于是所有位隻有兩種情況，都是0，或者是隻有一個1。我沒可以采用類似數位DP的方法，從高位向低位考慮。dp[i][j]表示考慮前i個高位，j是一個集合，表示n個數字的狀态。如果第k的數字的前i的高位已經小于原數了就是1，反之是0。因為在轉移的時候，j位上是1的一定可以在這一位上放1，否則當且僅當原數的第i位也是1才能放1。轉移分兩種情況，一個是全部放0，一個是放一個1，注意集合j的轉移就可以了。

#include <bits/stdc++.h>
using namespace std;
long long dp[70][1<<10];
const int MOD=1000000009;
class YetAnotherORProblem
{
public: int countSequences(vector<long long> a)
	{
		int n=a.size();
		dp[63][0]=1;
		for(int i=63;i>0;i--)
		{
			for(int j=0;j<(1<<n);j++)
			{
				if(!dp[i][j])
					continue;
				int cur=j;
				for(int k=0;k<n;k++)
				{
					if(a[k]&(1LL<<(i-1)))
						cur|=(1<<k);
				}
				dp[i-1][cur]=(dp[i-1][cur]+dp[i][j])%MOD;
				for(int k=0;k<n;k++)
				{
					if((1<<k)&j)
					{
						int st=j;
						for(int l=0;l<n;l++)
						{
							if(l==k)
								continue;
							if(a[l]&(1LL<<(i-1)))
							{
								st|=(1<<l);
							}
						}
						dp[i-1][st]=(dp[i-1][st]+dp[i][j])%MOD;
					}
					else
					{
						if(a[k]&(1LL<<(i-1)))
						{
							int st=j;
							for(int l=0;l<n;l++)
							{
								if(l==k)
									continue;
								if(a[l]&(1LL<<(i-1)))
								{
									st|=(1<<l);
								}
							}
							dp[i-1][st]=(dp[i-1][st]+dp[i][j])%MOD;
						}
					}
				}
			}
		}
		long long ans=0;
		for(int i=0;i<1<<n;i++)
			ans=(ans+dp[0][i])%MOD;
		return ans;
	}
};