DP61. 串
描述
输入描述
一个正整数()输出描述
一个正整数,为满足条件的字符串数量对取模的值示例1
输入:
2
输出:
1
说明:
仅有“us”这一个字符串合法示例2
输入:
3
输出:
77
说明:
示例3
输入:
874520
输出:
16471619
C++ 解法, 执行用时: 3ms, 内存消耗: 404KB, 提交时间: 2021-12-11
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e9+7; ll p(ll x, ll n) { ll a = 1; while (n) { if (n&1) a = a*x%mod; x=x*x%mod; n>>=1; } return a; } ll d(ll n) { return p(n, mod-2); } int main() { ios::sync_with_stdio(false); ll n; cin >> n; cout << (26*(p(26, n)-1+mod)%mod*d(25)%mod - 25*(p(25, n)-1+mod)%mod*d(24)%mod + ((p(25, n)-1+mod)%mod*d(24)%mod-n*p(25,n)%mod+mod)*d(24)%mod + mod)%mod<< endl; return 0; }
C++ 解法, 执行用时: 3ms, 内存消耗: 416KB, 提交时间: 2021-12-21
#include <bits/stdc++.h> using namespace std; template <typename T> inline void read(T &f) { f=0;T fu=1;char c=getchar(); while(c<'0'||c>'9') {if(c=='-'){fu=-1;}c=getchar();} while(c>='0'&&c<='9') {f=(f<<3)+(f<<1)+(c&15);c=getchar();} f*=fu; } template <typename T> void print(T x) { if(x<0) putchar('-'),x=-x; if(x<10) putchar(x+48); else print(x/10),putchar(x%10+48); } template <typename T> void print(T x, char t) { print(x);putchar(t); } typedef long long ll; typedef vector<int> VI; typedef pair<int,int> PII; const ll mod=1e9+7; ll powmod(ll a,ll b) { ll res=1; a%=mod; assert(b>=0); for(;b;b>>=1) { if(b&1) res=res*a%mod; a=a*a%mod; } return res; } ll _,n; namespace linear_seq { const int N=10010; ll res[N],base[N],_c[N],_md[N]; std::vector<ll>Md; void mul(ll *a,ll *b,int k) { for(int i=0;i<k+k;i++) _c[i]=0; for(int i=0;i<k;i++) if(a[i]) for(int j=0;j<k;j++) _c[i+j]=(_c[i+j]+a[i]*b[j])%mod; for(int i=k+k-1;i>=k;i--) if(_c[i]) for(int j=0;j<((int)(Md).size());j++) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod; for(int i=0;i<k;i++) a[i]=_c[i]; } int solve(ll n,VI a,VI b) { ll ans=0,pnt=0; int k=((int)(a).size()); assert(((int)(a).size())==((int)(b).size())); for(int i=0;i<k;i++) _md[k-1-i]=-a[i]; _md[k]=1; Md.clear(); for(int i=0;i<k;i++) if(_md[i]!=0) Md.push_back(i); for(int i=0;i<k;i++) res[i]=base[i]=0; res[0]=1; while((1ll<<pnt)<=n) pnt++; for(int p=pnt;p>=0;p--) { mul(res,res,k); if((n>>p)&1) { for(int i=k-1;i>=0;i--) res[i+1]=res[i]; res[0]=0; for(int j=0;j<((int)(Md).size());j++) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod; } } for(int i=0;i<k;i++) ans=(ans+res[i]*b[i])%mod; if(ans<0) ans+=mod; return ans; } VI BM(VI s) { VI C(1,1),B(1,1); int L=0,m=1,b=1; for(int n=0;n<((int)(s).size());n++) { ll d=0; for(int i=0;i<L+1;i++) d=(d+(ll)C[i]*s[n-i])%mod; if(d==0) ++m; else if(2*L<=n) { VI T=C; ll c=mod-d*powmod(b,mod-2)%mod; while(((int)(C).size())<((int)(B).size())+m) C.push_back(0); for(int i=0;i<((int)(B).size());i++) C[i+m]=(C[i+m]+c*B[i])%mod; L=n+1-L; B=T; b=d; m=1; } else { ll c=mod-d*powmod(b,mod-2)%mod; while(((int)(C).size())<((int)(B).size())+m) C.push_back(0); for(int i=0;i<((int)(B).size());i++) C[i+m]=(C[i+m]+c*B[i])%mod; ++m; } } return C; } int gao(VI a,ll n) { VI c=BM(a); c.erase(c.begin()); for(int i=0;i<((int)(c).size());i++) c[i]=(mod-c[i])%mod; return solve(n,c,VI(a.begin(),a.begin()+((int)(c).size()))); } }; void solve() { scanf("%lld",&n); vector<int>v; v.push_back(0); v.push_back(1); v.push_back(77); v.push_back(3928); v.push_back(166554); v.push_back(6347955); v.push_back(225658131); v.push_back(636707033); printf("%lld",linear_seq::gao(v,n-1)%mod); } int main() { #ifdef AC freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif clock_t program_start_clock=clock(); solve(); fprintf(stderr,"\nTotal Time: %lf ms",double(clock()-program_start_clock)/(CLOCKS_PER_SEC/1000)); return 0; }
C++ 解法, 执行用时: 3ms, 内存消耗: 496KB, 提交时间: 2022-05-08
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e9 + 7; ll p(ll x, ll n) { ll a = 1; while (n) { if (n & 1) a = a * x % mod; x = x * x % mod; n >>= 1; } return a; } ll d(ll n) { return p(n, mod - 2); } int main() { ios::sync_with_stdio(false); ll n; cin >> n; cout << (26 * (p(26, n) - 1 + mod) % mod * d(25) % mod - 25 * (p(25, n) - 1 + mod) % mod * d(24) % mod + ((p(25, n) - 1 + mod) % mod * d(24) % mod - n * p(25, n) % mod + mod)*d(24) % mod + mod) % mod << endl; return 0; }
C 解法, 执行用时: 8ms, 内存消耗: 352KB, 提交时间: 2021-12-03
#include <stdio.h> #define MOD (1000000000+7) int main() { int n; long long dp[1000001][3]={0}; long long count = 0; scanf("%d",&n); dp[1][0]=25; dp[1][1]=1; dp[1][2]=0; for(int i=2;i<=n;++i) { dp[i][0] = (dp[i-1][0]*25)%MOD; dp[i][1] = (dp[i-1][0]+dp[i-1][1]*25)%MOD; dp[i][2] = (dp[i-1][1]+dp[i-1][2]*26)%MOD; count = (count + dp[i][2]) % MOD; } printf("%lld",count); return 0; }
C++ 解法, 执行用时: 8ms, 内存消耗: 432KB, 提交时间: 2021-11-13
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MOD = 1e9+7; int dp[3]; int main() { int n; int ans = 0; scanf("%d" , &n); dp[0] = 1; for(int i=1;i<=n;++i) { dp[2]=(1ll*dp[1]+26ll*dp[2])%MOD; dp[1]=(1ll*dp[0]+25ll*dp[1])%MOD; dp[0]=25ll*dp[0]%MOD; ans=(1ll*ans+dp[2])%MOD; } printf("%lld\n",ans); }