1009
这么能猜?
这个数据范围,对博弈论来说一定存在某种结论。故这题是结论题。
设\(dp[n]\)表示有\(n\)个物体时敌方先手，我的胜率。则敌方先手后轮到我时有n-1或者n-4个物体，我再取物体。我取物体时肯定要的是胜率最大，所以有转移方程\(dp[n]=\frac{1}{2}*max(dp[n-1-1],dp[n-1-4])+\frac{1}{2}*max(dp[n-4-1],dp[n-4-4]))=\frac{max(dp[n-2],dp[n-5])+max(dp[n-5],dp[n-8])}{2}\)。数组越界时说明不存在这种选取方案。可以根据这个递推式打表或者手搓20以内的结果，就能发现规律。
赛时还是不够冷静啊!!!,可惜了，代码如下：
const int mod=998244353;int ksm(int x,int y){int ans=1,base=x;while(y){if(y&1){ans*=base;ans%=mod;}base*=base;base%=mod;y>>=1;}return ans%mod;
}
int inv(int x){return ksm(x,mod-2)%mod;
}void solve(){int n;cin>>n;int m=n%5,a,b;//a分母,b分子if(m==2||m==0){cout<<1<<endl;return;}else if(m==1){if(n==1) a=2,b=1;else a=ksm(2,n/5),b=a-1;}else if(m==3){if(n==3) a=4,b=3;else a=ksm(2,ceil(n/5.0)+1),b=a-1;}else if(m==4){if(n==4) a=2,b=1;else a=ksm(2,ceil(n/5.0)),b=a-1;}cout<<(b%mod*inv(a)%mod)%mod<<endl;
}
等整理完最近的学习笔记，再来追更1004和1003
耽搁了好久，过来更新了。
1004
这个题的第一眼我的想法是多重背包,可以对余数分类，然后可以求出每个余数类有多少个，那么这个题就相当于从每个类中取若干个，然后求和，要求最后的和模m为0，求方案数。看一眼数据范围，嗯，写不了。多重背包有一维是每种物品的方案数，所以这么想肯定不行。
经过后来的学习，了解到生成函数也可以求方案数，现在讲解这种方法。
我们对每个余数分类后，对某一余数类中的某一个数，都有两种状态，选或者不选，假设这个数为\(a\)，那么就有生成函数\(x^{0*a}+x^{1*a}\)，要取模的话，就是\(1+x^{r}\)，而有\(cnt[r]\)个这样的数，那么这个余数类\(r\)能够形成的方案数的生成函数就是\((1+x^r)^{cnt[r]}\)。在这个多项式中\(x\)并无实际意义，\(x\)的指数是每种方案取出来的数的和，而\(x\)的系数就是对应的方案数。事实上这个就是\(01\)背包的生成函数，所以也能看到有大神用\(01\)背包做。我们将每一个余数类的多项式乘在一起，\((1+x^0)^{cnt[0]}*(1+x^1)^{cnt[0]}……*(1+x^{m-1})^{cnt[m-1]}\)。这个多项式展开后，系数，指数所代表的意义依然不变，这也就是说，所有指数为\(m\)的倍数的项的系数之和，就是我们要求的答案。更进一步，如果我们在处理多项式的时候就对指数的运算进行取模，那么所有指数为\(m\)倍数的项取模后都会变成\(0\),这也就意味着最后的答案是取模处理后多项式中指数为\(0\)的项的系数\(-1\)，\(-1\)是因为取模处理前的多项式含有指数为\(0\)的项，而0本身不算作\(m\)的倍数(准确的说不是我们要的和)，所以取模后要把原本包含的这个减掉，而指数为\(0\)意味着和为\(0\)，那就是一个数都不选，方案数为\(1\)，所以要减\(1\)，这也是部分大佬代码中\(ans[0]-1\)的由来。
所以，问题本身就变成了求多项式的系数。
代码方面\((1+x^r)^{cnt[r]}\)，多项式快速幂即可。每个余数类的多项式相乘，卷积即可。时间复杂度\(O(能过)\)
#define int long long
const int mod=998244353;std::vector<int> mul(std::vector<int>&a,std::vector<int>&b,int m){std::vector<int>ans(m,0);for(int i=0;i<a.size();i++){for(int j=0;j<b.size();j++){ans[(i+j)%m]=(ans[(i+j)%m]%mod+(a[i]%mod*b[j]%mod))%mod;}}return ans;
}std::vector<int> pksm(std::vector<int>&a,int b,int m){std::vector<int>ans(m,0); ans[0]=1;std::vector<int>base=a;while(b){if(b&1)ans=mul(ans,base,m);base=mul(base,base,m);b>>=1;}return ans;
}void solve(){int n,m;std::cin>>n>>m;std::vector<int>cnt(m,0);for(int r=0;r<m;r++){if(r>n) cnt[r]=0;else if(!r) cnt[r]=n/m;else cnt[r]=(n-r)/m+1;}std::vector<int>ans(m,0); ans[0]=1;for(int r=0;r<m;r++){if(!cnt[r]) continue;std::vector<int>a(m,0);if(!r) a[0]=2;else a[0]=1,a[r]=1;a=pksm(a,cnt[r],m);ans=mul(a,ans,m);}std::cout<<(ans[0]-1+mod)%mod<<'\n';
}