dp变换种类数

sonambulo edited 4 年,4 月前

思路应该是有问题的,但是不知道这个dp大概是怎么写。(打表失败orz)

#include <bits/stdc++.h>
using namespace std;
#define n 1000000007

int main(){
    int t;cin>>t;while(t--){
        string s;cin>>s;int i,j,k,c,b,f,z,res,sum=0,l=s.size(),dp[l][l];
        for(i=0;i<l;i++){
            dp[i][i]=(s[i]-'0')%210;
            for(j=i+1;j<l;j++)dp[i][j]=(dp[i][j-1]*10+s[j]-'0')%210;
        }
        for(i=0;i<=(1<<l-1)-1;i++){
            c=0;k=i;while(k){k&=k-1;c++;}c=l-1-c;
            for(j=0;j<=(1<<c)-1;j++){
                b=0;f=1;z=0;res=0;
                for(k=0;k<l-1;k++){
                    if((1<<k)&i){res+=f*dp[b][k];f=1;b=k+1;}
                    else{
                        if((1<<z)&j){res+=f*dp[b][k];f=-1;b=k+1;}
                        z++;
                    }
                }
                res+=f*dp[b][l-1];
                if(res%2==0||res%3==0||res%5==0||res%7==0){sum++;sum%=n;}
            }
        }
        cout<<sum<<endl;
    }
}

Comments