結果
問題 | No.315 世界のなんとか3.5 |
ユーザー |
|
提出日時 | 2021-09-15 23:09:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 134 ms / 2,000 ms |
コード長 | 5,275 bytes |
コンパイル時間 | 2,627 ms |
コンパイル使用メモリ | 204,668 KB |
最終ジャッジ日時 | 2025-01-24 14:11:36 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define rep(i,n) for(ll i=0;i<n;i++)#define repl(i,l,r) for(ll i=(l);i<(r);i++)#define per(i,n) for(ll i=(n)-1;i>=0;i--)#define perl(i,r,l) for(ll i=r-1;i>=l;i--)#define fi first#define se second#define pb push_back#define ins insert#define pqueue(x) priority_queue<x,vector<x>,greater<x>>#define all(x) (x).begin(),(x).end()#define CST(x) cout<<fixed<<setprecision(x)#define vtpl(x,y,z) vector<tuple<x,y,z>>#define rev(x) reverse(x);using ll=long long;using vl=vector<ll>;using vvl=vector<vector<ll>>;using pl=pair<ll,ll>;using vpl=vector<pl>;using vvpl=vector<vpl>;const ll MOD=1000000007;const ll MOD9=998244353;const int inf=1e9+10;const ll INF=4e18;const ll dy[9]={0,1,-1,0,1,1,-1,-1,0};const ll dx[9]={1,0,0,-1,1,-1,1,-1,0};template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}const int mod = 1000000007;const int max_n = 200005;struct mint {ll x; // typedef long long ll;mint(ll x=0):x((x%mod+mod)%mod){}mint operator-() const { return mint(-x);}mint& operator+=(const mint a) {if ((x += a.x) >= mod) x -= mod;return *this;}mint& operator-=(const mint a) {if ((x += mod-a.x) >= mod) x -= mod;return *this;}mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}mint operator+(const mint a) const { return mint(*this) += a;}mint operator-(const mint a) const { return mint(*this) -= a;}mint operator*(const mint a) const { return mint(*this) *= a;}mint pow(ll t) const {if (!t) return 1;mint a = pow(t>>1);a *= a;if (t&1) a *= *this;return a;}bool operator==(const mint &p) const { return x == p.x; }bool operator!=(const mint &p) const { return x != p.x; }// for prime modmint inv() const { return pow(mod-2);}mint& operator/=(const mint a) { return *this *= a.inv();}mint operator/(const mint a) const { return mint(*this) /= a;}};istream& operator>>(istream& is, mint& a) { return is >> a.x;}ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}using vm=vector<mint>;using vvm=vector<vm>;ll P=800;mint solve(string s){while(s.size()<20)s="0"+s;string t;while(t.size()<10){t+=s.back();s.pop_back();}rev(all(t));ll n=s.size();mint dp[n+1][3][2][2];//mod3,3を含むか,smallerrep(i,n+1)rep(j,3)rep(k,2)rep(l,2)dp[i][j][k][l]=0;dp[0][0][0][0]=1;rep(i,n){ll p=s[i]-'0';rep(j,3){rep(k,10){if(k==3){rep(l,2)dp[i+1][(j+k)%3][1][1]+=dp[i][j][l][1];}else {rep(l,2)dp[i+1][(j+k)%3][l][1]+=dp[i][j][l][1];}}rep(k,p){if(k==3){rep(l,2)dp[i+1][(j+k)%3][1][1]+=dp[i][j][l][0];}else {rep(l,2)dp[i+1][(j+k)%3][l][1]+=dp[i][j][l][0];}}if(p==3){rep(l,2)dp[i+1][(j+p)%3][1][0]+=dp[i][j][l][0];}else{rep(l,2)dp[i+1][(j+p)%3][l][0]+=dp[i][j][l][0];}}}/*mint ans=0;rep(i,3)rep(j,2)rep(k,2){cout << dp[n][i][j][k] << endl;if(i==0||j==1)ans+=dp[n][i][j][k];}return ans;*/ll m=t.size();mint ndp[m+1][3][2][2][P];//さらにmodpを加えるrep(i,m+1)rep(j,3)rep(k,2)rep(l,2)rep(t,P)ndp[i][j][k][l][t]=0;rep(i,3)rep(j,2)rep(k,2)ndp[0][i][j][k][0]+=dp[n][i][j][k];rep(i,m){ll p=t[i]-'0';rep(j,3){rep(k,P){rep(to,10){if(to==3){rep(l,2)ndp[i+1][(j+to)%3][1][1][(k*10+to)%P]+=ndp[i][j][l][1][k];}else{rep(l,2)ndp[i+1][(j+to)%3][l][1][(k*10+to)%P]+=ndp[i][j][l][1][k];}}rep(to,p){if(to==3){rep(l,2)ndp[i+1][(j+to)%3][1][1][(k*10+to)%P]+=ndp[i][j][l][0][k];}else{rep(l,2)ndp[i+1][(j+to)%3][l][1][(k*10+to)%P]+=ndp[i][j][l][0][k];}}if(p==3){rep(l,2)ndp[i+1][(j+p)%3][1][0][(k*10+p)%P]+=ndp[i][j][l][0][k];}else{rep(l,2)ndp[i+1][(j+p)%3][l][0][(k*10+p)%P]+=ndp[i][j][l][0][k];}}}}mint ans=0;rep(j,3)rep(k,2)rep(l,2)rep(t,P){if((t!=0)&&(j==0||k==1))ans+=ndp[m][j][k][l][t];}return ans;}int main(){string a,b;cin >> a >> b;cin >> P;mint ans=solve(b)-solve(a);ll th=0,ex=0,ei=0;rep(i,a.size()){th*=10;ei*=10;ll p=a[i]-'0';if(p==3)ex=1;th+=p;ei+=p;th%=3;ei%=P;}if(((th==0)||ex)&&(ei!=0)){ans+=1;}cout << ans << endl;}