題意：求i&M的popcount的和，i屬于0……N
主要思路還是變加為乘。
舉個例子N=22，即10110
假設M的第3位是1，分析N中：
00110
00111
00100
00101
發現其實等價于
0010
0011
0000
0001
也就是左邊第4位和第5位不變，右邊第1位和第2位不變拼接起來，相當于0000~0011
01110
01111
01100
01101
等價于：
0110
0111
0100
0101
相當于0100~0111
10110
10111
10100
10101
相當于1000~1010
最后把3個部分合一起就是0000~1010
如果M的第3位是0，比如說10010（二進制），其實等價于求01110這個二進制數
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
ll ans,n,m;
int main(){cin>>n>>m;for(int i=0;i<60;i++){if((m>>i)&1){ll mask=(1ll<<i)-1;if((n>>i)&1){ll tmp=(n>>(i+1)<<i)|(n&mask);//左邊拼接上右邊ans=(ans+tmp+1)%mod;} else {ll t=(n-(1ll<<i))|mask;//先把n更新一下，注意要把右邊變成最大值ll tmp=(t>>(i+1)<<i)|(t&mask);//同樣處理ans=(ans+tmp+1)%mod;}}}cout<<ans;
}
題意：共n把鑰匙m次測試，至少k把鑰匙才打開門，問滿足所有測試條件的真鑰匙的組合種類
位元枚舉：用位元表示所有真鑰匙的組合，然后保存每個測試的鑰匙狀態，滿足所有測試就是答案組合
#include <bits/stdc++.h>
using namespace std;
int keys[20];
char r[105];
int f(int x){int ct=0;while(x){if(x&1)ct++;x>>=1;}return ct;
}
int main(){int n,m,k;cin>>n>>m>>k;//n把鑰匙，m個測試，至少k把鑰匙才能打開門for(int i=0;i<m;i++){int c;cin>>c;while(c--){int a;cin>>a;keys[i]|=1<<(a-1);//把i測試用的鑰匙存起來}cin>>r[i];//最終門的狀態}int ans=0;for(int s=0;s<(1<<n);s++){//枚舉所有正確鑰匙的組合情況bool er=0;for(int i=0;i<m;i++){//看看是否滿足所有的測試用例if((f(keys[i]&s)>=k&&r[i]!='o')||(f(keys[i]&s)<k&&r[i]=='o')){er=1;break;}}ans+=!er;}cout<<ans;
}
不難發現：10101010101010101010 = 10*（1010101010101010101）
就是10*(10^0+10^2+10^4+10^6+10^8+10^10+10^12+10^14+10^16+10^18) 進行等比求和：
10*(10^20-1)/(10^2-1)
那么輸入一個N，我們計算出其長度len
就是：N*(10^0+10^len+10^len*2+10^len*3+……+10^len*n-1)
就是N*(10^len*n)/(10^len-1)
然后知識點：a/b%mod=a*b^(mod-2)%mod
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=998244353;
ll f(ll x,ll y){x%=MOD;ll res=1;while(y){if(y&1)res=res*x%MOD;y>>=1;x=x*x%MOD;}return res;
}
ll inv(ll x){return f(x,MOD-2);
}
int main(){ll n;cin>>n;int len=(to_string(n)).size();cout<<n%MOD * (f(f(10,n),len)-1)%MOD * inv(f(10,len)-1)%MOD<<'\n';
}
題意：一共有n個店，每個店有許多口味，問能嘗到所有口味至少要去多少家店
位元枚舉：用位元來表示所有店的組合，并保存每個店提供的口味狀態，如果某個組合中可提供所有的口味就行
#include <bits/stdc++.h>
using namespace std;
int d[10];
int main(){int n,m;cin>>n>>m;//n個店，m種口味for(int i=0;i<n;i++){string s;cin>>s;for(char c:s){d[i]=(d[i]<<1)+(c=='o');//保存第i個店賣的口味狀態}}int an=100;for(int i=0;i<(1<<n);i++){//枚舉所有的店的組合int now=0,cnt=0;for(int j=0;j<n;j++){if((i>>j)&1)now|=d[j],cnt++;//把組合中的每個店賣的東西都合并起來}if(now==(1<<m)-1)an=min(an,cnt);//如果當好覆蓋了所有口味，那就更新一次答案}cout<<an;
}
