Topic link :hdu 4828 Grids

The main idea of the topic : A little .

Their thinking : Think of the previous line as a stack , The next line is seen as out of the stack , So the persistent solution is the Cartland number , It is solved by recursion .

#include <cstdio>
#include <cstring> typedef long long ll;
const int N = 1000005;
const ll MOD = 1e9+7; ll dp[N]; ll extendGcd(ll a, ll b, ll& x, ll& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
} ll d = extendGcd(b, a%b, y, x);
y -= a / b * x;
return d;
} ll solve (ll n) {
ll x, y;
ll tmp = extendGcd(n + 1, MOD, x, y);
x = (x % MOD + MOD) % MOD;
return x;
} void init () {
dp[1] = 1;
dp[2] = 2;
for (ll i = 3; i < N; i++)
dp[i] = (dp[i-1] * (4 * i - 2) % MOD * solve(i)) % MOD;
} int main () {
int cas, n;
scanf("%d", &cas);
for (int i = 1; i <= cas; i++) {
scanf("%d", &n);
printf("Case #%d:\n%lld\n", i, dp[n]);
return 0;

hdu 4828 Grids( Expand Euclid + Carter LAN number ) More articles about

  1. NOIP2012 Expand Euclid

    Pull the board ,,, Shut up Did I say that data structure is boring ,,, I want to take back ,,, The number theory started today is still disgusting , I feel dizzy all morning Let's start with Euclid #include <cstdio> void gcd ...

  2. poj 1061 Frog dating Expand Euclidean template

    // poj 1061 Frog dating Expand Euclidean template // Pay attention to exgcd when , Guarantee a,b Positive number , If the final answer is negative , It's going to add a membrane #include <cstdio> #include ...

  3. bzoj4517: [Sdoi2016] Permutation count -- mathematics + Expand Euclid

    This is a math problem , From the title we can see ,m The way to get a stable number is Cnm Then left n-m This book , Because the number is i You can't put your books in i Location , Therefore, the number of methods should be determined by the staggered formula , namely D(n-m) The staggered formula :D[i]=(i-1)*(D[i-1]+ ...

  4. POJ 2891 Strange Way to Express Integers( Expand Euclid )

    Description Elina is reading a book written by Rujia Liu, which introduces a strange way to express ...

  5. POJ1061 Frog dating - Expand Euclid

    Description Two frogs met on the Internet , They had a good chat , So it's necessary to meet . They are happy to find that they live on the same latitude line , So they agreed to go west , Until we meet . But before they set out, they forgot a very important thing ...

  6. BZOJ-2242 Calculator Fast power + Expand Euclid +BSGS( Number theory is three in one )

    Dirty... Dirty 2242: [SDOI2011] Calculator Time Limit: 10 Sec Memory Limit: 512 MB Submit: 2312 Solved: 917 [Submit][S ...

  7. BZOJ-1407 Savage enumeration + Expand Euclid (+ Chinese remainder theorem ??)

    zky The strength of senior students ACM Competition system test , and Big news (YveH) and Wallace (hjxcpg) organize a team ...2h 10T, Start I do A, Big news B, Wallace C, So I started : But the first question is the giant ghost animal , Think about 40min Discovery seems impossible ...

  8. poj2891 Expand Euclid

    //Accepted 164 KB 16 ms // Expand Euclid //m=a1*x+b1 --(1) //m=a2*(-y)+b2 --(2) //->a1*x+a2*y=b2-b1 // From Europe to Japan ...

  9. [zoj 3774]Power of Fibonacci number theory ( Second surplus Expand Euclid Sum of equal ratio sequence )

    Power of Fibonacci Time Limit: 5 Seconds      Memory Limit: 65536 KB In mathematics, Fibonacci numbe ...

Random recommendation

  1. Aspose.Cells export Excel(1)

    utilize Aspose.Cells export excel Attention problem 1.DataTable To deal with 2. Encoding , Easy to download Chinese name file 3. Don't forget Aspose.Cells.dll( You can search online by yourself ) public ...

  2. gifted with an extraordinary retentive memory JS Regular expressions

    Regular expressions , There are people like me , I've learned it several times, but I'm still confused , I always understand when I study , I forgot all about it . ok , In fact, I didn't practice enough , The so-called learning from the past , I can be a teacher , Today, let me review the proud regular expression . Why regular expressions ...

  3. robots

    User-agent: Baiduspider Disallow: /w? Allow: / User-agent: Googlebot Allow: / User-agent: Googlebot- ...

  4. visit IIS Metabase failure resolution

    problem : Failed to access metadata Details visit IIS Metabase failed . explain : Execute the current Web During the period of the request , An unhandled exception occurred . Please check the stack trace information , To learn more about the error and the source of the error in the code . Unusual details ...

  5. Windows Network sharing permission settings

    There are two permission settings for file sharing , As long as you understand these two permission settings, you can use them flexibly in domain control . The first is network sharing rights Sharing permission is a means to control users' access to shared folders through the network , Sharing rights are only valid if the user accesses through the network , Local users are not subject to this permission ...

  6. Use Css Intercepting string

    white-space:nowrap; /* No word wrap */ overflow:hidden; /* Hide overflow */ text-overflow:ellipsis; /* Overflow text using ... ...

  7. Common objects API、 additional : Gather to supplement

    Basic data type object wrapper class : To facilitate the operation of basic data type values , Encapsulate it as an object , The attributes and behaviors defined in the object enrich the operation of the data . The class used to describe the object is called the basic data type object wrapper class . byte——Byte short ...

  8. C# CheckedListBox How to use control

    1. Add checkedListBox1.Items.Add(" Blue "); checkedListBox1.Items.Add(" Red "); checked ...

  9. Windows Built in security principals

    from : Reading guide : about Windows In particular, the built-in security agent needs to pay attention to : You can't create it . Rename and delete them , ...

  10. Use rpm-build Make nginx Of rpm package

    2014-11-27 11:05:49   One .RPM Classification of packages RPM There are five basic operating functions : install . uninstall . upgrade . Query and verify . linux Software packages fall into two categories : (1) Binary class package , Include rpm Installation package ( Generally divided into i ...