1349. 参加考试的最大学生数     状态压缩。将每一行的学生的状态看作,表示第行状态为时前行的最大学生数量。状态转移方程：。。  class Solution { public: int maxStudents(vector<vector<char>>& a) { int m=a.size(),n=a[0].size(); int dp[10][1<<9]={0},ans=0; for(int j=0;j<(1<<n);j++)if(ok(a,0,j))dp[0][j]=__builtin_popcount(j); for(i...

求和         #include<bits/stdc++.h> using namespace std; typedef long long ll; ll mod; const int N=1e6+6; bool vis[N]; ll prime[N],phi[N],tot; ll cal_2(__int128 n){ __int128 x=n*(n+1)*(n*2+1)/6; return x%mod; } ll cal_1(__int128 n){ __int128 x=n*(n+1)/2; return x%mod; } void pre(){ phi[1]=1; fo...

C.Dirichlet k -th root     狄利克雷卷积性质，和HDU-5628 Clarke and math这题一样。 复杂度.   #include<bits/stdc++.h> using namespace std; const int mod=998244353; typedef long long ll; const int N=1e5+5; ll f[N],g[N],t[N]; int n,k; ll ksm(ll a,ll b){ ll ans=1; for(;b>0;b>>=1,a=a*a%mod)if(b&1)ans=ans...

莫比乌斯函数，欧拉函数，，，，。 为的不同素因子个数，为的所有素因子个数。。

Easy Problem     当时现场赛因为题我推的公式，化简的时候，出现了这个错误，导致找bug找了2个小时。A掉之后已经没有时间写题了，学了这么久的数论，题真的是再简单不过的反演了，但是策略有问题，加上化简公式时出现的错误，没来的及写，真的很可惜。 最后用欧拉降幂，线性筛即可。   #include<bits/stdc++.h> #define me(a,x) memset(a,x,sizeof(a)) #define sc scanf using namespace std; const int N=1e5+5; const int mod=59964251; typed...

HDU-6363 bookshelf  Patrick Star bought a bookshelf, he named it ZYG !! Patrick Star has book . The ZYG has layers (count from to ) and there is no limit on the capacity of each layer ! Now Patrick want to put all books on ZYG : 1. Assume that the i-th layer has books finally. 2. Assume that is the ...

GCD Array  Teacher Mai finds that many problems about arithmetic function can be reduced to the following problem:Maintain an array a with index from to . There are two kinds of operations:  Add to for every that . Query     插入操作：  2. 查询操作：    #include<bits/stdc++.h> #define me(a,x) memset(a,x...

Divisor Sums

codeforces-839D Winter is here     设，则答案可以表示为设，设的倍数个数为,则。所以有，反演得。   #include<bits/stdc++.h> using namespace std; const int N=1e6+6; const int p=1e9+7; typedef long long ll; ll ksm(ll a,ll b){ll ans=1;for(;b>0;b>>=1,a=a*a%p)if(b&1)ans=ans*a%p;return ans;} short int mu[N]; int flag[...

codeforces-1017F The Neutral Zone     这题内存限制只有16MB,考虑将2和3的倍数筛去，剩下的数只有1e8个，然后用bitset做标记数组，内存就只需要12MB.标记的数字下标刚好是i/3.   #include<bits/stdc++.h> #define me(a,x) memset(a,x,sizeof(a)) #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout); #define sc scanf #define itn int...

HDU-6134 Battlestation Operational       #include<bits/stdc++.h> using namespace std; const int N=1e6+6; const int p=1e9+7; typedef long long ll; short int mu[N]; bool vis[N]; int prime[N],tot=0; ll phi[N],f[N],g[N]; void pre(){ phi[1]=mu[1]=1; for(int i=2;i<N;i++){ if(!vis[i])prime[++tot]=...

GCD of Divisors

HDU-6102 GCDispower  给定一个的一个排列，有个查询。每次询问输出   离线处理,对于每次的询问,等价于求. 可以考虑枚举，讲右端点固定，那么对于这个区间中，所有的后 互相互质的对数乘，就是对左端点，所有区间的贡献。 将的倍数且位置小于的数筛出来后，考虑从大到小枚举，每次求与中互质的个数乘 也就是 是从大到小扫过之后整除的个数。利用树状数组区间修改，最后查询每个的值就行。   #include<bits/stdc++.h> using namespace std; #define IN freopen("in.txt","r",stdin); const int ...

Product        #include<bits/stdc++.h> #define me(a,x) memset(a,x,sizeof(a)) #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout); #define sc scanf #define itn int #define STR clock_t startTime = clock(); #define END clock_t endTime = clock();cout << double(e...