Meaningless Sequence Gym - 102832D

題意：

給你n和c，an的公式如下圖

讓你求a0+…an的和，mod 1e9+7

題解：

訓練時推了好一陣子才和隊友推出
我看網上正解為：
一個數的大小與它的二進制表示中的1的個數有關
a=c^{(二進制中1的個數)}
問題就變成了轉化為求所有數中1的個數，
dp[i][j]為考慮i~n位，有j個1的情況有多少種，然后數位dp跑，詳細可以看代碼

訓練時我們是找到了規律，我通過列出1~20的ai答案，發現規律，比如7，對應的二進制是111，那么它就等于去掉最高位剩下部分對應的數乘c，111去掉最高位就是011，也就是3，而3對應的是c²,所以7就是c³,（當然3也可以通過這個方法得到），邊界就是00對應1，01對應c
而且還有規律，第一位+第二位的和乘以c就是第三位加第四位的和，前四位的和乘c，就是5到8位的和，也就是sum=(c+1),sum+=sum*c，看幾輪

根據這些性質我們就可以算出答案，比如1000(二進制)，我們可以計算出111部分的答案，就是sum=(c+1),進行兩輪的sum+=sum * c,然后讓1100減去111，得到0101，重復這個過程，先計算11的答案，然后減11，一值重復，直到最后位，最后得到答案(不是很明白的可以看看代碼)

代碼：

數位dp

#include <cstdio> #include <algorithm> #include <cstring>using namespace std;const int mod = 1e9 + 7; typedef long long ll; char a[3005]; int n; ll dp[3005][3005],c;ll qpow(ll x,ll n) {ll res = 1;if(n == -1) return 0;while(n) {if(n & 1) {res = res * x % mod;}x = x * x % mod;n >>= 1;}return res; }ll dfs(int len,int sum,bool limit) {if(sum < 0) return 0;if(sum > n - len + 1) return 0;if(len == n + 1) {return sum == 0;}if(!limit && dp[len][sum] != -1) return dp[len][sum];int up = (limit ? (a[len] - '0') : 1);ll ans = 0;for(int i = 0;i <= up;i++) {ans += dfs(len + 1,sum - (i == 1),limit && i == up);ans %= mod;}return limit ? ans : dp[len][sum] = ans; }int main() {scanf("%s%lld",a + 1,&c);n = strlen(a + 1);memset(dp,-1,sizeof(dp));ll ans = 0;for(int i = 0;i <= n;i++) {ll num = dfs(1,i,true);ans = (ans + num * qpow(c,i) % mod) % mod;}printf("%lld\n",ans);return 0; }

規律遞推代碼：

#include <bits/stdc++.h> using namespace std; #define ll long long #define INF 0x3f3f3f3f const int mod=1e9+7; ll poww(ll a,ll b){ll ans=1;while(b){if(b&1)ans*=a%mod;a*=a%mod;b>>=1;}return ans%mod; } string s;ll c; ll cal(int len){ll sum=(c+1)%mod;for(int i=1;i<len;i++){sum=(sum+sum*c%mod)%mod;}return sum; }int main(){cin>>s>>c;ll sum=0;int len=s.length();if(s[len-1]=='0'){sum=1;}else sum=c+1;for(int i=len-2;i>=0;--i){if(s[i]!='0'){sum=sum*c%mod;sum=(sum+cal(len-i-1))%mod;} // cout<<sum<<endl;} // sum+=cal(len-1); // for(int i=0;i<len;i++){ // if(n[i]=='1') // sum+=cal(len-i-1); // }cout<<sum;return 0; }

總結

以上是生活随笔為你收集整理的Meaningless Sequence Gym - 102832D的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。